Julia for 循环比 while 慢？

Question

我正在使用 Julia 语言，并注意到我编写的小程序非常慢。怀疑它与for循环有某种关系，我将其重写为使用while，并且速度提高了大约 15 倍。

我确信我在范围等方面做错了什么，但我不知道是什么。

function primes_for()
    num_primes = 0
    for a = 2:3000000
        prime = true
  
        sa = floor(sqrt(a))
        
        for c in 2:sa
             if a % c == 0
                 prime = false
                 break
             end
         end

        if prime
            num_primes += 1
        end
    end
    println("Number of primes is $num_primes")
end

function primes()
    num_primes = 0
    a = 2
    while a < 3000000
        prime = true

        c = 2
        while c * c <= a
            if a % c == 0
                prime = false
                break
            end
            c += 1
        end
  
        if prime
            num_primes += 1
        end

        a += 1
    end
    println("Number of primes is $num_primes")
end

@time primes_for()
@time primes()

Answer 1

正如 @Vincent Yu 和 @Kelly Bundy 的评论中所解释的，这是因为sa = floor(sqrt(a))创建了一个浮动。然后c就变成了漂浮物，而且a % c速度很慢。

\n

您可以替换floor(sqrt(a))为floor(Int, sqrt(a))，或者最好替换为 ，我认为，替换为isqrt(a)，它会返回

\n

\n

m整数平方根：满足 的最大整数m*m <= n。

\n

\n

这可以避免由于浮点错误floor(Int, sqrt(a))而可能发生的（不太可能）向下舍入过大的事件。sqrt(x^2) = x - \xce\xb5

\n

编辑：这是一个要演示的基准（注意 的使用isqrt）：

\n

function primes_for2()\n    num_primes = 0\n    for a = 2:3000000\n        prime = true\n  \n        # sa = floor(sqrt(a))\n        sa = isqrt(a)\n        \n        for c in 2:sa\n             if a % c == 0\n                 prime = false\n                 break\n             end\n         end\n\n        if prime\n            num_primes += 1\n        end\n    end\n    println("Number of primes is $num_primes")\nend\n\n1.7.0> @time primes_for()\nNumber of primes is 216816\n  6.705099 seconds (15 allocations: 480 bytes)\n\n1.7.0> @time primes_for2()\nNumber of primes is 216816\n  0.691304 seconds (15 allocations: 480 bytes)\n\n1.7.0> @time primes()\nNumber of primes is 216816\n  0.671784 seconds (15 allocations: 480 bytes)\n

\n

我可以注意到，我的计算机上的每次调用isqrt大约需要 8 纳秒，而 3000000 乘以 8 纳秒就是 0.024 秒。调用常规程序sqrt大约需要 1 纳秒。

\n

Answer 2

造成速度差异的不是 for/while，而是sqrt. sqrt 返回 float 没有帮助，这会促进围绕整数 sqrt 输出的所有其余代码。

请注意，@time 不是测量 while 和 for 循环，而是测量这些循环之外的代码。

如果您正在对代码进行基准测试，则代码的其余部分需要相同，并且删除 sqrt 是该算法中的主要优化之一。也可以c * c在测试中删除 ，但这比较棘手。