Tim Chase:
for i in xrange(len(IN)):
for j in xrange(i+1, len(IN)):
if IN[i].coordinates == IN[j].coordinates:
SN.append(IN[i].label)
If my college algorithms memory serves me sufficiently, this
reduces your O(N^2) to O(N log N) which will garner you some
decent time savings.
That's O(n^2) still, it's just half matrix, a triangle.
Ah, good catch as I'm thinking about it more, you're right...it's
O((N^2)/2) which is just O(N^2). Sigh. I'm not awake enough
yet. However, dividing the time by 2 (from 15hr to 7.5hr) is
still a significant savings in my book :)
However, if list-comprehensions are faster as well, you might be
able to do something like
SN = [d.label
for (i,d) in enumerate(IN)
for j in xrange(i+1, len(IN))
if d.coordinates == IN[j].coordinates
]
or the slightly more verbose (but closer to my original code) version
SN = [IN[i].label
for i in xrange(len(IN))
for j in xrange(i+1, len(IN))
if IN[i].coordinates == IN[j].coordinates
]
To the OP: As always, throw some timing code on the various
samples you get back from the list and see what works for you.
-tkc
--
http://mail.python.org/mailman/listinfo/python-list
