Проект Euler 10-Почему первый код python работает намного быстрее, чем второй?

10-я задача в проекте Эйлера:

Сумма простых чисел ниже 10 равна 2 + 3 + 5 + 7 = 17.

Найти сумму всех простых чисел ниже двух миллионов.

Я нашел этот фрагмент: 

sieve = [True] * 2000000 # Sieve is faster for 2M primes
def mark(sieve, x):
    for i in xrange(x+x, len(sieve), x):
        sieve[i] = False

for x in xrange(2, int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve, x)

print sum(i for i in xrange(2, len(sieve)) if sieve[i])

Опубликовано здесь которые работают в течение 3 секунд.

Я написал этот код: 

def isprime(n):
    for x in xrange(3, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

sum=0;
for i in xrange(1,int(2e6),2):
    if isprime(i):
        sum += i

Я не понимаю, почему мой код (второй) намного медленнее?

4 4
python primes

4 ответа:

Ваш алгоритм проверяет каждое число в отдельности от 2 до N (где N=2000000) на примитивность.

Сниппет-1 использует сито Эратосфена алгоритм, открытый около 2200 лет назад. Он не проверяет каждое число, но:

  • делает "сито" из всех чисел от 2 до 2000000.
  • находит первое число (2), помечает его как простое, а затем удаляет все его кратные из сита.
  • затем находит следующее неотделенное число (3), помечает его как простое число и удаляет все его кратные из сита.
    • Затем находит следующее неотделенное число (5), помечает его как простое и удаляет все его кратные из сита.
  • ...
  • до тех пор, пока он не найдет простое число 1409 и не удалит все его кратные из сита.
  • тогда все простые числа до 1414 ~= sqrt(2000000) были найдены и он останавливается
  • числа от 1415 до 2000000 проверять не нужно. Все они, которые не были удалены, являются простыми числами, тоже.

Таким образом, алгоритм производит все простые числа до N.

Заметьте, что он не делает никакого деления, только сложения (даже не умножения, и не то, чтобы это имело значение с такими маленькими числами, но это могло бы быть с большими). Временная сложность равна O(n loglogn) , в то время как ваш алгоритм имеет что-то около O(n^(3/2)) (или O(n^(3/2) / logn), как прокомментировал @Daniel Fischer), предполагая, что деление стоит столько же, сколько умножение.

Из статьи Википедии (ссылка выше):

Сложность времени в модель машины произвольного доступа - это o (n log log n) операций, прямое следствие того, чторяд простых гармоник асимптотически приближается к log log n.

(с n = 2e6 в данном случае)

10

Первая версия предварительно вычисляет все простые числа в диапазоне и сохраняет их в массиве sieve, затем найти решение-это простой вопрос добавления простых чисел в массив. Он может рассматриваться как форма мемоизация.

Вторая версия проверяет каждое число в диапазоне, чтобы увидеть, является ли оно простым, повторяя много работы, уже проделанной предыдущими вычислениями.

В заключение, первая версия избегает повторного вычисления значений, в то время как вторая версия выполняет одни и те же операции снова и снова.

4

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

В вашем решении число 2 будет проверяться для каждого числа, когда это число будет проверяться на простое число. Каждое число, которое вы проходите по пути, будет использоваться в качестве потенциального делителя для каждого следующего числа.

В первом решении, как только вы перешагнули через число, вы никогда не оглядываетесь назад - вы всегда двигаетесь вперед от места, которого достигли. Кстати, а возможной и распространенной оптимизацией является переход на нечетные числа только после того, как вы отметили 2: 
mark(sieve, 2)
for x in xrange(3, int(len(sieve) ** 0.5) + 1, 2):
    if sieve[x]: mark(sieve, x)
Таким образом, вы только смотрите на каждое число один раз и очищаете все его умножения вперед, вместо того чтобы снова и снова проходить через все возможные делители, проверяя каждое число со всеми его предшественниками, и оператор if мешает вам выполнять повторную работу для числа, с которым вы ранее столкнулись.
2

Как показывает ответ Оскара, ваш алгоритм повторяет много работы. Чтобы увидеть, сколько всего экономит обработка другого алгоритма, рассмотрим следующую модифицированную версию функций mark() и isprime(), которые отслеживают, сколько раз была вызвана функция и общее число итераций цикла for: 

calls, count = 0, 0
def mark(sieve, x):
    global calls, count
    calls += 1
    for i in xrange(x+x, len(sieve), x):
        count += 1
        sieve[i] = False

После выполнения первого кода с этой новой функцией мы видим, что mark() вызывается 223 раза с общим числом 4489 006 (~4,5 миллиона) итераций в течение петля.

calls, count = 0
def isprime(n):
    global calls, count
    calls += 1
    for x in xrange(3, int(n**0.5)+1):
        count += 1
        if n % x == 0:
            return False
    return True
Если мы внесем аналогичное изменение в ваш код, то увидим, что isprime() вызывается 1 000 000 (1 миллион) раз с 177 492 735 (~177,5 миллиона) итерациями цикла for. Подсчет вызовов функций и итераций цикла не всегда является убедительным способом определить, почему алгоритм быстрее, но обычно меньше шагов = = меньше времени, и ясно, что ваш код может использовать некоторую оптимизацию для уменьшения числа шагов.
2