range() vs xrange() Python2|3 issues for performance
__peter__ at web.de
Tue Aug 2 11:05:43 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.
range = xrange
> So, here is PyPerfectNumbers.py ----------------------------
> def PNums(q):
> for i in range(2, q):
> m = 1
> s = 0
> while m <= i/2:
i/2 returns a float in Python 3; you should use i//2 for consistency.
> if not i%m:
> s += m
> m += 1
> if i == s:
> return 0
> def perf(n):
> 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.
Python 3's range() is indeed slower, but not orders of magnitude:
$ python3.2 -m timeit -s"r = range(33550336)" "for i in r: pass"
10 loops, best of 3: 1.88 sec per loop
$ python2.7 -m timeit -s"r = xrange(33550336)" "for i in r: pass"
10 loops, best of 3: 1.62 sec per loop
$ cat tmp.py
range = xrange
return n == sum(i for i in range(1, n) if not n % i)
if __name__ == "__main__":
$ time python2.7 tmp.py
$ time python3.2 tmp.py
I don't know what's causing the slowdown, maybe the int/long unification is
> 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?
More information about the Python-list