K-d tree: Difference between revisions
Content added Content deleted
(Updated D entry) |
(+ second D entry) |
||
Line 439: | Line 439: | ||
Visited an average of 43.10 nodes on 10000 searches in 213ms.</pre> |
Visited an average of 43.10 nodes on 10000 searches in 213ms.</pre> |
||
===Faster Alternative Version=== |
|||
{{trans|C}} |
|||
This version performs less lookups. Compiled with DMD this version is two times slower than the C version. |
|||
<lang d>import std.stdio, std.algorithm, std.math, std.random, std.typetuple; |
|||
enum maxDim = 3; |
|||
template Iota(int stop) { |
|||
static if (stop <= 0) |
|||
alias TypeTuple!() Iota; |
|||
else |
|||
alias TypeTuple!(Iota!(stop - 1), stop - 1) Iota; |
|||
} |
|||
struct KdNode { |
|||
double[maxDim] x; |
|||
KdNode* left, right; |
|||
} |
|||
// See QuickSelect method. |
|||
KdNode* findMedian(size_t idx)(KdNode[] nodes) pure nothrow { |
|||
auto start = nodes.ptr; |
|||
auto end = &nodes[$ - 1] + 1; |
|||
if (end <= start) |
|||
return null; |
|||
if (end == start + 1) |
|||
return start; |
|||
KdNode* md = start + (end - start) / 2; |
|||
while (true) { |
|||
immutable double pivot = md.x[idx]; |
|||
swap(md.x, (end - 1).x); // Swaps the whole arrays x. |
|||
auto store = start; |
|||
foreach (p; start .. end) { |
|||
if (p.x[idx] < pivot) { |
|||
if (p != store) |
|||
swap(p.x, store.x); |
|||
store++; |
|||
} |
|||
} |
|||
swap(store.x, (end - 1).x); |
|||
// Median has duplicate values. |
|||
if (store.x[idx] == md.x[idx]) |
|||
return md; |
|||
if (store > md) |
|||
end = store; |
|||
else |
|||
start = store; |
|||
} |
|||
} |
|||
KdNode* makeTree(size_t dim, size_t i)(KdNode[] nodes) pure nothrow { |
|||
if (!nodes.length) |
|||
return null; |
|||
auto n = findMedian!i(nodes); |
|||
if (n != null) { |
|||
enum i2 = (i + 1) % dim; |
|||
immutable size_t nPos = n - nodes.ptr; |
|||
n.left = makeTree!(dim, i2)(nodes[0 .. nPos]); |
|||
n.right = makeTree!(dim, i2)(nodes[nPos + 1 .. $]); |
|||
} |
|||
return n; |
|||
} |
|||
void nearest(size_t dim)(in KdNode* root, in ref KdNode nd, |
|||
in size_t i, ref const(KdNode)* best, |
|||
ref double bestDist, ref size_t nVisited) |
|||
pure nothrow { |
|||
static double dist(in ref KdNode a, in ref KdNode b) pure nothrow { |
|||
typeof(KdNode.x[0]) result = 0; |
|||
foreach (i; Iota!dim) |
|||
result += (a.x[i] - b.x[i]) ^^ 2; |
|||
return result; |
|||
} |
|||
if (root == null) |
|||
return; |
|||
immutable double d = dist(*root, nd); |
|||
immutable double dx = root.x[i] - nd.x[i]; |
|||
immutable double dx2 = dx ^^ 2; |
|||
nVisited++; |
|||
if (!best || d < bestDist) { |
|||
bestDist = d; |
|||
best = root; |
|||
} |
|||
// If chance of exact match is high. |
|||
if (!bestDist) |
|||
return; |
|||
immutable i2 = (i + 1 >= dim) ? 0 : i + 1; |
|||
nearest!dim(dx > 0 ? root.left : root.right, |
|||
nd, i2, best, bestDist, nVisited); |
|||
if (dx2 >= bestDist) |
|||
return; |
|||
nearest!dim(dx > 0 ? root.right : root.left, |
|||
nd, i2, best, bestDist, nVisited); |
|||
} |
|||
void randPt(size_t dim=3)(ref KdNode v, ref Xorshift rng) nothrow { |
|||
foreach (i; Iota!dim) { |
|||
v.x[i] = rng.front() / cast(double)Xorshift.max; |
|||
rng.popFront(); |
|||
} |
|||
} |
|||
void smallTest() { |
|||
KdNode[] wp = [{[2, 3]}, {[5, 4]}, {[9, 6]}, |
|||
{[4, 7]}, {[8, 1]}, {[7, 2]}]; |
|||
KdNode thisPt = {[9, 2]}; |
|||
KdNode* root = makeTree!(2, 0)(wp); |
|||
KdNode* found = null; |
|||
double bestDist = 0; |
|||
size_t nVisited = 0; |
|||
nearest!2(root, thisPt, 0, found, bestDist, nVisited); |
|||
writefln("WP tree:\n Searching for %s\n" |
|||
" Found %s, dist = %g\n Seen %d nodes.\n", |
|||
thisPt.x[0..2], found.x[0..2], sqrt(bestDist), nVisited); |
|||
} |
|||
void bigTest() { |
|||
enum N = 1_000_000; |
|||
enum testRuns = 100_000; |
|||
auto bigTree = new KdNode[N]; |
|||
auto rng = Xorshift(1); |
|||
foreach (ref node; bigTree) |
|||
randPt(node, rng); |
|||
KdNode* root = makeTree!(3, 0)(bigTree); |
|||
KdNode thisPt; |
|||
randPt(thisPt, rng); |
|||
KdNode* found = null; |
|||
double bestDist = 0; |
|||
size_t nVisited = 0; |
|||
nearest!3(root, thisPt, 0, found, bestDist, nVisited); |
|||
writefln("Big tree (%d nodes):\n Searching for %s\n"~ |
|||
" Found %s, dist = %g\n Seen %d nodes.", |
|||
N, thisPt.x, found.x, sqrt(bestDist), nVisited); |
|||
size_t sum = 0; |
|||
foreach (_; 0 .. testRuns) { |
|||
found = null; |
|||
nVisited = 0; |
|||
randPt(thisPt, rng); |
|||
nearest!3(root, thisPt, 0, found, bestDist, nVisited); |
|||
sum += nVisited; |
|||
} |
|||
writefln("\nBig tree:\n Visited %d nodes for %d random "~ |
|||
"searches (%.2f per lookup).", |
|||
sum, testRuns, sum / cast(double)testRuns); |
|||
} |
|||
void main() { |
|||
smallTest(); |
|||
bigTest(); |
|||
}</lang> |
|||
{{out}} |
|||
<pre>WP tree: |
|||
Searching for [9, 2] |
|||
Found [8, 1], dist = 1.41421 |
|||
Seen 3 nodes. |
|||
Big tree (1000000 nodes): |
|||
Searching for [0.225893, 0.725471, 0.486279] |
|||
Found [0.220761, 0.729613, 0.489134], dist = 0.00718703 |
|||
Seen 35 nodes. |
|||
Big tree: |
|||
Visited 4267592 nodes for 100000 random searches (42.68 per lookup).</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |