[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