Re: [pygame] y-Sorted RenderGroup

["Mike C. Fletcher" <mcfletch@rogers.com>]

If there's no reason to keep the sprites in a dict (sorry, haven't had 
time to look at the code, just going by Frank's comments), then using a 
bisect-based approach can be very fast.

Basically, you store the data in a sorted-order list and use the bisect 
module to add new items (which maintains sort order).  If you really do 
need the objects in a dict, you can do the work of pushing them into 
both dict and list and deleting them when adding/removing items.  The 
key is that you store the objects in the list as (sortParam, object), so 
that the standard Python sorting and comparison automatically works for 
the items.

The (sortParam,object) storage means you need to access objects as 
list[item][1] (or wrap that in an accessor method), but compared to 
calling a Python function (lambda or not) huge numbers of times (which 
is pretty darn slow) to do a sort, it should be much faster.

For the common case (wanting all objects), you can use
	map( operator.getitem, sortedlist, [1]*len(sortedlist))
to get all second items (the objects in sorted order) very fast.

Asides:
	cmp is a built-in, very fast.

	list.sort using a custom function is often much slower than building a 
temporary list of (sortValue, object) tuples, using default sort, then 
doing the operator.getitem (also a built-in) trick above to get the results.

	for changed values, simply remove the sprite, then re-insert with bisect. 
  There is overhead in finding the entry in the sorted list (use 
bisect.bisect( previousY, object) to get the index).  That means your 
sprite class needs to know to call the group with both previous and new 
y values, of course.

HTH,
Mike

Frank Raiser wrote:
> On Tue, Jun 04, 2002 at 10:52:02AM -0700, steve wrote:
...
>>   As you can see, I sort when I paint the sprites, because Python's 
>>dictionaries return their items in random order, sorting the dictionary 
>>would be pointless (you can't anyways).  After I sort, I paint the 
>>sorted list of sprites instead of spritedict.items(), #3 below.  I use 
>>my own sorting routine called y_sort(a, b).
...
>>   My question is, is creating an iternal list inside draw(), "y" in #1 
>>below, the right way of doing this?  Since draw is called so frequently, 
>>should I worry about garbage, and make this sorted list a class variable 
>>(self.y)?  Is there a better way of doing this within the existing 
>>Sprite classes, or am I on track here?
> 
> 
> The problem with the class variable is to keep it up2date when you change
> the group. I've tested a little (very little actually :) with your script
> and found that it doesn't make much of a difference unless you expand the
> group to several hundred sprites. And even then the difference is almost
> neglectable. I wouldn't say it's worth the effort of keeping the group
> updated.
> I'm not sure if you could get an improvement by keeping an internal flag
> for the sorting. As you sort all your sprites each time draw() is called
> this might be an overhead one could eliminate by keeping a flag that
> triggers the sorting only when a sprite has actually moved in the y
> direction. But then again I don't know how the sort routine works and how
> much work is actually done in case of an already sorted list. I think it'll
> be just another minor improvement only relevant to a group with hundreds
> of sprites.
> 
> hth,


-- 
_______________________________________
   Mike C. Fletcher
   http://members.rogers.com/mcfletch/


____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org