Разница между списками и петлями

Question

У меня есть скрипт, который находит сумму всех чисел, которые могут быть записаны как сумма пятых степеней их цифр. (Эта проблема описана более подробно on the Project Euler web site.)

Я написал это двумя способами, но я не понимаю разницу в производительности.

Первый способ использует вложенные списковых:

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)) ]) 

и профили, как это:

$ 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} 

Второй способ является более обычным for цикл:

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 

Здесь информация профилирования снова:

$ 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} 

Почему реализация реализации списка вызывает min_combo() на 1000 000 раз больше, чем реализация цикла цикла for?

Answer 1

Потому что на второй раз вы реализовали содержание min_combo внутри set вызова ...

Сделайте то же самое, и вы будете иметь тот же результат.

BTW, изменить те, чтобы избежать больших списков создается:

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

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

(без [...] они становятся выражениями генератора).