[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] Fastest (x,y) distance calculation




On Wednesday, Sep 10, 2003, at 17:26 America/New_York, Nicola Larosa wrote:
###
class Game:
...
def get_nearest_temple(self, pos):
posx = pos[0]
posy = pos[1]
temples = self.temples
distances = []
for temple in temples:
distx = posx - temple.rect.centerx
disty = posy - temple.rect.centery
distances.append((distx * distx + disty * disty, temple))
return min(distances)[1]
...

Of course the best optimization would be a better algorithm. If you have a
really huge number of "temples", you may want to feed and care for more
complex data structures, like BSP (Binary Space Partition) trees, or something.
Yeah, a better and more complex algorithm will surely help, however doing the distance calculation and min in parallel should be measurably faster (esp. in psyco or pyrex).. this also has the added benefit at the super low level (from psyco or pyrex) that it does a little more calculation between memory accesses, so it's probably less often waiting due to access penalties.

import sys
class Game:
...
def get_nearest_temple(self, pos):
# assuming pos has two elements, this inline unpack should be faster because I think it has its own bytecode
posx, posy = pos
temples = self.temples
mindistance = sys.maxint
mintemple = None
for temple in temples:
# the same inline unpack might help if temple.rect has a center tuple..
# i.e. centerx, centery = temple.rect.center
# it would also save you 2 object attribute lookups
distx = posx - temple.rect.centerx
disty = posy - temple.rect.centery
dist = (distx * distx) + (disty * disty)
if dist < mindistance:
mindistance = dist
mintemple = temple
return mintemple
...

this code should surely be faster, _definitely_ will be under something like pyrex or psyco. assuming N is len(temples), the additional work done by the quoted code (compared to mine) is:
creation and garbage collection of 1 list and N tuples (at the expensive of two local variable object references, which are pathetically cheap)
N object attribute lookups of distances.append (could easily be aliased as a local, though)
N calls to distances.append (calling stuff is particularly expensive in python)
probably a few list resizes behind the scenes
an iteration over N distances (the min calculation, which is partially in fast C code)
that has to rip open the first one or two elements of N tuples

-bob