4

几周前我在 python 中编写了 erathostenes 算法，它看起来像下面这样：

def erathostenes(n):

    A = range(2,n+1)
    B = []
    i = 0

    while A[i] < math.sqrt(n):
        B.append(A[i])
        j = i
        aux = A[i]
        while j < len(A):
            if A[j]%aux == 0:
                A[j] = 0
            j += aux
        i += 1
        while A[i] == 0:
            i +=  1
    for i in range(len(A)):
        if A[i] != 0:
            B.append(A[i])
        i += 1
    return B

经过一番思考（我是编程菜鸟），我只是对我的算法进行了一些修改，现在看起来像：

def erathostenes(n):

    A = range(2,n + 1)
    B = []
    i = 0

    raiz = math.sqrt(n)
    lenA = len(A)       
    rangeLenA = range(lenA)

    while A[i] < raiz:
        B.append(A[i])
        j = i
        aux = A[i]

        while j < lenA:
            A[j] = 0
            j += aux
        i += 1
        while A[i] == 0:
            i +=  1
    for i in rangeLenA:
        if A[i] != 0:
            B.append(A[i])
        i += 1
    return B

如果我使用 n=10.000.000 执行算法，则第一个代码中的执行时间约为 7 秒，而第二个代码中的执行时间约为 4 秒。

关于我的算法中更多优化的任何想法？谢谢！

4

4 回答 4

4 
i += 1

在最后一个循环很有趣。

考虑更换

for i in rangeLenA:

和

for i in xrange(LenA)

您可以避免生成不需要的庞大列表。

编辑：

还要考虑这个：

    for j in xrange(i,lenA,aux):

代替：

    while j < lenA:

并修复错误

while A[i] <= raiz:

正如friday所建议的那样。

于 2013-10-26T15:19:40.293 回答
2

您的代码中有错误。改变

while A[i] < raiz:

上

while A[i] <= raiz:

当 N 为平方时，您会发现错误。

对于优化使用xrange代替rangeLenA。

于 2013-10-26T15:44:14.650 回答
2

试图制作一个非循环版本只是为了好玩。结果是这样的：

def erathostenes(n):

    def helper_function(num_lst, acc):

        if not num_lst:
            return acc
        if len(num_lst) == 1:
            acc.append(num_lst[0])
            return acc
        num = num_lst.pop(0)
        multiples = ([x for x in range(num + 1, num_lst[-1] + 1) 
                         if x % num == 0])

        remains = ([x for x in num_lst if x not in multiples])
        acc.append(num)
        return helper_function(remains, acc )
    return helper_function(range(2, n + 1), [])

当我运行计时时，post erathhostenes（1000）得到 826 us，我的版本（！！）得到 26ms。让我感到惊讶，它是如此缓慢。

函数式编程更有趣，但看起来不适合这个问题，在 Python 中（我的猜测是在更函数式的语言中它会更快）。

所以我尝试了一个命令式版本。它看起来像这样：

def erathostenes_imperative(n):
    limit = int(math.sqrt(n))
    def helper_function(flags, size):
        for i in range(2,limit):
            if flags[i] == True:
                j = 2*i
                while j < size:
                    if j % i == 0:
                        flags[j] = False
                    j = j + i
        return [x for x in range(2, n + 1) if flags[x]]
    return helper_function([True]*(n + 1), n)

我所做的是将整数列表更改为真/假标志列表。直觉上，看起来迭代速度更快，对吧？

我的结果是 831ms 的 erathostenes_imperative(100000)，而你的版本是 1.45。

遗憾的是，命令式编写它的速度更快。代码看起来很乱，包含所有的 fors、while、i 和 j

于 2013-10-26T18:04:14.553 回答
1

试试阿特金筛。它很相似，但它是对埃拉托色尼筛法的修改，它会立即过滤掉所有 2、3、5 的倍数，以及一些其他优化。您可能还想尝试找到一个工具来告诉您每个操作的运行时间，并使用更长的运行时间修改这些操作。

但是，由于您是编程新手，因此最好为您服务，要么实现其他算法，要么进行其他编程练习以进行改进。

于 2013-10-26T15:58:58.367 回答