Eratosthenes筛选速度比较:Python与朱莉娅

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

这是朱莉娅代码:

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代码在大约.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.5x).

在朱莉娅写一个更惯用的写作方式是使用一系列布尔值,打开和关闭它们:

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在端部返回的索引,其中的载体是非零(即真实).在我的机器上,这比其他Julia版本快5倍(0.0001秒),比Python版本快45倍.