163 lines
38 KiB
Plaintext
163 lines
38 KiB
Plaintext
(phixonline)-->
|
|
<span style="color: #000080;font-style:italic;">-- demo\rosetta\kd_tree.exw</span>
|
|
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
|
|
<span style="color: #008080;">enum</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">,</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">RIGHT</span> <span style="color: #000080;font-style:italic;">-- (keeping the IDX on each node too would not be a bad idea..)
|
|
-- (the code below deduces it from the (unbalanced) tree depth)</span>
|
|
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">kd_nodes</span> <span style="color: #000080;font-style:italic;">-- nb probably not best coding style</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">sqdist</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">),</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">procedure</span> <span style="color: #000000;">swap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">],</span><span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">],</span><span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]}</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">find_median</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">first</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">last</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">first</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">==</span><span style="color: #000000;">first</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">first</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">stor</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">md</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">first</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">last</span><span style="color: #0000FF;">-</span><span style="color: #000000;">first</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">atom</span> <span style="color: #000000;">pivot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">md</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">][</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span>
|
|
|
|
<span style="color: #000000;">swap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">md</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">stor</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">first</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">first</span> <span style="color: #008080;">to</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">][</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">pivot</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">stor</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">swap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">stor</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #000000;">stor</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #000000;">swap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stor</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
|
|
|
|
<span style="color: #000080;font-style:italic;">/* median has duplicate values */</span>
|
|
<span style="color: #004080;">atom</span> <span style="color: #000000;">sx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stor</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">][</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">],</span>
|
|
<span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">md</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">][</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">sx</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">mx</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">stor</span><span style="color: #0000FF;">></span><span style="color: #000000;">md</span> <span style="color: #008080;">then</span> <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stor</span> <span style="color: #008080;">else</span> <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stor</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #000000;">md</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">make_tree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dim</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">kd_nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #000000;">0</span><span style="color: #0000FF;">:</span><span style="color: #000000;">find_median</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">))</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dim</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">])!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (once)</span>
|
|
<span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">],</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (add l/r slots)</span>
|
|
<span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dim</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">+</span><span style="color: #000000;">len</span><span style="color: #0000FF;">-(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dim</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #000000;">n</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">visited</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">best</span>
|
|
<span style="color: #004080;">atom</span> <span style="color: #000000;">best_dist</span>
|
|
|
|
<span style="color: #008080;">procedure</span> <span style="color: #000000;">nearest</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">nd</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dim</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sqdist</span><span style="color: #0000FF;">(</span><span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">],</span><span style="color: #000000;">nd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]),</span>
|
|
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">nd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
|
|
<span style="color: #000000;">dx2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">;</span>
|
|
|
|
<span style="color: #000000;">visited</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
|
|
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">best</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">best_dist</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">best_dist</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">;</span>
|
|
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">;</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
|
|
<span style="color: #000080;font-style:italic;">/* if chance of exact match is high */</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">best_dist</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
|
|
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dim</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">][</span><span style="color: #000000;">LEFT</span><span style="color: #0000FF;">..</span><span style="color: #000000;">RIGHT</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #000000;">nearest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dim</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">dx2</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">best_dist</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #000000;">nearest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dim</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">rand_pt</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">sq_rnd</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}})</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">make_3D</span><span style="color: #0000FF;">()</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,{{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">}})</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #000080;font-style:italic;">// aside: shave a little off under pwa/p2js, but 1e6 build still takes ~20s</span>
|
|
<span style="color: #008080;">constant</span> <span style="color: #000000;">test_runs</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">10_000</span><span style="color: #0000FF;">:</span><span style="color: #000000;">100_000</span><span style="color: #0000FF;">)</span>
|
|
|
|
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">id</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">test_node</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">show_average_behaviour</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">dim</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]),</span>
|
|
<span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dim</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
|
|
<span style="color: #000000;">visited</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
|
|
<span style="color: #000000;">nearest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">test_node</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dim</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n>> %s tree\nsearching for %v\nfound %v dist %g\nseen %d nodes\n"</span><span style="color: #0000FF;">,</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">id</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">test_node</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">kd_nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">best</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">],</span> <span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">best_dist</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">visited</span><span style="color: #0000FF;">})</span>
|
|
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">show_average_behaviour</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000080;font-style:italic;">--
|
|
-- search many random points to see average behavior.
|
|
--
|
|
-- tree size vs avg nodes visited:
|
|
-- 10 ~ 7
|
|
-- 100 ~ 16.5
|
|
-- 1000 ~ 25.5
|
|
-- 10000 ~ 32.8
|
|
-- 100000 ~ 38.3
|
|
-- 1000000 ~ 42.6
|
|
-- 10000000 ~ 46.7
|
|
--</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">test_runs</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
|
|
<span style="color: #000000;">visited</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
|
|
<span style="color: #000000;">test_node</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rand_pt</span><span style="color: #0000FF;">()</span>
|
|
<span style="color: #000000;">nearest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">test_node</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">total</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">visited</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"average behaviour: "</span><span style="color: #0000FF;">&</span>
|
|
<span style="color: #008000;">"visited %d nodes for %,d random findings (%f per lookup)\n"</span><span style="color: #0000FF;">,</span>
|
|
<span style="color: #0000FF;">{</span><span style="color: #000000;">total</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">test_runs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">total</span><span style="color: #0000FF;">/</span><span style="color: #000000;">test_runs</span><span style="color: #0000FF;">});</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
|
|
|
|
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wp</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">}},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">}},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">}},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">}},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">}}},</span>
|
|
<span style="color: #000000;">test_node</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
|
|
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"WP"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">test_node</span><span style="color: #0000FF;">)</span>
|
|
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cube</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_3D</span><span style="color: #0000FF;">()</span>
|
|
<span style="color: #000000;">test_node</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rand_pt</span><span style="color: #0000FF;">(),</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3D"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cube</span><span style="color: #0000FF;">,</span><span style="color: #000000;">test_node</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
|
|
|
|
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1_000_000</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">million</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span> <span style="color: #000000;">million</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rand_pt</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #000000;">test_node</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rand_pt</span><span style="color: #0000FF;">()</span>
|
|
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Million"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">million</span><span style="color: #0000FF;">,</span><span style="color: #000000;">test_node</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
|
|
|
|
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #0000FF;">?</span><span style="color: #008000;">"done"</span>
|
|
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<!--
|