Почему этот алгоритм хуже?

Question

В Википедии это один из заданных алгоритмов для генерации простых чисел:

def eratosthenes_sieve(n):
    # Create a candidate list within which non-primes will be
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = [i for i in range(n + 1)]
    fin = int(n ** 0.5)

    # Loop over the candidates, marking out each multiple.
    for i in range(2, fin + 1):
        if not candidates[i]:
            continue

        candidates[i + i::i] = [None] * (n // i - 1)

    # Filter out non-primes and return the list.
    return [i for i in candidates[2:] if i]

Я немного изменил алгоритм.

def eratosthenes_sieve(n):
    # Create a candidate list within which non-primes will be
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = [i for i in range(n + 1)]
    fin = int(n ** 0.5)

    # Loop over the candidates, marking out each multiple.

    candidates[4::2] = [None] * (n // 2 - 1)

    for i in range(3, fin + 1, 2):
        if not candidates[i]:
            continue

        candidates[i + i::i] = [None] * (n // i - 1)

    # Filter out non-primes and return the list.
    return [i for i in candidates[2:] if i]

Я впервые отметилот всех кратных 2, а затем я рассмотрел только нечетные числа.Когда я рассчитывал оба алгоритма (пробовал 40.000.000), первый всегда был лучше (хотя и немного).Я не понимаю почему.Может кто-нибудь объяснить, пожалуйста?

PS: Когда я пытаюсь 100.000.000, мой компьютер зависает.Это почему?У меня есть Core Duo E8500, 4 ГБ ОЗУ, Windows 7 Pro 64 бит.

Обновление 1: Это Python 3.

Обновление 2: Вот как я рассчитал время:

start = time.time()
a = eratosthenes_sieve(40000000)
end = time.time()
print(end - start)

ОБНОВЛЕНИЕ: После ценных комментариев (особенно Nightcracker и Winston Ewert) мне удалось сначала написать то, что я намеревался:

def eratosthenes_sieve(n):
    # Create a candidate list within which non-primes will be
    # marked as None; only c below sqrt(n) need be checked. 
    c = [i for i in range(3, n + 1, 2)]
    fin = int(n ** 0.5) // 2

    # Loop over the c, marking out each multiple.

    for i in range(fin):
        if not c[i]:
            continue

        c[c[i] + i::c[i]] = [None] * ((n // c[i]) - (n // (2 * c[i])) - 1)

    # Filter out non-primes and return the list.
    return [2] + [i for i in c if i]

Этот алгоритм улучшает оригинальный алгоритм (упоминается сверху) (обычно) на 50%.(Тем не менее, это хуже, чем алгоритм, упомянутый nightcracker, естественно).

Вопрос к Python Masters: есть ли более Pythonic способ выразить этот последний код более «функциональным» способом?

ОБНОВЛЕНИЕ 2: Я все еще не смог расшифровать алгоритм, упомянутый Nightcracker.Я думаю, что я слишком глуп.

Answer 1

Вы не экономите много времени, избегая вечеров. Большая часть времени вычислений в алгоритме тратится на это:

candidates[i + i::i] = [None] * (n // i - 1)

Эта строка вызывает много действий со стороны компьютера. Всякий раз, когда рассматриваемое число является четным, оно не запускается, поскольку цикл выполняет оператор if. Время, потраченное на выполнение цикла для четных чисел, таким образом, действительно очень мало. Таким образом, устранение этих четных циклов не приводит к значительному изменению времени цикла. Вот почему ваш метод не намного быстрее.

Когда python создает числа для диапазона, он использует формулу: start + index * step. Умножение на два, как в вашем случае, будет немного дороже, чем в первом случае.

Существует также небольшая нагрузка на более длинную функцию.

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

Answer 2

Вопрос в том, почему это было бы даже быстрее? В обоих примерах вы фильтруете кратные два, трудный путь. Не имеет значения, используете ли вы жесткий код candidates[4::2] = [None] * (n // 2 - 1) или он выполняется в первом цикле for i in range(2, fin + 1):.

Если вы заинтересованы в оптимизированном сите Eratosthenes, вот вам:

def primesbelow(N):
    # /2029352/samyi-bystryi-sposob-perechislit-vse-prostye-chisla-nizhe-n#2029364
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = (N, N-1, N+4, N+3, N+2, N+1)[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

Объяснение здесь: Портирование оптимизированного сита эратосфена с Python на C ++

Первоначальный источник здесь , но объяснений не было. Вкратце, это простое число пропускает кратные 2 и 3 и использует несколько хаков для быстрого назначения Python.

Answer 3

Ваш дополнительный шаг не является необходимым и фактически будет проходить через всю коллекцию n, выполнив операцию «избавиться от четности» вместо того, чтобы просто работать с n ^ 1 / 2.

Answer 4

Это, вероятно, немного медленнее, потому что вы выполняете дополнительную настройку, чтобы сделать что-то, что было сделано в первом случае в любом случае (отмечая кратные два).Это время установки может быть тем, что вы видите, если оно так мало, как вы говорите