range() vs xrange() Python2|3 issues for performance
harmar at member.fsf.org
Tue Aug 2 09:12:20 CEST 2011
The following is intended as a helpful small extension to the xrange()
range() discussion brought up this past weekend by Billy Mays...
With Python2 you basically have two ways to get a range of numbers:
range() , which returns a list, and
xrange() , which returns an iterator.
With Python3 you must use range(), which produces an iterator; while
xrange() does not exist at all (at least not on 3.2).
I have been doing some research in number theory related to Mersenne
Primes and perfect numbers (perfects, those integers whose primary
divisors when summed result in the number, not including the number
itself)... the first few of those being 6, 28, 496, 8128, 33550336, etc
Never mind, but you know... are there an infinite number of them?
... and of course, are there any "odd" perfect numbers... well not under
10^1500.... I digress, sorry ...
This brought up the whole range() xrange() thing for me again
because Python in any case is just not fast enough (no brag, just fact).
So my perfect number stuff is written in C, for the moment. But, what
about the differences in performance (supposing we were to stay in
Python for small numbers) between xrange() vs range() [on Python2]
versus range() [on Python3]? I have put my code snips below, with some
explanation below that... these will run on either Python2 or
Python3... except that if you substitute xrange() for range() for
Python2 they will throw an exception on Python3... doh.
So, here is PyPerfectNumbers.py ----------------------------
for i in range(2, q):
m = 1
s = 0
while m <= i/2:
if not i%m:
s += m
m += 1
if i == s:
sum = 0
for i in range(1, n):
if n % i == 0:
sum += i
return sum == n
fperf = lambda n: n == sum(i for i in range(1, n) if n % i == 0)
PNums(8200) will crunch out the perfect numbers below 8200.
perf(33550336) will test to see if 33550336 is a perfect number
fperf(33550336) is the lambda equivalent of perf()
These are coded with range(). The interesting thing to note is that
xrange() on Python2 runs "considerably" faster than the same code using
range() on Python3. For large perfect numbers (above 8128) the
performance difference for perf() is orders of magnitude. Actually,
range() on Python2 runs somewhat slower than xrange() on Python2, but
things are much worse on Python3.
This is something I never thought to test before Billy's question,
because I had already decided to work in C for most of my integer
stuff... like perfects. But now that it sparked my interest, I'm
wondering if there might be some focus placed on range() performance in
Python3 for the future, PEP?
FSF ...free as in freedom/
More information about the Python-list