[Numpy-discussion] Large symmetrical matrix

Hoyt Koepke hoytak@gmail....
Wed Jun 11 15:26:34 CDT 2008


> The factor of two memory hit is not really the problem, it is the scaling
> O(N^2) which is the limitation

Have you thought about using kd-trees or similar structures?  If you
are only concerned about the minimum distances between two points,
that is the ideal data structure.  It would reduce your running time /
memory usage for generating / using the data from O(n^2) to O(n log
n), with a O(log n) lookup time for the closest distance to each
point.

Without doing something like that, looking at the distance between
each pair of points is \Omega(n^2).

--Hoyt

-- 
+++++++++++++++++++++++++++++++++++
Hoyt Koepke
UBC Department of Computer Science
http://www.cs.ubc.ca/~hoytak/
hoytak@gmail.com
+++++++++++++++++++++++++++++++++++


More information about the Numpy-discussion mailing list