K-d tree: Difference between revisions
Content added Content deleted
(J: fix a bug in node visit counting, and redo timings) |
(bugfix: need to test distance from point to dividing plane to decide if checking other side is relevant) |
||
Line 830:
create=:3 :0
Axis=: ({:$y)|<.2^.#y
if. 3>#y do.
Leaf=:1
Points=: y
Line 836 ⟶ 837:
Leaf=:0
data=. y /: Axis|."1 y
n=.
Points=: ,:n{data
Left=: conew&'kdnode' n{.data
Line 848 ⟶ 849:
_ 0 nearest y
:
n=.' ',~":N_base_=:N_base_+1
dists=. Points distance y
ndx=. (i. <./) dists
Line 860 ⟶ 861:
if. d0=0 do. 0;y return. end.
if. 0={./:Axis|."1 y,Points do.
'dist pnt'=.
if. dist > d0 do.
if. dist > (Mask#pnt) distance Mask#,Points do.
'dist2 pnt2'=. d0 nearest__Right y
if. dist2 < dist do. dist2;pnt2 return. end.
end.
end.
else.
'dist pnt'=.
if. dist > d0 do
if. dist > (Mask#pnt) distance Mask#,Points do.
'dist2 pnt2'=. d0 nearest__Left y
if. dist2 < dist do. dist2;pnt2 return. end.
end.
end.
end.
Line 893 ⟶ 902:
nearest__tree 9 2
┌───────┬─┬───┐
│1.
└───────┴─┴───┘</lang>
Line 902 ⟶ 911:
<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 940 ⟶ 949:
<lang J> tree=:conew&'kdtree' (2,3), (5,4), (9,6), (4,7), (8,1),: (7,2)
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'
3.62419e_5 6016</lang>
The kdtree implementation is
<lang J> tree=:conew&'kdtree' dataset
timespacex 'nearest__tree pnt'
0.00141408 45312
build0 dataset
timespacex 'nearest0 pnt'
0.00140702 22144</lang>
On the bigger dataset, the kdtree implementation is
See also: [[wp:KISS_principle]]
| |||