CODEWITHSUNDEEP
pythonoptimizationlist-comprehension
David Chan
David Chan

Reputation: 7505

Performance difference between list comprehensions and for loops

I have a script that finds the sum of all numbers that can be written as the sum of fifth powers of their digits. (This problem is described in more detail on the Project Euler web site.)

I have written it two ways, but I do not understand the performance difference.

The first way uses nested list comprehensions:

exp = 5

def min_combo(n):
    return ''.join(sorted(list(str(n))))

def fifth_power(n, exp):
    return sum([int(x) ** exp for x in list(n)])

print sum( [fifth_power(j,exp) for j in set([min_combo(i) for i in range(101,1000000) ]) if int(j) > 10 and j == min_combo(fifth_power(j,exp)) ] )

and profiles like this:

$ python -m cProfile euler30.py
443839   
         3039223 function calls in 2.040 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1007801    1.086    0.000    1.721    0.000 euler30.py:10(min_combo)
     7908    0.024    0.000    0.026    0.000 euler30.py:14(fifth_power)
        1    0.279    0.279    2.040    2.040 euler30.py:6(<module>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  1007801    0.175    0.000    0.175    0.000 {method 'join' of 'str' objects}
        1    0.013    0.013    0.013    0.013 {range}
  1007801    0.461    0.000    0.461    0.000 {sorted}
     7909    0.002    0.000    0.002    0.000 {sum}

The second way is the more usual for loop:

exp = 5
ans= 0

def min_combo(n):
    return ''.join(sorted(list(str(n))))


def fifth_power(n, exp):
    return sum([int(x) ** exp for x in list(n)])


for j in  set([ ''.join(sorted(list(str(i)))) for i in range(100, 1000000) ]):
    if int(j) > 10:

        if j ==  min_combo(fifth_power(j,exp)):
            ans += fifth_power(j,exp)

print 'answer', ans

Here is the profiling info again:

$ python -m cProfile euler30.py 
answer 443839
         2039325 function calls in 1.709 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     7908    0.024    0.000    0.026    0.000 euler30.py:13(fifth_power)
        1    1.081    1.081    1.709    1.709 euler30.py:6(<module>)
     7902    0.009    0.000    0.015    0.000 euler30.py:9(min_combo)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  1007802    0.147    0.000    0.147    0.000 {method 'join' of 'str' objects}
        1    0.013    0.013    0.013    0.013 {range}
  1007802    0.433    0.000    0.433    0.000 {sorted}
     7908    0.002    0.000    0.002    0.000 {sum}

Why does the list comprehension implementation call min_combo() 1,000,000 more times than the for loop implementation?

Upvotes: 0

Views: 107

Answers (1)

JBernardo
JBernardo

Reputation: 33397

Because on the second one you implemented again the content of min_combo inside the set call...

Do the same thing and you'll have the same result.

BTW, change those to avoid big lists being created:

sum([something for foo in bar]) -> sum(something for foo in bar)

set([something for foo in bar]) -> set(something for foo in bar)

(without [...] they become generator expressions).

Upvotes: 2

Related Questions