2

我最近从这里下载了 bitarray 模块，以获得更快的初筛，但结果令人沮丧。

from bitarray import bitarray
from numpy import ones
from timeit import timeit


def sieve1(n = 1000000):
    '''Sieve of Eratosthenes (bitarray)'''
    l = (n - 1)/2; a = bitarray(l); a.setall(True)
    for i in xrange(500):
        if a[i]:
            s = i+i+3; t = (s*s-3)/2; a[t:l:s] = False
    return [2] + [x+x+3 for x in xrange(l) if a[x]]

def sieve2(n = 1000000):
    '''Sieve of Eratosthenes (list)'''
    l = (n - 1)/2; a = [True] * l
    for i in xrange(500):
        if a[i]:
            s = i+i+3; t = (s*s-3)/2; u = l-t-1
            a[t:l:s] = [False] * (u/s + 1)
    return [2] + [x+x+3 for x in xrange(l)]

def sieve3(n = 1000000):
    '''Sieve of Eratosthenes (numpy.ones)'''    
    l = (n - 1)/2; a = ones(l, dtype=bool)
    for i in xrange(500):
        if a[i]:
            s = i+i+3; t = (s*s-3)/2; a[t:l:s] = False
    return [2] + [x+x+3 for x in xrange(l)]

print timeit(sieve1, number=10)
print timeit(sieve2, number=10)
print timeit(sieve3, number=10)

结果如下——

1.59695601594
0.666230770593
0.523708537583

筛子的bitarray速度是列表的两倍多。有人对更好的阵列有建议吗？任何东西都应该比 python 快list，或者我想。 numpy.ones最快，但我不喜欢，numpy因为它需要很长时间import。

我基本上是在寻找一个快速的数据持有者，它是可变的，并且可以持有True和False.

4

1 回答 1

2

bitarray 中位的实际设置和清除速度非常快。正在做的是建立退货清单的速度较慢。与其遍历一个范围，然后测试每个位，不如利用 bitarray 对遍历位的支持。

试试这个：

def bitarray_sieve(n = 1000000):
    '''Sieve of Eratosthenes (bitarray)'''
    l = (n - 1)//2; a = bitarray(l); a.setall(True)
    for i in range(500):
        if a[i]:
            s = i+i+3; t = (s*s-3)//2; a[t:l:s] = False
    return [2] + [x+x+3 for x,b in enumerate(a) if b]

它在我的机器上运行大约 0.38 秒，而列表版本大约需要 0.47 秒。

你看过这个问题吗？

我维护 gmpy2 并添加了迭代整数位和设置/清除位的能力。

以下示例大约需要 0.16 秒。

def gmpy2_sieve2(n=1000000):
    '''Sieve of Eratosthenes (gmpy2, version 2)'''
    l = (n - 1)//2; a = gmpy2.xbit_mask(l)
    for i in range(500):
        if a[i]:
            s = i+i+3; t = (s*s-3)//2; u = l-t-1
            a[t:l:s] = 0
    return [2] + [x+x+3 for x in a.iter_set()]

现在的瓶颈是计算x+x+3。以下解决方案不会跳过筛分 2。它需要两倍的内存，但它允许立即使用位位置。在我的机器上大约需要 0.08 秒：

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

    Bits are set to 1 if their position is composite.'''

    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 list(bitmap.iter_clear(2, limit))

对于位的实际设置/清除，bitarray 比 gmpy2 快。而且 bitarray 有很多 gmpy2 所缺乏的能力。但是，我在二进制中找不到更快的方法来获取设置或清除哪些位的索引。

顺便说一句，您的基准函数 sieve2() 和 sieve3() 返回不正确的结果；你不见了if a[x]。

于 2013-03-28T05:40:43.047 回答