iterating in reverse

[Chad Netzer]

On Thursday 16 January 2003 17:30, Carl Banks wrote:
> Chad Netzer wrote:
> > FWIW. list.reverse() is often not too bad since it only has to do
> > the work of reversing the list indices in memory, not copying the
> > actual objects themselves.  Iterating backwards does save an O(N)
> > operation, but for small lists, list.reverse() is likely faster.
>
> Iterating a list is an O(N) operation itself.  If .reverse() is
> faster for a small list, it should also be faster for a large list.

Well, true of course.  I was thinking there might be possible cache 
poisoning effects that would occur for large lists (since a 
copy/reverse/iteration implies three linear passes though the indices, 
versus 1 for reverse_iter()). 

> The only problem with .reverse() is you might want to keep the
> unreversed list around.

Yeah, so you may need to do a copy/reverse  or a reverse/reverse, to 
keep the original list.

I wrote a quick, crude benchmark, and it seems that list.reverse() is 
always a speed win over reverse_iter.  It would be interesting to 
compare the other methods suggested in this thread.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
from __future__ import generators
from __future__ import division

import time

def reverse_iter( seq ):
    i = 0
    n = len( seq )
    while i < n:
        j = -(i + 1)
        yield seq[ j ]
        i += 1

if __name__ == '__main__':
    N = 100

    seq = range(1,10,2)
    seq += range( 10, 100, 20 )
    seq += range( 100, 1000, 200 )
    seq += range( 1000, 10000, 2000 )
    seq += range( 10000, 100000, 20000 )

    print "t1: avg time for list reversal, t2: avg time for reverse 
iterator"
    for list_len in seq:
        l = [None] * list_len

        start_time = time.time()
        for i in range( N ):
            g = l[:]
            g.reverse()
            for j in g:
                pass
        end_time = time.time()
        reverse_list_time = (end_time - start_time) / N

        start_time = time.time()
        for i in range( N ):
            for j in reverse_iter( l ):
                pass
        end_time = time.time()
        reverse_iter_time = (end_time - start_time) / N
        ratio = reverse_iter_time / reverse_list_time

        s = "list len %7d: t1 %f,\tt2 %f,\tratio %f"
        print s %(list_len, reverse_list_time, reverse_iter_time, ratio)

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
$ python reverse_iter_test.py
t1: avg time for list reversal, t2: avg time for reverse iterator
list len       1: t1 0.000007,	t2 0.000009,	ratio 1.368592
list len       3: t1 0.000008,	t2 0.000014,	ratio 1.787987
list len       5: t1 0.000009,	t2 0.000019,	ratio 2.232744
list len       7: t1 0.000010,	t2 0.000046,	ratio 4.472117
list len       9: t1 0.000145,	t2 0.000029,	ratio 0.199969
list len      10: t1 0.000011,	t2 0.000032,	ratio 2.855135
list len      30: t1 0.000022,	t2 0.000080,	ratio 3.729080
list len      50: t1 0.000030,	t2 0.000130,	ratio 4.276323
list len      70: t1 0.000040,	t2 0.000180,	ratio 4.500167
list len      90: t1 0.000049,	t2 0.000230,	ratio 4.727376
list len     100: t1 0.000054,	t2 0.000253,	ratio 4.700716
list len     300: t1 0.000151,	t2 0.000756,	ratio 5.016149
list len     500: t1 0.000241,	t2 0.001348,	ratio 5.591028
list len     700: t1 0.000336,	t2 0.001767,	ratio 5.254217
list len     900: t1 0.000430,	t2 0.002273,	ratio 5.287656
list len    1000: t1 0.000477,	t2 0.002526,	ratio 5.299844
list len    3000: t1 0.001417,	t2 0.007579,	ratio 5.347900
list len    5000: t1 0.002358,	t2 0.012665,	ratio 5.370679
list len    7000: t1 0.003344,	t2 0.018058,	ratio 5.400407
list len    9000: t1 0.004256,	t2 0.022734,	ratio 5.341331


-- 
Bay Area Python Interest Group - http://www.baypiggies.net/

Chad Netzer