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

Question

10-я задача в Project Euler:

Сумма простых чисел ниже 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

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

Answer 1

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

Snippet-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) операций, что является прямым следствием того факта, что ряд основной гармоники *1038* асимптотически приближается к log log n.

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

Answer 2

Первая версия предварительно вычисляет все простые числа в диапазоне и сохраняет их в массиве sieve, затем для нахождения решения достаточно просто добавить простые числа в массив.Его можно рассматривать как форму памятки .

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

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

Answer 3

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

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 раза с общим количеством 4 489 006 (~ 4,5 миллиона) итераций в цикле for.

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.

Подсчет вызовов функций и итераций цикла не всегда является убедительным способом определить, почему алгоритм работает быстрее, но обычно меньше шагов == меньше времени, и, очевидно, ваш код может использовать некоторую оптимизацию для сокращения количества шагов.

Answer 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 не позволяет вам выполнять повторную работу для числа, с которым вы встречались ранее.