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