2012-02-10 3 views
4

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

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

опубликован here , которые проходят в течение 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 

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

ответ

10

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

Snippet-1 использует алгоритм sieve of Eratosthenes, обнаруженный около 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), как прокомментировал @ Даниэль Фишер), предполагая, что дивизии стоят так же, как умножения.

Из Википедии (сопряженный выше) статьи:

сложности времени в случайной модели машины доступа O (N журнал журнал п) операций, является прямым следствием того, что prime harmonic series асимптотически приближается log log n.

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

+0

Почему это O (n log logn), является n = log (2e6) или n = 2e6? – 0x90

+1

Я имею в виду 'n = 2e6' –

+0

Пробное деление останавливается у квадратного корня, поэтому его сложность лучше, чем O (n^2), с верхней части головы, я бы сказал O (n^1.5/log n), но я не учитывал композиты с большими наименьшими основными факторами, поэтому он может быть немного хуже (верхняя граница O (n^1.5)). –

4

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

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

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

+0

@machineyearning спасибо, я включил ссылку на мой ответ –

+1

производительность не за счет предварительного вычисления простых чисел. Это происходит из-за того, что они предварительно вычисляются. –

+1

Призыв к сите Эратосфена алгоритм замеченного пробного деления не делает должного кредита. –

2

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

В вашем решении, номер 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() функций, которые отслеживают, сколько раз функция была вызвана и общее количество для итераций цикла:

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 млн) итераций для цикла.

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