Anonymous user
Closest-pair problem: Difference between revisions
→{{header|Microsoft Small Basic}}
m (→{{header|REXX}}: added whitespace in the output section header.) |
|||
Line 2,671:
[0.925092,0.818220]
</pre>
=={{header|Nim}}==
<lang Nim>import math, algorithm
type
Point = tuple[x, y: float]
Pair = tuple[p1, p2: Point]
Result = tuple[minDist: float; minPoints: Pair]
#---------------------------------------------------------------------------------------------------
template sqr(x: float): float = x * x
#---------------------------------------------------------------------------------------------------
func dist(point1, point2: Point): float =
sqrt(sqr(point2.x - point1.x) + sqr(point2.y - point1.y))
#---------------------------------------------------------------------------------------------------
func bruteForceClosestPair*(points: openArray[Point]): Result =
doAssert(points.len >= 2, "At least two points required.")
result.minDist = Inf
for i in 0..<points.high:
for j in (i + 1)..points.high:
let d = dist(points[i], points[j])
if d < result.minDist:
result = (d, (points[i], points[j]))
#---------------------------------------------------------------------------------------------------
func closestPair(xP, yP: openArray[Point]): Result =
## Recursive function which takes two open arrays as arguments: the first
## sorted by increasing values of x, the second sorted by increasing values of y.
if xP.len <= 3:
return xP.bruteForceClosestPair()
let m = xP.high div 2
let xL = xP[0..m]
let xR = xP[(m + 1)..^1]
let xm = xP[m].x
var yL, yR: seq[Point]
for p in yP:
if p.x <= xm: yL.add(p)
else: yR.add(p)
let (dL, pairL) = closestPair(xL, yL)
let (dR, pairR) = closestPair(xR, yR)
let (dMin, pairMin) = if dL < dR: (dL, pairL) else: (dR, pairR)
var yS: seq[Point]
for p in yP:
if abs(xm - p.x) < dmin: yS.add(p)
result = (dMin, pairMin)
for i in 0..<yS.high:
var k = i + 1
while k < yS.len and ys[k].y - yS[i].y < dMin:
let d = dist(yS[i], yS[k])
if d < result.minDist:
result = (d, (yS[i], yS[k]))
inc k
#---------------------------------------------------------------------------------------------------
func closestPair*(points: openArray[Point]): Result =
let xP = points.sortedByIt(it.x)
let yP = points.sortedByIt(it.y)
doAssert(points.len >= 2, "At least two points required.")
result = closestPair(xP, yP)
#———————————————————————————————————————————————————————————————————————————————————————————————————
import random, times, strformat
randomize()
const N = 50_000
const Max = 10_000.0
var points: array[N, Point]
for pt in points.mitems: pt = (rand(Max), rand(Max))
echo "Sample contains ", N, " random points."
echo ""
let t0 = getTime()
echo "Brute force algorithm:"
echo points.bruteForceClosestPair()
let t1 = getTime()
echo "Optimized algorithm:"
echo points.closestPair()
let t2 = getTime()
echo ""
echo fmt"Execution time for brute force algorithm: {(t1 - t0).inMilliseconds:>4} ms"
echo fmt"Execution time for optimized algorithm: {(t2 - t1).inMilliseconds:>4} ms"</nim>
{{out}}
<pre>Sample contains 50000 random points.
Brute force algorithm:
(minDist: 0.1177082437919083, minPoints: (p1: (x: 3686.601318778875, y: 2187.261792916939), p2: (x: 3686.483703931143, y: 2187.257104820359)))
Optimized algorithm:
(minDist: 0.1177082437919083, minPoints: (p1: (x: 3686.483703931143, y: 2187.257104820359), p2: (x: 3686.601318778875, y: 2187.261792916939)))
Execution time for brute force algorithm: 2656 ms
Execution time for optimized algorithm: 63 ms</pre>
=={{header|Objective-C}}==
| |||