Является ли это оптимальным простым генератором?

Является ли это каким-либо образом оптимальным решением для нахождения простых чисел? Я не пытаюсь добавить каждую оптимизацию на свете, но хороша ли основная?

def primesUpto(self, x):
    primes = [2]
    sieve = [2]
    i = 3
    while i <= x:
        composite = False
        j = 0
        while j < len(sieve):
            sieve[j] = sieve[j] - 1
            if sieve[j] == 0:
                composite = True
                sieve[j] = primes[j]
            j += 1
        if not composite:
            primes.append(i)
            sieve.append(i*i-i)
        i += 1
    return primes

python algorithm primes sieve-of-eratosthenes sieve
person Kody King    schedule 31.05.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Хм, очень интересно. Ваш код на самом деле честен до совершенства подлинное сито Эратосфена ИМХО, считая свой путь по возрастанию натуральных чисел, уменьшая каждый счетчик, который он устанавливает для каждого встречающегося простого числа, на 1 на каждом шагу.

И это очень неэффективно. Проверено на Ideone, он работает на том же эмпирический порядок роста ~ n^2.2 (в проверенном диапазоне нескольких тысяч простых чисел) как известно неэффективный Сито пробного деления Тернера (на языке Haskell).

Почему? Некоторые причины. Во-первых, в вашем тесте нет раннего выхода из строя: когда вы обнаружите, что это составной элемент, вы продолжаете обработку массива счетчиков, sieve. Вы должны это сделать по второй причине: вы подсчитываете разницу, уменьшая каждый счетчик на 1 на каждом шаг, где 0 представляет ваше текущее положение. Это наиболее точное выражение оригинального решета ИМХО, и оно очень неэффективно: сегодня наши процессоры умеют складывать числа за время O(1) (если эти числа принадлежат определенному диапазону, 0 .. 2^32 или 0 .. 2^64, разумеется).

Более того, наши компьютеры теперь тоже имеют оперативную память, и, вычислив дальнее число, мы можем пометить его в массиве оперативного доступа. Что лежит в основе эффективности решета Эратосфена на современных компьютерах — как прямое вычисление, так и прямое выделение кратных.

И третье, возможно, самая непосредственная причина неэффективности, — это преждевременная обработка кратных значений: когда вы сталкиваетесь с 5 в качестве простого числа вы добавляете его первое кратное (еще не встреченное), то есть 25, сразу в массив счетчиков, sieve (т.е. расстояние между текущей точкой и кратным, i*i-i). Это слишком рано. Прибавление 25 нужно отложить до... ну, пока мы не встретим 25 среди возрастающих натуральных чисел. Преждевременное начало обработки кратных каждому простому числу (в p вместо p*p) приводит к необходимости поддерживать слишком много счетчиков — O(n) из них (где n — количество произведенных простых чисел), а не только O(π(sqrt(n log n))) = O(sqrt(n / log n)).

Оптимизация отсрочки при применении к аналогичному "счетному" ситу в Haskell принесла свои эмпирические порядки рост с ~ n^2.3 .. 2.6 для n = 1000 .. 6000 простых чисел до чуть выше ~ n^1.5 (с очевидным огромным приростом скорости). Когда подсчет был далее заменен прямым сложением, результирующие измеренные эмпирические порядки роста были ~ n^1.2 .. 1.3 при получении до 1/1 миллиона простых чисел (хотя, по всей вероятности, он выиграет на ~ n^1.5 для больших диапазонов).

person Will Ness    schedule 31.05.2013
comment
Спасибо за оценку, очень помогает. - person Kody King; 04.06.2013