K-d tree: Difference between revisions
J: fix a bug in node visit counting, and redo timings
m (→{{header|J}}) |
(J: fix a bug in node visit counting, and redo timings) |
||
Line 827:
As a general rule, tree algorithms are a bad idea in J. That said, here's an implementation:
<lang J>coclass 'kdnode'▼
▲coclass 'kdnode'
create=:3 :0
Axis=: ({:$y)|<.2^.#y
Line 864 ⟶ 848:
_ 0 nearest y
:
dists=. Points distance y
ndx=. (i. <./) dists
Line 870 ⟶ 854:
range=. ndx { dists
if. Leaf do.
range
else.
d0=.
p0=. nearest
if. d0=0 do. 0
if. 0={./:Axis|."1 y,Points do.
'dist
if. dist > d0 do. d0
if. dist <
'dist2
if. dist2 < dist do. dist2
end.
else.
'dist
if. dist > d0 do. d0
if. dist < x do.
'dist2
if. dist2 < dist do. dist2
end.
end.
end.
dist
)
Line 899 ⟶ 883:
)
nearest=:3 :0
'dist point'=. nearest__root y
dist;N_base_;point
)</lang>
Line 907 ⟶ 893:
nearest__tree 9 2
┌───────┬─┬───┐
│1.
└───────┴─┴───┘</lang>
Line 915 ⟶ 901:
<lang J> tree=:conew&'kdtree' dataset=:?1000 3$0
nearest__tree pnt
┌─────────┬───┬──────────────────────────┐
│0.
└─────────┴───┴──────────────────────────┘</lang>
So, why are trees "generally a bad idea in J"?
Line 954 ⟶ 940:
<lang J> tree=:conew&'kdtree' (2,3), (5,4), (9,6), (4,7), (8,1),: (7,2)
timespacex 'nearest__tree 9 2'
0.000262674 15616
build0 (2,3), (5,4), (9,6), (4,7), (8,1),: (7,2)
timespacex 'nearest0 9 2'
3.62419e_5 6016</lang>
The kdtree implementation is almost
<lang J> tree=:conew&'kdtree' dataset
0.0169044 48128
build0 dataset
timespacex 'nearest0 pnt'
0.00140702 22144</lang>
On the bigger dataset, the kdtree implementation is
Exercise for the student: work out the cost of cpu time and decide how big of a dataset you need for the time it takes to implement the kdtree to pay back the investment of time needed to implement it. Also work out how many times the tree has to be accessed to more than cover the time needed to build it.
| |||