[Python-bugs-list] [ python-Feature Requests-728304 ] reverse form of enumeration

[SourceForge.net]

Feature Requests item #728304, was opened at 2003-04-27 01:30
Message generated for change (Comment added) made by rhettinger
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=355470&aid=728304&group_id=5470

Category: Python Library
Group: None
>Status: Closed
>Resolution: Rejected
Priority: 5
Submitted By: Douglas Napoleone (derivin)
Assigned to: Nobody/Anonymous (nobody)
Summary: reverse form of enumeration

Initial Comment:
I love the new enumeration builtin. Before it was put in I 
had my own version of the functionality as many did 
using xrange and zip.

I also used an extension that would give a reverse of 
what enumeration returns (in behavior at least)

enumeration(list)
returns an xrange like itterator that behaves like:
( (0, list[0]), (1, list(1)), ...)

my old code looked like:

def old_enumeration( argList):
_ return zip(range(len(argList)), argList)

def revenum( argList ):
_ temp = old_enumeration( argList)
_ temp.reverse()
_ return temp


obviously this is really slow for really long lists and 
tuples

these structures would be used for looping 90% of the 
time. One of my fav's:
matches = []
for ind, val in revenum(aList):
_ if test(val): matches.append(aList.pop(ind))

am I the only person wanting an effecient reverse 
enumeration??

(NOTE: currently if the list is really long I use:
for ind in xrange(len(aList) - 1, -1, -1):
create two new lists, then delete the old one.
the additional time for pop() is non trivial on a list of 
50Mil entries and memory isnt much of a concern as 
time for me. A reverse enumeration would be much 
clearer to read IMO).



----------------------------------------------------------------------

>Comment By: Raymond Hettinger (rhettinger)
Date: 2003-05-12 12:47

Message:
Logged In: YES 
user_id=80475

You were on target with your question about whether 
you're the only one wanting C coded reverse enumeration.  
The use case for going in reverse *and* needing the indices 
is rare.  

When needed, it can be cleanly coded in python in just a 
few lines.  You get reasonable performance with your 
existing code (old_enumeration and revenum). 

Using a generator and an index variable gives an even 
cleaner, memory efficient alternative.  That latter 
approach can be brought to near C speed using just two 
lines from Psyco.

On a separate note, the matches example code suffers 
from O(n^2) run-time because alist.pop(i) has to slide-
back every element after i.  You do *much* better with:  
matches=filter(test, alist) and then alist=filter(inversetest, 
alist).  If test() is expensive, then run a single loop that 
adds each element to either matches or newlist.

Also, if you have 50 Mil entries in your lists (which I find 
surprising with 200Mb for the list of pointers alone and 
much more memory for the objects being pointed to), 
then consider using either Numeric or Pysco to get a 
speed boost.  Failing that, the application may warrant a 
single C function in the time critical section.  Unless both 
the objects and test() are very simple, I would be surprised 
to find the loop overhead to dominate running time.

Also, consider using Py2.3's new itertools module.  You 
ought to get near C speed (as fast as enumerate) from:
  itertools.izip(xrange(len(aList) - 1, -1, -1), alist)

----------------------------------------------------------------------

Comment By: Douglas Napoleone (derivin)
Date: 2003-04-27 21:52

Message:
Logged In: YES 
user_id=541557

At issue is the speed of list operations on excessivly large 
lists. 

a = list(xrange(5000000))    - 1 second
a = list(xrange(50000000))  - 4 min

list(enumerate(a))[::-1]

is 3 list operations... or 12min (actually took 25min for me in 
a test but other processes were running. NOTE: the list
(xrange(#)) time is NOT included in this.)

enumerate(a, reverse=True)  - 15seconds  (took the code for 
enumerate and made my own pyd)

this does not include the time that it would take to make all 
the calls to the enumerate's next() method; obviously.

in the end, quarter of a min, or quarter of an hour. What 
would you use?



----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-04-27 12:17

Message:
Logged In: YES 
user_id=80475

This runs pretty fast:

     list(enumerate(data))[::-1]

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=355470&aid=728304&group_id=5470