Benchmarking KDTree

KDTree should be fast for searches, although not necessarily fast for creation/addition/deletion. 

/////////// Construction

(

// Change these two parameters if you like:

~dims = 3;

~num = 10000;

// Test either with uniformly-distributed data or quasi-gaussian data - will get different performance

~rand = {|n| n.rand };

~rand = {|n| n.sum3rand };

~halffillsize = (~num * 2).pow(1/~dims).floor.asInteger;

~array = { {~rand.value(~halffillsize)}.dup(~dims) }.dup(~num);

"KDTree construction:".postln;

bench{~tree = KDTree(~array)};

""

);

////////// Exact-match search

// Note: this exact-match finding is only faster than Array for large dataset sizes (e.g. 100000, I find).

// But the other types of search (e.g. nearest neighbour) are very fast, compared to 

// the brute-force approach that would have to be used on a flat array.

(

"100 finds using array:".postln;

bench{

100.do{

~array.indexOf({~halffillsize.rand}.dup(~dims));

};

};

"100 finds using kd-tree:".postln;

bench{

100.do{

~tree.find({~halffillsize.rand}.dup(~dims));

};

};

""

);

/////////// general nearest neighbour to arbitrary spatial point

(

"Nearest neighbour query time estimated average:".postln;

(""++(bench({

100.do{

~tree.nearest({~halffillsize.rand}.dup(~dims));

}

}, false)/100) + "seconds").postln;

""

);

//////////// nearest neighbour to a node - this test will TAKE A WHILE for large trees since it runs once on each node

(

"Nearest neighbour to each node, queried separately - query time average:".postln;

(""++(bench({

~tree.collect{ |node|

node.nearestToNode

}

}, true)/~tree.size) + "seconds per node").postln;

""

);

//////////// All Nearest Neighbours. Can theoretically re-use data to optimise re the separate query above.

(

"All Nearest Neighbours (single call, should ideally be faster due to ability to re-use data):".postln;

(""++(bench({

~tree.allNearest

}, true)/~tree.size) + "seconds per node (but note: individual queries don't exist)").postln;

""

);