python-3.x - 加速Python中的位串/位运算？

Question

我使用 Sieve of Eratosthenes 编写了一个素数生成器和Python 3.1。代码在 ideone.com 上以 0.32 秒正确、优雅地运行。生成最多 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

正如你想象的那样，分配 10 亿个 bool 值( 1 字节 在 Python 中每个字节 4 或 8 字节(见注释))确实不可行，所以我研究了 bitstring 。我想，每个标志使用 1 位会更加节省内存。然而，该程序的性能急剧下降 - 对于 1,000,000 以内的质数，运行时间为 24 秒。这可能是由于 bitstring 的内部实现造成的。

您可以注释/取消注释这三行，看看我更改了什么以使用 BitString，如上面的代码片段。

我的问题是，有没有办法加速我的程序，无论是否有位串？

编辑:请在发布之前自行测试代码。当然，我不能接受运行速度比我现有代码慢的答案。

再次编辑:

I've compiled a list of benchmarks on my machine.

Answer 1

您的版本有一些小的优化。通过颠倒 True 和 False 的角色，您可以将“if flags[i] is False:”更改为“if flags[i]:”。第二个 range 语句的起始值可以是 i*i 而不是 i*3。你的原始版本在我的系统上需要 0.166 秒。经过这些更改，下面的版本在我的系统上花费了 0.156 秒。

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 = [True, True] + [False] * (limit - 2)
    # Step through all the odd numbers
    for i in range(3, limit, 2):
        if flags[i]:
            continue
        yield i
        # Exclude further multiples of the current prime number
        if i <= sub_limit:
            for j in range(i*i, limit, i<<1):
                flags[j] = True

但这并不能解决你的内存问题。

进入 C 扩展世界，我使用了 gmpy 的开发版本。 (免责声明:我是维护者之一。)开发版本称为 gmpy2，支持称为 xmpz 的可变整数。使用 gmpy2 和以下代码，我的运行时间为 0.140 秒。 1,000,000,000 的限制运行时间为 158 秒。

import gmpy2

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)
    # Actual number is 2*bit_position + 1.
    oddnums = gmpy2.xmpz(1)
    current = 0
    while True:
        current += 1
        current = oddnums.bit_scan0(current)
        prime = 2 * current + 1
        if prime > limit:
            break
        yield prime
        # Exclude further multiples of the current prime number
        if prime <= sub_limit:
            for j in range(2*current*(current+1), limit>>1, prime):
                oddnums.bit_set(j)

插入优化并牺牲清晰度，我使用以下代码获得了 0.107 秒和 123 秒的运行时间:

import gmpy2

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)
    # Actual number is 2*bit_position + 1.
    oddnums = gmpy2.xmpz(1)
    f_set = oddnums.bit_set
    f_scan0 = oddnums.bit_scan0
    current = 0
    while True:
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        if prime > limit:
            break
        yield prime
        # Exclude further multiples of the current prime number
        if prime <= sub_limit:
            list(map(f_set,range(2*current*(current+1), limit>>1, prime)))

编辑:基于此练习，我修改了 gmpy2 以接受 xmpz.bit_set(iterator)。使用以下代码，对于小于 1,000,000,000 的所有素数，Python 2.7 的运行时间为 56 秒，Python 3.2 的运行时间为 74 秒。 (如评论中所述，xrange 比 range 更快。​​)

import gmpy2

try:
    range = xrange
except NameError:
    pass

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)
    oddnums = gmpy2.xmpz(1)
    f_scan0 = oddnums.bit_scan0
    current = 0
    while True:
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        if prime > limit:
            break
        yield prime
        if prime <= sub_limit:
            oddnums.bit_set(iter(range(2*current*(current+1), limit>>1, prime)))

编辑#2:再试一次!我修改了 gmpy2 以接受 xmpz.bit_set(slice) 。使用以下代码，对于 Python 2.7 和 Python 3.2，所有小于 1,000,000,000 的素数的运行时间约为 40 秒。

from __future__ import print_function
import time
import gmpy2

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 = gmpy2.xmpz(1)
    # pre-allocate the total length
    flags.bit_set((limit>>1)+1)
    f_scan0 = flags.bit_scan0
    current = 0
    while True:
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        if prime > limit:
            break
        yield prime
        if prime <= sub_limit:
            flags.bit_set(slice(2*current*(current+1), limit>>1, prime))

start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)

编辑#3:我已更新 gmpy2 以正确支持 xmpz 位级别的切片。性能没有变化，但 API 非常好。我做了一些调整，把时间缩短到了 37 秒左右。 (请参阅编辑 #4 以更改 gmpy2 2.0.0b1。)

from __future__ import print_function
import time
import gmpy2

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.
    '''
    sub_limit = int(limit**0.5)
    flags = gmpy2.xmpz(1)
    flags[(limit>>1)+1] = True
    f_scan0 = flags.bit_scan0
    current = 0
    prime = 2
    while prime <= sub_limit:
        yield prime
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        flags[2*current*(current+1):limit>>1:prime] = True
    while prime <= limit:
        yield prime
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1

start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)

编辑#4:我在 gmpy2 2.0.0b1 中做了一些更改，打破了前面的示例。 gmpy2 不再将 True 视为提供无限 1 位源的特殊值。应使用 -1 代替。

from __future__ import print_function
import time
import gmpy2

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.
    '''
    sub_limit = int(limit**0.5)
    flags = gmpy2.xmpz(1)
    flags[(limit>>1)+1] = 1
    f_scan0 = flags.bit_scan0
    current = 0
    prime = 2
    while prime <= sub_limit:
        yield prime
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1
        flags[2*current*(current+1):limit>>1:prime] = -1
    while prime <= limit:
        yield prime
        current += 1
        current = f_scan0(current)
        prime = 2 * current + 1

start = time.time()
result = list(prime_numbers(1000000000))
print(time.time() - start)

编辑#5:我对 gmpy2 2.0.0b2 进行了一些增强。您现在可以迭代所有已设置或清除的位。运行时间缩短了约 30%。

from __future__ import print_function
import time
import gmpy2

def sieve(limit=1000000):
    '''Returns a generator that yields the prime numbers up to limit.'''

    # Increment by 1 to account for the fact that slices do not include
    # the last index value but we do want to include the last value for
    # calculating a list of primes.
    sieve_limit = gmpy2.isqrt(limit) + 1
    limit += 1

    # Mark bit positions 0 and 1 as not prime.
    bitmap = gmpy2.xmpz(3)

    # Process 2 separately. This allows us to use p+p for the step size
    # when sieving the remaining primes.
    bitmap[4 : limit : 2] = -1

    # Sieve the remaining primes.
    for p in bitmap.iter_clear(3, sieve_limit):
        bitmap[p*p : limit : p+p] = -1

    return bitmap.iter_clear(2, limit)

if __name__ == "__main__":
    start = time.time()
    result = list(sieve(1000000000))
    print(time.time() - start)
    print(len(result))