我一直在 Julia 中试验各种主要筛子,以期找到最快的筛子。这是我最简单的,如果不是我最快的话,它在我的 1.80 GHz 处理器上运行大约 5-6 毫秒,n = 100 万。但是,当我添加一个简单的“if”语句来处理 n <= 1 或 s(起始编号)> n 的情况时,运行时间会增加 15 倍,达到 80-90 毫秒左右。
using BenchmarkTools
function get_primes_1(n::Int64, s::Int64=2)::Vector{Int64}
#=if n <= 1 || s > n
return []
end=#
sieve = fill(true, n)
for i = 3:2:isqrt(n) + 1
if sieve[i]
for j = i ^ 2:i:n
sieve[j]= false
end
end
end
pl = [i for i in s - s % 2 + 1:2:n if sieve[i]]
return s == 2 ? unshift!(pl, 2) : pl
end
@btime get_primes_1(1_000_000)
如上所述,注释掉“if”语句的输出是:
5.752 ms (25 allocations: 2.95 MiB)
包含“if”语句的输出是:
86.496 ms (2121646 allocations: 35.55 MiB)
我可能非常无知或非常愚蠢,但如果有人能指出我做错了什么,我们将不胜感激。
最佳答案
这个函数的问题在于,当你的函数中出现闭包时,Julia 编译器在类型推断方面存在问题。在这种情况下,闭包是一个理解,问题是 if
声明使sieve
只能有条件地定义。
移动sieve
可以看到向上:
function get_primes_1(n::Int64, s::Int64=2)::Vector{Int64}
sieve = fill(true, n)
if n <= 1 || s > n
return Int[]
end
for i = 3:2:isqrt(n) + 1
if sieve[i]
for j = i ^ 2:i:n
sieve[j]= false
end
end
end
pl = [i for i in s - s % 2 + 1:2:n if sieve[i]]
return s == 2 ? unshift!(pl, 2) : pl
end
但是,这使得 sieve
也将在 n<1
时创建我猜你想避免 :)。
你可以通过包装sieve
来解决这个问题在 let
像这样阻止:
function get_primes_1(n::Int64, s::Int64=2)::Vector{Int64}
if n <= 1 || s > n
return Int[]
end
sieve = fill(true, n)
for i = 3:2:isqrt(n) + 1
if sieve[i]
for j = i ^ 2:i:n
sieve[j]= false
end
end
end
let sieve = sieve
pl = [i for i in s - s % 2 + 1:2:n if sieve[i]]
return s == 2 ? unshift!(pl, 2) : pl
end
end
或者避免像这样的内部闭包:
function get_primes_1(n::Int64, s::Int64=2)::Vector{Int64}
if n <= 1 || s > n
return Int[]
end
sieve = fill(true, n)
for i = 3:2:isqrt(n) + 1
if sieve[i]
for j = i ^ 2:i:n
sieve[j]= false
end
end
end
pl = Int[]
for i in s - s %2 +1:2:n
sieve[i] && push!(pl, i)
end
s == 2 ? unshift!(pl, 2) : pl
end
现在您可能会问如何检测此类问题并确保某些解决方案可以解决这些问题?答案是使用 @code_warntype
在一个函数上。在您的原始功能中,您会注意到 sieve
是Core.Box
这表明存在问题。
参见 https://github.com/JuliaLang/julia/issues/15276了解详情。总的来说,在我看来,这是 Julia 代码性能最重要的问题,很容易被忽略。希望将来编译器会更聪明。
关于if-statement - Julia 中的一个简单的 'if' 语句将我的主筛的运行时间增加了 15 倍——为什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50785681/