K-d tree: Difference between revisions

Also there are algorithms for inserting, deleting, and balancing k-d trees.

These are also not required for the task.

 

=={{header|C}}==

Using a Quickselectesque median algorithm. Compared to unbalanced trees (random insertion), it takes slightly longer (maybe half a second or so) to construct a million-node tree, though average look up visits about 1/3 fewer nodes.

 

#include <stdio.h>

}

 

{{out}}

<pre>>> WP tree

=={{header|C++}}==

This code is based on the C version. A significant difference is the use of the standard library function nth_element, which replaces the find_median function in the C version.

#include <array>

#include <cmath>

return nullptr;

size_t n = begin + (end - begin)/2;

index = (index + 1) % dimensions;

nodes_[n].left_ = make_tree(begin, n, index);

nodes_.reserve(n);

for (size_t i = 0; i < n; ++i)

root_ = make_tree(0, nodes_.size(), 0);

}

}

return 0;

 

{{out}}

=={{header|Common Lisp}}==

The 3D data set is the set of coordinates from (0,0,0) to (9,9,9) (ie. uniformly distributed), while the ordinates of the random target are positive real < 10.

 

 

 

 

 

 

 

 

{{out}}

{{trans|Go}}

Points are values, the code is templated on the the dimensionality of the points and the floating point type of the coordinate. Instead of sorting it uses the faster topN, that partitions the points array in two halves around their median.

// "An introductory tutorial on kd-trees" by Andrew W. Moore,

// Carnegie Mellon University, PDF accessed from:

writefln("Visited an average of %0.2f nodes on %d searches " ~

"in %d ms.", visited / double(M), M, sw.peek.msecs);

{{out|Output}} using the ldc2 compiler

<pre>Wikipedia example data:

{{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.

 

struct KdNode(size_t dim) {

sum, testRuns, sum / double(testRuns));

}

{{out}}

<pre>WP tree:

 

=={{header|Go}}==

// by Andrew W. Moore, Carnegie Mellon University, PDF accessed from

// http://www.autonlab.org/autonweb/14665

fmt.Println("distance: ", math.Sqrt(ssq))

fmt.Println("nodes visited: ", nv)

{{out}}

<pre>

=={{header|Haskell}}==

There is a space leak when creating the trees which will lead to terrible performance on massive trees. This can probably be quelled with strictness annotations.

import Data.List (sortBy, genericLength, minimumBy)

import Data.Ord (comparing)

printResults randSearch randNearest tuple3D

putStrLn "Confirm naive nearest:"

{{out}}

<pre>Wikipedia example:

As a general rule, tree algorithms are a bad idea in J. That said, here's an implementation:

 

create=:3 :0

Axis=: ({:$y)|<.2^.#y

'dist point'=. nearest__root y

dist;N_base_;point

 

And here's example use:

 

nearest__tree 9 2

┌───────┬─┬───┐

│1.41421│4│8 1│

 

The first box is distance from argument point to selected point. The second box is the number of nodes visited. The third box is the selected point.

Here's the bigger problem:

 

nearest__tree pnt

┌─────────┬──┬──────────────────────────┐

│0.0387914│12│0.978082 0.767632 0.392523│

 

So, why are trees "generally a bad idea in J"?

Well, let's compare the above implementation to a brute force implementation for time. Here's a "visit all nodes" implementation. It should give us the same kinds of results but we will claim that each candidate point is a node so we'll be visiting a lot more "nodes":

 

data=: y

)

nearest=. data {~ (i. <./) |data distance y

(nearest distance y);(#data);nearest

 

Here's the numbers we get:

 

nearest0 9 2

┌───────┬─┬───┐

┌─────────┬────┬──────────────────────────┐

│0.0387914│1000│0.978082 0.767632 0.392523│

 

But what about timing?

 

timespacex 'nearest__tree 9 2'

0.000487181 19328

build0 (2,3), (5,4), (9,6), (4,7), (8,1),: (7,2)

timespacex 'nearest0 9 2'

 

The kdtree implementation is over ten times slower than the brute force implementation for this small dataset. How about the bigger dataset?

 

timespacex 'nearest__tree pnt'

0.00141408 45312

build0 dataset

timespacex 'nearest0 pnt'

 

On the bigger dataset, the kdtree implementation is about the same speed as the brute force implementation.

Based on the C++ solution.

File KdTree.java:

 

public class KdTree {

}

}

File QuickSelect.java:

 

//

return left + random.nextInt(right - left + 1);

}

File KdTreeTest.java:

 

public class KdTreeTest {

System.out.println("nodes visited: " + tree.visited());

}

 

{{out}}

distance: 0.004361560347252592

nodes visited: 34

</pre>

 

=={{header|Julia}}==

 

using NearestNeighbors

" at distance $(dist[1]).")

NearestNeighbors.print_stats()

{{out}}

<pre>

=={{header|Kotlin}}==

{{trans|Go}}

 

import java.util.Random

kd = KdTree(randomPts(3, 400_000), hr)

showNearest("400,000 random 3D points", kd, randomPt(3))

 

Sample output:

</pre>

 

 

 

 

 

 

 

 

 

 

 

{{out}}

<pre>

seen 43 nodes

average behaviour: visited 4267089 nodes for 100,000 random findings (42.670890 per lookup)

</pre>

 

=={{header|Python}}==

{{trans|D}}

from operator import itemgetter

from collections import namedtuple

 

N = 400000

kd2 = KdTree(random_points(3, N), Orthotope(P(0, 0, 0), P(1, 1, 1)))

text = lambda *parts: "".join(map(str, parts))

show_nearest(2, text("k-d tree with ", N,

" random 3D points (generation time: ",

t1-t0, "s)"),

{{out}}

<pre>Wikipedia example data:

=={{header|Racket}}==

The following code is optimized for readability.

#lang racket

 

n)]))

(nn 0 t (infinite-bb k)))

Tests:

(define (wikipedia-test)

(define t (kdtree 0 2 '(#(2 3) #(5 4) #(9 6) #(4 7) #(8 1) #(7 2))))

(test 3 1000)

(test 3 1000)

{{out}}

Wikipedia Test

Nearest neighbour to (9,2) is: #(8 1)

Control: 0.0018063471125121851

Visits: 39

 

=={{header|Raku}}==

(formerly Perl 6)

{{trans|Python}}

has $.d;

has $.split;

"k-d tree with $N random 3D points (generation time: {$t1 - $t0}s)",

$kd2, random_point(3));

{{out}}

<pre>Wikipedia example data:

Distance: 0.0340950700678338

Nodes visited: 23</pre>

 

=={{header|Scala}}==

This example works for sequences of Int, Double, etc, so it is non-minimal due to its type-safe Numeric parameterisation.

import Numeric._

 

def compare[T](a: Seq[T], b: Seq[T])(implicit num: Numeric[T]): Int =

a.zip(b).find(c => num.compare(c._1, c._2) != 0).map(c => num.compare(c._1, c._2)).getOrElse(0)

Task test:

def test[T](haystack: Seq[Seq[T]], needles: Seq[T]*)(implicit num: Numeric[T]) = {

println

assume(small.size == 27)

test(small, List(0, 0, 0), List(4, 5, 6))

{{out}}

<pre>KDNode(List(7, 2),Some(KDNode(List(5, 4),Some(KDNode(List(2, 3),None,None,0)),Some(KDNode(List(4, 7),None,None,0)),1)),Some(KDNode(List(9, 6),Some(KDNode(List(8, 1),None,None,0)),None,1)),0)

=={{header|Sidef}}==

{{trans|Raku}}

d,

split,

show_nearest(2,

"k-d tree with #{N} random 3D points (generation time: #{t1 - t0}s)",

{{out}}

<pre>

{{trans|Python}}

{{libheader|TclOO}}

 

oo::class create KDTree {

return [list $nearest $dist2 $nodesVisited]

}

Demonstration code:

puts ${heading}:

puts "Point: \[[join $point ,]\]"

set t [time {KDTree create kd2 [randomPoints 3 $N]}]

showNearest "k-d tree with $N random 3D points (generation time: [lindex $t 0] us)" kd2 [randomPoint 3]

{{out}}

<pre>

Nodes visited: 22

Search time: 289.894755 microseconds per iteration

</pre>

 

=={{header|zkl}}==

{{trans|Python}}

const NEAREST=0, DIST_SQD=1, NODES_VISITED=2;

class KdNode{

println("Nodes visited: ", n[NODES_VISITED], "\n");

}

kd1:=KdTree(T(T(2,3), T(5,4), T(9,6), T(4,7), T(8,1), T(7,2)),

Orthotope(List(0,0), List(10,10)));

{{out}}

<pre>

Nodes visited: 3

</pre>

fcn randomPoints(k,n){ // ( (p1,p2,,pk), ... n of them), p in [0..1]

n.pump(List,randomPoint.fp(k))

kd2:=KdTree(randomPoints(3,N), Orthotope(L(0,0,0), L(1,1,1)));

kd2.show_nearest(2, String("k-d tree with ", N," random 3D points"),

{{out}}

<pre>