Hugo Arts, 08.11.2010 00:53:
On Mon, Nov 8, 2010 at 12:36 AM, Richard D. Moores wrote:
def proper_divisors(n):
"""
Return the sum of the proper divisors of positive integer n
"""
return sum([x for x in range(1,n) if int(n/x) == n/x])
The list comprehension is this function is inefficient in that it computes
n/x twice. I'd like to do an a = n/x and use a in
"if int(a) == a", but I don't know how.
You can't do that inside a list comprehension. Either get rid of the
comprehension and do a regular loop, or get rid of the n/x expression.
I'd suggest replacing the whole check with x % n == 0. n is a proper
divisor of x if there is no remainder after division, after all. This
also means you won't have to do a cast, which tend to be fairly
expensive.
On another note, getting rid of the list comprehension and using a
generator expression will be even faster, since you won't have to
build the list.
I gave this suggestion a try. It is true for me when run in CPython 3.2:
$ python3 -m timeit -s 'from divisors import forloop' 'forloop(1000000)'
10 loops, best of 3: 161 msec per loop
$ python3 -m timeit -s 'from divisors import genexp' 'genexp(1000000)'
10 loops, best of 3: 159 msec per loop
$ python3 -m timeit -s 'from divisors import listcomp' 'listcomp(1000000)'
10 loops, best of 3: 171 msec per loop
However, it is no longer true when I run the same thing in Cython:
$ python3 -m timeit -s 'from divisors import forloop' 'forloop(1000000)'
100 loops, best of 3: 13.6 msec per loop
$ python3 -m timeit -s 'from divisors import genexp' 'genexp(1000000)'
100 loops, best of 3: 13.6 msec per loop
$ python3 -m timeit -s 'from divisors import listcomp' 'listcomp(1000000)'
100 loops, best of 3: 12.6 msec per loop
Here, the listcomp clearly wins, i.e.
return sum([x for x in range(1,n) if n%x == 0])
is actually *faster* than the inlined loop for
result = sum(x for x in range(1,n) if n%x == 0)
return result
This totally surprised me, until I figured out what was going on here.
In the case of the listcomp, the inner loop is smaller, it does not contain
the adding. It only contains the division that filters out the
non-divisors. Then, from time to time, it calls into the list appender to
append a Python integer that actually matched the condition. But the final
list is tiny, so this is done extremely rarely compared to the number of
loop iterations. The tighter loop simply wins. And summing up a short list
in another tight loop is just another very fast operation.
Lesson learned:
Sometimes, it can be worth splitting a loop in two, one with a tight filter
for the values, and another one to work on the remaining values.
Stefan
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
