Re: [pygame] Numeric optimization advice

[John Eikenberry <jae@zhar.net>]

After reading your comments and looking over the code again I can see
the source(s) of your confusion. I trimmed down the code to post the the
lists, to try to make it more compact and understandable. Seems I didn't
get it quite right. :P

Pete Shinners wrote:

> John Eikenberry wrote:
> >            # spread the influence
> >            # diamond_h
> >            neighbors = _shift_up(weightmap)/factor
> >            neighbors += _shift_left(weightmap)/factor
> >            neighbors += _shift_right(weightmap)/factor
> >            neighbors += _shift_down(weightmap)/factor
> >            neighbors += _shift_hex_up(weightmap)/factor
> >            neighbors += _shift_hex_down(weightmap)/factor
> 
> this is certainly the core of your work. the first thing you could easily 
> do is remove all the "/factor" and add a final line "neighbors /= factor" 
> or perhaps slightly better might be "neighbors *= (1/factor)"

Score one for Pete. This works with one small change:

one = array(1.).astype(Float16)
        ...
        neighbors *= (one/factor)

Just using 1/factor results in an type error (TypeError: return array
has incorrect type). I've found when working with Numeric that
consistent types is important to avoiding these types of errors. I
encountered my share of them while figuring this out and have just taken
to always keeping my types consistent.

> the other thing would be the absolute rediculous number of calls that must 
> be going to _shift_up and _shift_down.
> 
> def shift_up(cells):
>     return concatenate((cells[1:], cells[-1:]*edge_mod))
> 
> this looks pretty rough to me. the "concantenate" cannot make a 'clean 
> reference' of the array, so it must make a copy of all the data. the 
> *edge_mod must also make a copy of the last column.
> 
> i'm actually a little confused what  the edge_mod is for exactly. is it 
> really needed? the edge_mod will require we make a copy of something, here 
> is a potential quicker plan? i'm also a little confused here since the 
> passed in "hex_map" is unused, and all the action only takes place on the 
> arrays of "zeros".

The edge_mod is used to deal with the edge of the map. As the influence
map works by shifting the map and suming the values, I needed a way to
deal with map edges. I found that by taking the product of the values
from the row/column next to the edge of the map and a modifier I could
get a very close proximation to the values in the interior of the map.
This is a recent change, previously I had just used a zeros array for
off the edge of the map. But then the values of the hexes near the edge
of the map were lower than they should have been. It's not a necessary
part of the algorithm... more of a tweak.

The hex_map is the civil map object. It holds of a list of lists of all
the hexes on the map along with other info (including the map size). I
only need the map size here and could probably get rid of the reference.

> class InfluenceMap:
> 	def __init__(self, hex_map):
> 		self.hex_map = hex_map
> 		self.temp_map = zeros(hex_map.size, Float16)
> 		self.temp_up = self.temp_map[2:,1:1]
> 		self.temp_down = self.temp_map[:-2,1:1]
> 		self.temp_left = self.temp_map[1:1,2:]
> 		self.temp_right = self.temp_map[1:1,:-2]
> 		self.temp_hexup = self.temp_map[2:,2:]
> 		self.temp_hexdown = self.temp_map[:-2,:-2]
> 			
> 
> 	def step(self, iterations):
> 		edge_mod = 0.66
> 		centermap = self.hex_map[1:1,1:1]
> 		for x in range(iterations):
> 			self.temp_map[:] = self.hex_map
> 			self.temp_map[1] *= edge_mod
> 			self.temp_map[-1] *= edge_mod
> 			self.temp_map[:,1] *= edge_mod
> 			self.temp_map[:,-1] *= edge_mod
> 			centermap = self.temp_up
> 			centermap += self.temp_down
>                       centermap += self.temp_left
> 			centermap += self.temp_right
> 			centermap += self.temp_hexup
> 			centermap += self.temp_hexdown
> 			centermap *= 1.0 / 6.0
> 
> 
> now, using my quick email logic, the "hexup" and "hexdown" logic may be 
> incorrect. if so you'll get best results by working on the even/odd rows 
> each at a time, instead of like your shift_hex_up function that makes a 
> copy of the entire array.

As per your warning I'm still trying to get this working. I've made a
little progress (haven't had much time to work on it) and am currently
figuring out why I get "ValueError: frames are not aligned" for the
line:    
        centermap += self.temp_left

I'm going to keep trying as this would eliminate a ton of array copies.

> there should also be no need for clamping the results from 'overheated' 
> values here? since we are averaging all the surrounding cells, no value can 
> become 'hotter' than any of its neighbors.

I'm assuming your referring to masking the unit value map (constmap in
the code). I'm glad you were able to pick up on it as I never assign it
a real value (trimmed that part out... opps).

Anyways. It's not really needed for curtailing overheating as the
comment suggests, that's a leftover from a previous incarnation and the
factoring really keeps that in check. It is used now to maintain the
value of the unit hexes through the iterations. Otherwise the map
quickly levels off at low values. Though this can also be adjusted with
larger unit values. [testing]. Yeah, higher base values for units have a
similar effect, without the mask. So it can probably go.

> anyways, beware my code here. i just typed it into the email program, and 
> it may not work, or worse, muhaha

Well, it didn't cause my cpu to burst into flames or anything so I'll
count my blessings. ;)

Thanks for all the tips. I really appreciate the your taking the time to
help. I'll let you know how things go.

-- 

John Eikenberry
[jae@zhar.net - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org