0

我正在使用 Python 2.7

在我编写的 Erat2() 的两个 Eratosthenes 的 Sieve 实现中，erat() 和 erat2() 的好处是，在第二次运行 erat2() 时，它在相对较短的时间内给出了结果。

def erat2(num, isprime = [2]):
    if num > len(isprime) + 2:

        last_original = len(isprime) + 2
        isprime += [num for num in xrange(last_original ,num + 1)]

        for i in xrange(2,num + 1):
            if isprime[i-2]:
                if i <= last_original:
                    j = last_original//i + 1
                else:
                    j = 2
                temp = j * i
                while temp <= num:
                    isprime[temp-2] = 0
                    j += 1
                    temp = j * i

    return filter(lambda x: x != 0, isprime[:num - 1])

def erat(num):
    isprime = [num for num in xrange(2,num + 1)]
    for i in xrange(2,num + 1):
        if isprime[i-2]:
            j = 2
            temp = j * i
            while temp <= num:
                isprime[temp-2] = 0
                j += 1
                temp = j * i

    return filter(lambda x: x != 0, isprime)

import time
def t():
    num = 100000000
    i = 10
    while i < num:
        s = time.time()
        erat2(i)
        x = time.time() - s

        print "%10d %10f" %(i,x),

        s = time.time()
        erat(i)
        y = time.time() - s

        print " %10f" %(y)

        i *= 10

为了支持在第二次运行代码时结果会更快的事实，这里给出了一些时序分析。第一列是测试输入。第二列是 erat2() 的时序，第三列是 erat() 的时序。很明显，在第二次运行中时间减少了 7 倍。

>>> t()
        10   0.000000    0.000000
       100   0.000000    0.000000
      1000   0.000000    0.000000
     10000   0.010000    0.010000
    100000   0.100000    0.110000
   1000000   1.231000    1.410000
  10000000  13.605000   15.081000
>>> t()
        10   0.000000    0.000000
       100   0.000000    0.000000
      1000   0.000000    0.000000
     10000   0.000000    0.020000
    100000   0.020000    0.140000
   1000000   0.170000    1.550000
  10000000   1.770000   15.752000

我面临的问题是此测试输入后内存使用量激增。

  • 是否可以进行一些优化以减少内存消耗？
  • 这样的内存增加是一个很好的实施实践吗？

编辑：

我发现对函数 erat() 和 erat2() 进行了一些优化以提高速度。将 lambda 函数从

lambda x: x != 0

至

lambda x: x

结果相同，但速度稍快。num = 10000000 时快一秒。

编辑2：

使用了 vartec 和 btilly 的建议。将 erat() 改进为 erat3()。这是改进的实现以及时序检查。还发现在 xrange 函数中放置表达式会导致性能损失。添加变量以提高性能。

def erat3(num):
    ''' Improves Sieve of eratosthenes '''
    #REQUIRES MATH MODULE
    if num < 2:
        return []

    isprime = [num for num in xrange(3,num + 1,2)]
    #temp2's expression placed in xrange function => performance-loss
    temp2 = int(math.sqrt(num)) + 1
    for i in xrange(3, temp2 ,2):
        if isprime[(i-3)/2]:
            j = 3
            temp = j * i
            while temp <= num:
                isprime[(temp-3)/2] = 0
                j += 2
                temp = j * i

    return [2] + filter(lambda x: x, isprime)

erat() 和 erat3() 的时间

>>> t()
        10   0.000000    0.000000
       100   0.000000    0.000000
      1000   0.000000    0.000000
     10000   0.010000    0.010000
    100000   0.110000    0.040000
   1000000   1.241000    0.530000
  10000000  14.131000    6.111000
4

2 回答 2

2

在内存和性能之间进行权衡是很常见的。哪个对您更重要取决于您的应用程序。

在这种情况下，我建议通过使用 BitVector 来缓解这种情况（有关详细信息，请参阅https://pypi.python.org/pypi/BitVector），以便您创建的数据结构更加紧凑。

同样在这种情况下，特殊的外壳 2 并且仅存储奇数位将使性能加倍，并将内存减半，但代价是代码复杂度稍高。这可能是值得的。

于 2013-06-03T19:48:20.893 回答
0

您可以对 isprime 数组使用单个位。Python 并没有为您提供一种非常快速的方法来操作这些位，但一种简单的方法是使用 long。

is_prime = (1 << num) - 1

并使用它来检查一个数字是否已被筛选

is_prime & (1 << x)

以下是如何将其应用到您的第二个功能的最小更改

def erat(num):
    isprime = (1 << num) - 1
    for i in xrange(2,num + 1):
        if isprime & (1 << i):
            j = 2
            temp = j * i
            while temp <= num:
                isprime &= (1 << num) - 1 - (1 << temp)
                j += 1
                temp = j * i
    return [i for i in range(num) if isprime&(1 << i)]

可能值得将其存储(1 << num)在局部变量中以节省一遍又一遍地构建它。正如@btilly 指出的那样，通过一些额外的工作，您只需跟踪奇数就可以节省一半的空间。

于 2013-06-03T19:48:57.283 回答