0

我在 Python 2.7 中编写了一个用于创建素数列表的代码。代码是

def primes_list(num):
    ans = [2]
    for i in range(3, num, 2):
        for j in ans:
            if i % j == 0:
                break
        else:
            ans.append(i)
    else:
        return ans

这是否比埃拉托色尼筛法更有效？我认为内存效率应该更好，但我对时间效率表示怀疑。如何计算时间和内存效率以及如何对效率进行基准测试？

4

4 回答 4

4

您正在做的是试用除法- 将每个候选素数与它下面的每个已知素数进行测试。在调用中跳过奇数range将为您节省一些除法，但这正是筛选所基于的技术：您知道每个第二个数字都可以被 2 整除，因此是复合数。筛子只是将其扩展到：

  • 每三个数都可以被三整除，因此是合数；
  • 每五分之一乘五，因此是复合的

等等。由于筛子被认为是可用的最省时的算法之一，而试验划分是最少的算法之一（维基百科将筛子描述为O(n log log n)，并且根据下面的评论，您的算法很可能O(n^2 / log n)）），有理由假设具有一些类似筛子优化的试验划分达不到筛分效果。

于 2013-05-22T11:40:58.387 回答
3

不，那是试除法，在时间复杂度上比埃拉托色尼筛法差得多。它的空间复杂度要好一些，但是，因为素数是关于n/log(n)你并没有节省大量的内存。筛子也可以使用位向量来完成，它将常数减少 32/64 倍（因此出于实际目的，它可能会更好）。

显示时间差异的小基准测试：

>>> timeit.timeit('primes_list(1000)', 'from __main__ import primes_list', number=1000)
0.901777982711792
>>> timeit.timeit('erat(1000)', 'from __main__ import erat', number=1000)
0.2097640037536621

如您所见，即使使用n=1000eratosthenes 也快 4 倍以上。如果我们将搜索增加到10000：

>>> timeit.timeit('primes_list(10000)', 'from __main__ import primes_list', number=1000)
50.41101098060608
>>> timeit.timeit('erat(10000)', 'from __main__ import erat', number=1000)
2.3083159923553467

现在，eratosthenes 的速度提高了 21 倍。正如你所看到的，很明显，eratosthenes要快得多。

使用 numpy 数组很容易将内存减少 32 或 64（取决于您的机器架构）并获得更快的结果：

>>> import numpy as np
>>> def erat2(n):
...     ar = np.ones(n, dtype=bool)
...     ar[0] = ar[1] = False
...     ar[4::2] = False
...     for j in xrange(3, n, 2):
...             if ar[j]:
...                     ar[j**2::2*j] = False
...     return ar.nonzero()[0]
... 
>>> timeit.timeit('erat2(10000)', 'from __main__ import erat2', number=1000)
0.5136890411376953

比其他筛子快 4 倍。

于 2013-05-22T11:39:51.050 回答
1

“如何衡量效率？”

测量经验增长顺序，就是这样！:)

例如，使用来自已接受答案、log_10(50.41/0.9) = 1.75和的数据log_10(2.31/0.21) = 1.04，因此它是~ n^1.75您的 TD（试验部门）代码（在 1,000 ... 10,000 范围内）与~ n^1.04Eratosthenes 筛子的经验增长顺序。

其中，后者与 一致n log log n，而前者与一致n^2 / log(n)^2。

有了g(n) = n^2 / log(n)^2，我们有了g(10000)/g(1000) = 56.25，仅比经验值低 0.4% 50.41/0.9 = 56.01。但是g2(n) = n^2 / log(n)，我们有g2(10000)/g2(1000) = 75，这与证据相去甚远。

关于时间复杂度：实际上，大多数复合都提前失败（是小素数的倍数）。在这里产生k=n/log(n)素数需要时间，通过所有O(k^2)前面的素数来测试每个素数，而不是那些不超过其平方根的素数。

复合材料不会增加复杂性（M. ONeill 的 JFP 文章（第 4 页）中的精确分析给出了复合材料与素数测试时相同的复杂性sqrt- 每个复合材料都保证有一个不大于其的素数因子sqrt- 所以复合材料的复杂性甚至低于这里素数的复杂性）。

所以总体来说O(k^2)是 ，也就是说，O(n^2/log(n)^2)。

通过仅添加两行代码，您可以显着提高代码的速度，包括O(n^2/log(n)^2)时间O(n^1.5/log(n)^2)复杂度：

    for j in ans: 
        if j*j > i: 
            ans.append(i); break; 
        if i % j == 0:
            break
    # else:
    #     ans.append(i)

17.8x时间复杂度的提高意味着10,000 比 1,000的运行时间比率，而不是56.25x像以前那样。这转化~ n^1.25为该范围内的经验增长顺序（而不是~ n^1.75）。10,000 次调用的绝对运行时间将比旧的 50.41 秒更接近 2.31 秒。

顺便说一句，您的原始代码相当于大卫特纳的著名代码，

primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, rem y x /= 0]

和改进的代码，对此：

primes = 2 : sieve [3..] primes 
sieve xs (p:ps) | (h,t) <- span (< p*p) xs =
              h ++ sieve [y | y <- t, rem y p /= 0] ps

（代码在 Haskell 中，我认为它具有足够的可读性。x:xs代表带有x头部元素和xs列表其余部分的列表）。

于 2013-05-23T19:36:20.373 回答
0

由于range在 Python 2 中返回一个列表，您的算法的空间复杂度仍然是O(n)，因此它的空间效率并不高（至少不是渐近的）。如果您使用 xrange （或 Python 3 中的 range ），它会更节省空间，因为您只会存储素数 - 并非所有数字都达到n.

无论哪种方式，您的时间效率都会比筛子差。

于 2013-05-22T11:41:34.893 回答