efficiency of range() and xrange() in for loops

[Felipe Almeida Lessa]

Em Qua, 2006-04-05 às 22:24 +0200, Fredrik Lundh escreveu:
> the difference isn't very
> large, xrange is actually slower in some python versions, and you'll
> need the integer objects sooner or later anyway... 

Some code is worth a thousand words:


$ python2.3
Python 2.3.5 (#2, Mar  6 2006, 10:12:24)
[GCC 4.0.3 20060304 (prerelease) (Debian 4.0.2-10)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import Timer
>>> min(Timer('for i in range(1): pass').repeat(3, 100000))/100
0.00099303960800170891
>>> min(Timer('for i in xrange(1): pass').repeat(3, 100000))/100
0.00077417135238647464
>>> min(Timer('for i in range(10): pass').repeat(3, 1000))
0.0016450881958007812
>>> min(Timer('for i in xrange(10): pass').repeat(3, 1000))
0.0013418197631835938
>>> min(Timer('for i in range(100): pass').repeat(3, 1000))
0.010170936584472656
>>> min(Timer('for i in xrange(100): pass').repeat(3, 1000))
0.0073339939117431641
>>> min(Timer('for i in range(1000): pass').repeat(3, 1000))
0.083337783813476562
>>> min(Timer('for i in xrange(1000): pass').repeat(3, 1000))
0.070460796356201172
>>> min(Timer('for i in range(10000): pass').repeat(3, 1000))
0.88027620315551758
>>> min(Timer('for i in xrange(10000): pass').repeat(3, 1000))
0.71050214767456055
>>> min(Timer('for i in range(100000): pass').repeat(3, 1000))
13.938336849212646
>>> min(Timer('for i in xrange(100000): pass').repeat(3, 1000))
7.0900959968566895
>>> min(Timer('for i in range(1000000): pass').repeat(3, 100))*10
141.37096881866455
>>> min(Timer('for i in xrange(1000000): pass').repeat(3, 100))*10
70.822579860687256


$ python2.4
Python 2.4.3 (#2, Mar 30 2006, 21:52:26)
[GCC 4.0.3 (Debian 4.0.3-1)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import Timer
>>> min(Timer('for i in range(1): pass').repeat(3, 100000))/100
0.00084012031555175776
>>> min(Timer('for i in xrange(1): pass').repeat(3, 100000))/100
0.00069013833999633791
>>> min(Timer('for i in range(10): pass').repeat(3, 1000))
0.0014748573303222656
>>> min(Timer('for i in range(10): pass').repeat(3, 1000))
0.0014920234680175781
>>> min(Timer('for i in xrange(10): pass').repeat(3, 1000))
0.0012860298156738281
>>> min(Timer('for i in range(100): pass').repeat(3, 1000))
0.0079219341278076172
>>> min(Timer('for i in xrange(100): pass').repeat(3, 1000))
0.0069670677185058594
>>> min(Timer('for i in range(1000): pass').repeat(3, 1000))
0.079225063323974609
>>> min(Timer('for i in xrange(1000): pass').repeat(3, 1000))
0.067707061767578125
>>> min(Timer('for i in range(10000): pass').repeat(3, 1000))
0.84912896156311035
>>> min(Timer('for i in xrange(10000): pass').repeat(3, 1000))
0.6791541576385498
>>> min(Timer('for i in range(100000): pass').repeat(3, 1000))
13.973598003387451
>>> min(Timer('for i in xrange(100000): pass').repeat(3, 1000))
6.8047640323638916
>>> min(Timer('for i in range(1000000): pass').repeat(3, 100))*10
138.38916063308716
>>> min(Timer('for i in xrange(1000000): pass').repeat(3, 100))*10
68.15216064453125


In sum, difference is as big as the function argument, but xrange was
*never* slower on Python 2.3 or Python 2.4 on x86 with Linux. I'd say
three things:

1) Probably xrange is faster than range on other architectures and
operational systems as well.
2) I can't say anything for Python < 2.3.
3) Run your own tests. If you see the same I saw, use xrange everywhere
you can.

The 3rd point is specially true if your code can be break in the middle,
for example (a really dumb example, I know):

for i in xrange(0, 10000000, 42):
	if i**2 >= x:
		break

This way you won't create all numbers, in this case just those less than
sqrt(x) plus one.

Cheers,

-- 
Felipe.