python challenge question (string manipulation)

[Felipe Almeida Lessa]

Em Qua, 2006-03-29 às 22:20 -0800, Caleb Hattingh escreveu:
> That is very succint.  Rewriting my shift function given earlier:
> 
> >>> import string
> >>> alpha = string.ascii_lowercase
> >>> print alpha
> abcdefghijklmnopqrstuvwxyz
> >>> def shift(lst, n):
> 	return [lst[(i+len(lst)-n)%len(lst)] for i,item in enumerate(lst)]

It sure is short, but is it fast? Compare to the function below (the
fastest I can think of ATM):

def shift(lst, n):
	first = (-n) % len(lst)
	result = list(lst[first:]) # if lst is a iterable but not a list
	result.extend(lst[:first])
	return result

Now benchmarking:

$ python2.4 -mtimeit -s "def shift(lst, n): return [lst[(i+len(lst)-n)%
len(lst)] for i,item in enumerate(lst)]"
"shift('abcdefghijklmnopqrstuvwxyz',2)"
10000 loops, best of 3: 21.5 usec per loop
$ python2.4 -mtimeit -s "def shift(lst, n): length = len(lst); first =
(-n) % length; result = list(lst[first:]); result.extend(lst[:first]);
return result" "shift('abcdefghijklmnopqrstuvwxyz',2)"
100000 loops, best of 3: 3.98 usec per loop

The five-line version is more than five times faster than the two-line
counterpart. But it scales better too:

$ python2.4 -mtimeit -s "string = 'abcdefghijklmnopqrstuvwxyz'*10000 def
shift(lst, n): length = len(lst); first = (-n) % length; result =
list(lst[first:]); result.extend(lst[:first]); return result"
"shift(string,2)"
100 loops, best of 3: 10.6 msec per loop
$ python2.4 -mtimeit -s "string = 'abcdefghijklmnopqrstuvwxyz'*10000
def shift(lst, n): return [lst[(i+len(lst)-n)%len(lst)] for i,item in
enumerate(lst)]"         "shift(string,2)"
10 loops, best of 3: 206 msec per loop

With a 10 000 times larger list it takes almost 20 times less time.

Of course a human can't perceive a 17.52 usec difference in time, but
I'd like to make it clear that the two-line function shouldn't be used
on a real system.

What we learn from this? When it's not needed (like now), please don't
iterate over all items of a list.

HTH,

-- 
Felipe.