Anonymous user
K-d tree: Difference between revisions
→Faster Alternative Version: Added dim template parameter to KdNode, more idiomatic D code.
(Added Kotlin) |
(→Faster Alternative Version: Added dim template parameter to KdNode, more idiomatic D code.) |
||
Line 565:
{{trans|C}}
This version performs less lookups. Compiled with DMD this version is two times slower than the C version. Compiled with ldc2 it's a little faster than the C version compiled with gcc.
<lang d>import std.stdio, std.algorithm, std.math, std.random
struct KdNode(size_t dim) {▼
▲struct KdNode {
▲ double[maxDim] x;
KdNode* left, right;
}
// See QuickSelect method.
KdNode!dim* findMedian(size_t idx, size_t dim)(KdNode!dim[] nodes) pure nothrow @nogc {
auto start = nodes.ptr;
auto end = &nodes[$ - 1] + 1;
Line 584 ⟶ 582:
return start;
while (true) {
Line 611 ⟶ 609:
}
KdNode!dim* makeTree(size_t dim, size_t i = 0)(KdNode!dim[] nodes)
pure nothrow @nogc {
if (!nodes.length)
return null;
auto n = nodes.findMedian!i
if (n != null) {
enum i2 = (i + 1) % dim;
immutable size_t nPos = n - nodes.ptr;
n.left
n.right = makeTree!(dim, i2)(nodes[nPos + 1 .. $]);
}
Line 627 ⟶ 625:
}
void nearest(size_t dim)(in KdNode!dim* root,
in ref KdNode!dim nd,
in size_t i,
ref const(KdNode!dim)* best,
ref double bestDist,
ref size_t nVisited) pure nothrow @safe @nogc {
static double dist(in ref KdNode!dim a, in ref KdNode!dim b)
pure nothrow @nogc {
static foreach (
result += (a.x[i] - b.x[i]) ^^ 2;
return result;
Line 668 ⟶ 666:
}
void randPt(size_t dim
pure nothrow @safe @nogc {
static foreach (
v.x[i] = rng.uniform01;
}
unittest {
KdNode!2[] wp = [{[2, 3]}, {[5, 4]}, {[9, 6]},
{[4, 7]}, {[8, 1]}, {[7, 2]}];
KdNode!2 thisPt = {[9, 2]};
const(KdNode!2)* found = null;
double bestDist = 0;
size_t nVisited = 0;
root.nearest
writefln("WP tree:\n Searching for %s\n" ~
" Found %s, dist = %g\n Seen %d nodes.\n",
thisPt.x
}
unittest {
enum N = 1_000_000;
enum testRuns = 100_000;
auto bigTree = new KdNode!3[N];
auto rng = 1.Xorshift;
foreach (ref node; bigTree)
randPt(node, rng);
KdNode!3 thisPt;
randPt(thisPt, rng);
const(KdNode!3)* found = null;
double bestDist = 0;
size_t nVisited = 0;
root.nearest
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;
Line 721 ⟶ 719:
sum += nVisited;
}
writefln("\nBig tree:\n Visited %d nodes for %d random " ~
"searches (%.2f per lookup).",
sum, testRuns, sum / double(testRuns));
}
▲}</lang>
{{out}}
<pre>WP tree:
| |||