Closest-pair problem: Difference between revisions
Content added Content deleted
| Line 214: | Line 214: | ||
<lang d>import std.stdio,std.typecons,std.math,std.algorithm,std.array,std.random; |
<lang d>import std.stdio,std.typecons,std.math,std.algorithm,std.array,std.random; |
||
auto |
auto bruteForceClosestPair(cdouble[] points) { |
||
auto minD = typeof(points[0].re).infinity; |
auto minD = typeof(points[0].re).infinity; |
||
typeof(points[0]) minI, minJ; |
|||
foreach (i; 0 .. points.length-1) |
foreach (i; 0 .. points.length-1) |
||
foreach (j; i+1 .. points.length) { |
foreach (j; i+1 .. points.length) { |
||
| Line 222: | Line 222: | ||
if (dist < minD) { |
if (dist < minD) { |
||
minD = dist; |
minD = dist; |
||
minI = i; |
minI = points[i]; |
||
minJ = j; |
minJ = points[j]; |
||
} |
} |
||
} |
} |
||
return tuple(minD, |
return tuple(minD, minI, minJ); |
||
} |
} |
||
| Line 290: | Line 290: | ||
A faster brute-force version: |
A faster brute-force version: |
||
<lang d>import std.stdio, std.typecons, std.math, std.random; |
<lang d>import std.stdio, std.typecons, std.math, std.random; |
||
| ⚫ | |||
auto bruteForceClosestPair2(cdouble[] points) { |
auto bruteForceClosestPair2(cdouble[] points) { |
||
auto minD = typeof(points[0].re).infinity; |
auto minD = typeof(points[0].re).infinity; |
||
if (points.length < 2) |
|||
return tuple(minD, typeof(points[0]).nan, typeof(points[0]).nan); |
|||
size_t minI, minJ; |
size_t minI, minJ; |
||
foreach (i; 0 .. points.length-1) |
foreach (i; 0 .. points.length-1) { |
||
auto points_i_re = points[i].re; |
|||
auto points_i_im = points[i].im; |
|||
foreach (j; i+1 .. points.length) { |
foreach (j; i+1 .. points.length) { |
||
auto dre = |
auto dre = points_i_re - points[j].re; |
||
auto |
auto dist = dre * dre; |
||
auto dist = dre * dre + dim * dim; |
|||
if (dist < minD) { |
if (dist < minD) { |
||
auto dim = points_i_im - points[j].im; |
|||
dist += dim * dim; |
|||
if (dist < minD) { |
|||
minD = dist; |
|||
minI = i; |
|||
minJ = j; |
|||
} |
|||
} |
} |
||
} |
} |
||
} |
|||
return tuple(sqrt(minD), points[minI], points[minJ]); |
return tuple(sqrt(minD), points[minI], points[minJ]); |
||
} |
|||
| ⚫ | |||
void main() { |
|||
auto rnd = Random(1); |
|||
auto points = new cdouble[10_000]; |
|||
foreach (ref p; points) |
|||
p = uniform(0.0, 1000.0, rnd) + uniform(0.0, 1000.0, rnd) * 1i; |
|||
writeln("bruteForceClosestPair2: ", bruteForceClosestPair2(points)); |
|||
} |
} |
||
| Line 315: | Line 331: | ||
writeln("bruteForceClosestPair2: ", bruteForceClosestPair2(points)); |
writeln("bruteForceClosestPair2: ", bruteForceClosestPair2(points)); |
||
}</lang> |
}</lang> |
||
Time gave 0: |
Time gave 0:00.89 elapsed for brute-force version 2 (10_000 points). |
||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |
||