Почему цикл while намного эффективнее, чем цикл for здесь?

Question

Я работаю над Сито Эратосфена, и я анализирую, как я могу фильтровать непростые числа из диапазона кандидатов.

Для тестирования, я использую эту команду:

import timeit 
print timeit.timeit(stmt="sieve(1000)", setup='from sieve import sieve', number=1000) 

Это то, что я в настоящее время:

def sieve(limit): 
    primes = [2] 
    pRange = range(3, limit, 2) 
    while pRange: 
     p = pRange.pop(0) 
     filter_range = range(p**2, limit, p << 1) 
     pRange = filter(lambda x: x not in filter_range, pRange) 
     primes.append(p) 
    return primes 

секунд =>5.42698788643

Я тогда подумал, что если бы я был собираюсь выпустить первый элемент из диапазона, я мог бы написать его вот так:

def sieve(limit): 
    primes = [2] 
    pRange = range(3, limit, 2) 
    for p in pRange: 
     filter_range = range(p**2, limit, p << 1) 
     pRange = filter(lambda x: x not in filter_range, pRange) 
     primes.append(p) 
    return primes 

, но он оказывается намного медленнее на 15.7085180283 Секунд.

Почему это происходит? Является ли цикл for итерацией по начальному значению pRange и не обновляется?

Answer 1

for p in pRange: 

Это оценивает pRange, превращая его в список (Python 2) или генератор (Python 3), а затем итерацию по элементам в диапазоне. Он не переоценивает pRange.

В любом случае это приведет к большему количеству итераций цикла, чем цикл while, потому что последний пересматривает диапазон каждый раз через цикл.

Помните, что в Python переменные все ссылки. Даже что-то вроде a = 5 означает «установить a для обозначения целочисленной константы со значением 5». Аналогично, pRange = filter(...) означает «возьмите объект, возвращаемый filter(...), и установите для него pRange. Отпустите ссылку на любое значение pRange, используемое для ссылки (и, возможно, на сборку мусора позже, если на это ничего не ссылается)».