Eratosthenes筛速比较:Python与Julia [英] Sieve of Eratosthenes Speed Comparison: Python vs Julia

问题描述

因此，我有一些用Python和Julia编写的Eratosthenes函数的筛子，并且我正在比较运行时间.

So I have a little sieve of Eratosthenes function written in both Python and Julia, and I'm comparing run times.

这是Python代码:

Here is the Python code:

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代码的运行时间约为.005秒，而Julia代码的运行时间约为.5秒，这意味着Python的运行速度大约快100倍.可能有一个完全合乎逻辑的原因，但是我真的不知道自己在做什么.

The Python code runs in about .005 seconds, while the Julia code takes about .5 seconds, so that means Python runs about 100x times faster. There's probably a perfectly logical reason for this, but I really have no idea what I'm doing.

推荐答案

主要区别在于，在Python中，您分配了一个单独的集number，然后对其进行了修改，而在Julia中，您是在循环的每次迭代中分配一个新数组.另一个区别是您在Python中使用了一个集合，在Julia中使用了一个数组(Python称之为列表").让我们更改Julia代码以消除这两个区别:

The main difference is that in Python you're allocating a single set, number, and then modifying it in place, while in Julia, you're allocating a new array on every iteration of the loop. Another difference is that you're using a set in Python and an array in Julia (what Python calls a "list"). Let's change the Julia code to eliminate these two differences:

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).

With this change, on my system, the Julia code is 10x faster than the Python code (0.0005 vs. 0.0048 seconds). Note that I also used a range as the second argument of the setdiff! – it's both terser and faster (1.5x) than constructing an array with a comprehension.

在朱莉娅中写这句话的一种更惯用的风格是使用布尔数组，打开和关闭它们:

A somewhat more idiomatic style of writing this in Julia would be to use an array of booleans, turning them on and off:

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倍.

The find at the end returns the indices where a vector is non-zero (i.e. true). On my machine, this is 5x faster (0.0001 seconds) than the other Julia version and 45x faster than the Python version.

这篇关于Eratosthenes筛速比较:Python与Julia的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！