[Tutor] List comprehension question

[Stefan Behnel]

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