Ускорить битовые / битовые операции в Python? - PullRequest
Новая
       62

Ускорить битовые / битовые операции в Python?

39 голосов
/ 24 мая 2010

Я написал генератор простых чисел, используя Сито Эратосфена и Python 3.1.Код работает правильно и изящно за 0,32 секунды на ideone.com для генерации простых чисел до 1 000 000. 

# from bitstring import BitString

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...    
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5) 
    flags = [False, False] + [True] * (limit - 2)   
#     flags = BitString(limit)
    # Step through all the odd numbers
    for i in range(3, limit, 2):       
        if flags[i] is False:
#        if flags[i] is True:
            continue
        yield i
        # Exclude further multiples of the current prime number
        if i <= sub_limit:
            for j in range(i*3, limit, i<<1):
                flags[j] = False
#                flags[j] = True

Проблема в том, что у меня не хватает памяти при попытке сгенерироватьчисла до 1 000 000 000. 

    flags = [False, False] + [True] * (limit - 2)   
MemoryError

Как вы можете себе представить, выделение 1 миллиарда логических значений ( 1 байт 4 или 8 байтов (см. комментарий) каждое в Python) действительно неосуществимо,поэтому я посмотрел на цепочку бит .Я полагал, что использование 1 бита для каждого флага будет намного более эффективным с точки зрения памяти.Тем не менее, производительность программы резко упала - 24 секунды времени выполнения, для простого числа до 1 000 000.Вероятно, это связано с внутренней реализацией цепочки битов.

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

У меня такой вопрос, Есть ли способ ускорить мою программу с использованием цепочки битов или без нее?

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

Изменить еще раз:

Я собрал список тестов на своеммашина.

Ответы [ 11 ]

1 голос
/ 27 мая 2010

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

Используйте любое медленное решение, чтобы сгенерировать список и сохранить его в исходный файл python, например, primes.py, который будет содержать: 

primes = [ a list of a million primes numbers here ]

Теперь, чтобы использовать их, вам просто нужно сделать import primes, и вы получите их с минимальным объемом памяти при скорости дискового ввода-вывода. Сложность - число простых чисел: -)

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

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

Страница:
...