python - Eratosthenes 筛法速度比较 : Python vs Julia

Question

所以我有一些用 Python 和 Julia 编写的 Eratosthenes 函数，我正在比较运行时间。

这是 Python 代码:

import time

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

start = time.time()
get_primes(10000)
print time.time() - start

这是 Julia 代码:

function get_primes(n)
        numbers = [2:n]
        primes = Int[]
        while numbers != []
                p = numbers[1]
                push!(primes, p)
                numbers = setdiff(numbers, [p*i for i=1:int(n/p)])
        end
        return primes
end

@time get_primes(10000);

Python 代码的运行时间约为 0.005 秒，而 Julia 代码的运行时间约为 0.5 秒，这意味着 Python 的运行速度大约快 100 倍。这可能有一个完全合乎逻辑的原因，但我真的不知道我在做什么。

Answer 1

主要区别在于，在 Python 中，您分配单个集合 number，然后就地修改它，而在 Julia 中，您在每次迭代时分配一个新数组环形。另一个区别是您在 Python 中使用集合，在 Julia 中使用数组(Python 称之为“列表”)。让我们更改 Julia 代码以消除这两个差异:

function get_primes(n)
    numbers = IntSet(2:n)
    primes = Int[]
    while !isempty(numbers)
        p = shift!(numbers)
        push!(primes, p)
        setdiff!(numbers, p:p:n)
    end
    return primes
end

有了这个变化，在我的系统上，Julia 代码比 Python 代码快 10 倍(0.0005 对 0.0048 秒)。请注意，我还使用了一个范围作为 setdiff! 的第二个参数——它比使用推导式构建数组更简洁、更快 (1.5 倍)。

在 Julia 中更惯用的写法是使用 bool 值数组，打开和关闭它们:

function eratosthenes(n)
    primes = fill(true,n)
    primes[1] = false
    for p = 2:n
        primes[p] || continue
        for i = 2:div(n,p)
            primes[p*i] = false
        end
    end
    find(primes)
end

末尾的 find 返回向量非零(即 true)的索引。在我的机器上，这比其他 Julia 版本快 5 倍(0.0001 秒)，比 Python 版本快 45 倍。