I'm not sure 20 dimensions is such a good idea, 2mb shared object file? that does sound excessive. Maybe instead, just do a reasonable number of dimensions and document how to increase the number for those who need more?<br>
<br><div class="gmail_quote">2009/3/21 Willi Richert <span dir="ltr"><<a href="mailto:w.richert@gmx.net">w.richert@gmx.net</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi,<br>
<br>
here they are.<br>
<br>
Regards,<br>
wr<br>
<div><div></div><div class="h5"><br>
On Freitag 20 März 2009 18:29:55 Willi Richert wrote:<br>
> Hi,<br>
><br>
> nice to hear. So stay tuned. I have just finished my template based swig<br>
> system that creates dim \in [1,20] for (int, float). I think that nobody<br>
> will use NN for more than 20 dimensions. Nevertheless the stuff then gets<br>
> quite big:<br>
><br>
> -rw-r--r-- 1 wr wr 756 2009-03-20 13:03 CMakeLists.txt<br>
> -rwxr-xr-x 1 wr wr 8754 2009-03-20 18:27 gen-swig-hpp.py<br>
> -rw-r--r-- 1 wr wr 54260 2009-03-20 18:27 kdtree.py<br>
> -rw-r--r-- 1 wr wr 4822 2009-03-20 18:27 kdtree.pyc<br>
> -rwxr-xr-x 1 wr wr 2119152 2009-03-20 18:28 _kdtree.so<br>
> -rw-r--r-- 1 wr wr 1328 2009-03-20 18:20 Makefile<br>
> -rw-r--r-- 1 wr wr 51603 2009-03-20 18:27 py-kdtree.hpp<br>
> -rw-r--r-- 1 wr wr 4054 2009-03-20 18:09 py-kdtree.hpp.tmpl<br>
> -rw-r--r-- 1 wr wr 130817 2009-03-20 18:27 py-kdtree.i<br>
> -rw-r--r-- 1 wr wr 380 2009-03-20 16:54 py-kdtree.i.tmpl<br>
> -rw-r--r-- 1 wr wr 2808 2009-03-20 13:03 py-kdtree_test.cpp<br>
> -rw-r--r-- 1 wr wr 15353 2009-03-20 18:13 py-kdtree_test.py<br>
> -rw-r--r-- 1 wr wr 18796 2009-03-20 18:17 py-kdtree_test.pyc<br>
> -rw-r--r-- 1 wr wr 1146062 2009-03-20 18:27 py-kdtree_wrap.cxx<br>
> -rw-r--r-- 1 wr wr 2386768 2009-03-20 18:28 py-kdtree_wrap.o<br>
><br>
><br>
><br>
> Regards,<br>
> wr<br>
><br>
> On Freitag 20 März 2009 18:24:16 Michal J. Gajda wrote:<br>
> > Hi,<br>
> ><br>
> > Indeed KD-tree data structure seems designed to use 'taxi-cab' metric<br>
> > instead of euclidean metric. That's why I used the same distance type as<br>
> > COORD_T in my patch.<br>
> > I work around this in my code by filtering points with euclidean distance<br>
> > afterwards.<br>
> ><br>
> > On the other hand I would love to beta test code for other dimensions<br>
> > than 1f, 3f, and 6f. For now I've got surprising result of 3f projection<br>
> > being faster for 20k points than 6f one. It may be because runtime grows<br>
> > as O(2^dim*log(n)). It may be that nobody has enough points to usefully<br>
> > exploit anything beyond 10D? --<br>
> > Best regards<br>
> > Michal<br>
> ><br>
> > -original message-<br>
> > Subject: Re: Python bindings for libkdtree: FIX of find_within_range...<br>
> > From: Paul Harris <<a href="mailto:paulharris@computer.org">paulharris@computer.org</a>><br>
> > Date: 20-03-2009 15:15<br>
> ><br>
> > Hrm.<br>
> ><br>
> > It may be the same reason that find_within_range() would return 4 as<br>
> > well.<br>
> ><br>
> > See email in archives, subject "Accuracy of libkdtree", 29 Jan 2009.<br>
> ><br>
> > This will need to be confirmed, I'll put it on my list to try and do<br>
> > asap. My theory is that it may only be checking in each dimension<br>
> > individually (a Manhattan distance check), and not doing a final<br>
> > Euclidean distance check. That would be my initial guess. I'm not sure<br>
> > what the logic would be behind that, maybe just speed. Anyway enough<br>
> > guess-work, next step is to confirm.<br>
> ><br>
> > If anyone wants to step up and figure out what is going on, and to have<br>
> > some input into what should be done about it, be my guest :)<br>
> ><br>
> > cheers,<br>
> > Paul<br>
> ><br>
> ><br>
> > 2009/3/20 Willi Richert <<a href="mailto:w.richert@gmx.net">w.richert@gmx.net</a>><br>
> ><br>
> > > Hi,<br>
> > ><br>
> > > alright, I can do that.<br>
> > ><br>
> > > However, I just found out that the range measurement is somehow<br>
> > > "illogic":<br>
> > ><br>
> > > def test_count_within_range(self):<br>
> > > nn = KDTree_2Int()<br>
> > ><br>
> > > for p in [(0,0), (1,0), (0,1), (1,1)]:<br>
> > > nn.add((p, id(p)))<br>
> > ><br>
> > > res = nn.count_within_range((0,0), 1.0)<br>
> > > self.assertEqual(3, res, "Counted %i points instead of %i"%(res,<br>
> > > 3))<br>
> > ><br>
> > > res = nn.count_within_range((0,0), 1.9)<br>
> > > self.assertEqual(4, res, "Counted %i points instead of<br>
> > > %i"%(res, 4))<br>
> > ><br>
> > ><br>
> > > libkdtree_new/python-bindings> python -m unittest<br>
> > > py-kdtree_test.KDTree_2IntTestCase.test_count_within_range<br>
> > > F<br>
> > > ======================================================================<br>
> > > FAIL: test_count_within_range (py-kdtree_test.KDTree_2IntTestCase)<br>
> > > ----------------------------------------------------------------------<br>
> > > Traceback (most recent call last):<br>
> > > File "py-kdtree_test.py", line 110, in test_count_within_range<br>
> > > self.assertEqual(3, res, "Counted %i points instead of %i"%(res,<br>
> > > 3)) AssertionError: Counted 4 points instead of 3<br>
> > ><br>
> > > ----------------------------------------------------------------------<br>
> > > Ran 1 test in 0.001s<br>
> > ><br>
> > ><br>
> > > Any suggestion why that is the case? The point (1,1) should not be<br>
> > > counted as its distance to (0,0) is sqrt(2)>1.0<br>
> > ><br>
> > > wr<br>
> > ><br>
> > > On Freitag 20 März 2009 11:56:16 Paul Harris wrote:<br>
> > > > Hi,<br>
> > > ><br>
> > > > 2009/3/20 Willi Richert <<a href="mailto:w.richert@gmx.net">w.richert@gmx.net</a>><br>
> > > ><br>
> > > > > One more thing: The current state of having one explicit template<br>
> > > > > realization<br>
> > > > > in the python/swig part annoys me a little bit. Some weeks ago<br>
> > > > > there<br>
> > ><br>
> > > was<br>
> > ><br>
> > > > > a discussion on the ML about whether or not dynamically supporting<br>
> > > > > the specification of the dimension and type. How is the status<br>
> > > > > here, Paul?<br>
> > ><br>
> > > If<br>
> > ><br>
> > > > > you<br>
> > > > > have decided against it, I will provide a python file that<br>
> > > > > generates<<br>
> > ><br>
> > > all<br>
> > ><br>
> > > > > the<br>
> > > > > stuff for float, double and int for dim \in [1, .., 20]. That will<br>
> > > > > ease the maintenance a lot. In the other case the situation for<br>
> > > > > the python bindings will be much smoother. But the performance will<br>
> > > > > maybe suffer. Can you shed some light on this decision, Paul?<br>
> > > ><br>
> > > > Its still on the list, but I haven't had the time to do anything on<br>
> > ><br>
> > > kdtree<br>
> > ><br>
> > > > for a while now, so i'm just focusing pushing through bug fixes to<br>
> > > > ensure that the results are correct.<br>
> > > ><br>
> > > > I would guess it'll be at least a month before I can do anything,<br>
> > > > unless<br>
> > ><br>
> > > I<br>
> > ><br>
> > > > manage to find a small random window of time where I can attack that<br>
> > ><br>
> > > issue.<br>
> > ><br>
> > > > Would it be too much to ask if you write the python file that<br>
> > > > generates<br>
> > ><br>
> > > all<br>
> > ><br>
> > > > the variants, and then we can do the dynamic version later? I don't<br>
> > > > know how much work that would involve, if its not too much then I<br>
> > > > would prefer if you set yourself up with a low-maintenance solution<br>
> > > > first.<br>
> > > ><br>
> > > > cheers,<br>
> > > > Paul<br>
><br>
</div></div>> _______________________________________________<br>
> libkdtree-devel mailing list<br>
> <a href="mailto:libkdtree-devel@lists.alioth.debian.org">libkdtree-devel@lists.alioth.debian.org</a><br>
> <a href="http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel</a><br>
<br>
</blockquote></div><br>