Closest-pair problem: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Line 288: Line 288:
Time gave 0:04.03 elapsed for brute force version, and 0:00.06 elapsed for the divide & conquer one (10_000 points).
Time gave 0:04.03 elapsed for brute force version, and 0:00.06 elapsed for the divide & conquer one (10_000 points).


A more efficient implementation of the brute-force algorithm:
A more efficient implementation of the brute-force algorithm, D version 1 with Tango library, LDC compiler:
<lang d>import std.stdio, std.typecons, std.math, std.random;
<lang d>import tango.stdc.stdio, tango.stdc.stdlib, tango.math.Math;


auto bruteForceClosestPair2(cdouble[] points) {
void bfClosestPair2(cdouble[] points, out cdouble p1, out cdouble p2) {
auto minD = typeof(points[0].re).infinity;
auto minD = typeof(points[0].re).infinity;
if (points.length < 2)
if (points.length < 2) {
return tuple(minD, typeof(points[0]).nan, typeof(points[0]).nan);
p1 = p2 = typeof(points[0]).nan;
return;
}
size_t minI, minJ;
size_t minI, minJ;
foreach (i; 0 .. points.length-1) {
for (int i = 0; i < points.length-1; i++) {
auto points_i_re = points[i].re;
auto points_i_re = points[i].re;
auto points_i_im = points[i].im;
auto points_i_im = points[i].im;
foreach (j; i+1 .. points.length) {
for (int j = i+1; j < points.length; j++) {
auto dre = points_i_re - points[j].re;
auto dre = points_i_re - points[j].re;
auto dist = dre * dre;
auto dist = dre * dre;
Line 313: Line 315:
}
}
}
}

return tuple(sqrt(minD), points[minI], points[minJ]);
p1 = points[minI];
p2 = points[minJ];
}
}

void main() {
void main() {
auto rnd = Random(1);
auto points = new cdouble[10_000];
srand(31415);
auto points = new cdouble[10_000];

foreach (ref p; points)
foreach (ref p; points)
p = uniform(0.0, 1000.0, rnd) + uniform(0.0, 1000.0, rnd) * 1i;
p = 1000.0 * (cast(double)rand() / (RAND_MAX + 1.0)) +
writeln("bruteForceClosestPair2: ", bruteForceClosestPair2(points));
1000.0i * (cast(double)rand() / (RAND_MAX + 1.0));

cdouble p1, p2;
bfClosestPair2(points, p1, p2);
double dist = sqrt((p1.re - p2.re) * (p1.re - p2.re) +
(p1.im - p2.im) * (p1.im - p2.im));
printf("Closest pair: dist: %lf p1, p2: (%lf, %lf), (%lf, %lf)\n",
dist, p1.re, p1.im, p2.re, p2.im);
}</lang>
}</lang>
Time gave 0:00.78 elapsed for brute-force version 2 (10_000 points).
Time gave 0:00.15 elapsed for brute-force version 2 (10_000 points).


=={{header|F Sharp|F#}}==
=={{header|F Sharp|F#}}==
Retrieved from "https://rosettacode.org/wiki/Closest-pair_problem"