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

造成速度差异的不是 for/while，而是 sqrt。 sqrt returns 浮点数没有帮助，它提升了整数输出的 sqrt 周围的所有其余代码。

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

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

Answer 2

正如@Vincent Yu 和@Kelly Bundy 在评论中所解释的那样，这是因为 sa = floor(sqrt(a)) 创建了一个浮动。那么c就变成了float，而a % c就慢了。

您可以将 floor(sqrt(a)) 替换为 floor(Int, sqrt(a))，或者 最好是 ，我认为 isqrt(a)，其中 returns

Integer square root: the largest integer m such that m*m <= n.

这避免了 floor(Int, sqrt(a)) 可能向下舍入过多的（不太可能的）事件，如果 sqrt(x^2) = x - ε 由于浮点错误可能会发生这种情况。

编辑： 这里有一个基准来演示（注意 isqrt 的使用）：

function primes_for2()
    num_primes = 0
    for a = 2:3000000
        prime = true
  
        # sa = floor(sqrt(a))
        sa = isqrt(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

1.7.0> @time primes_for()
Number of primes is 216816
  6.705099 seconds (15 allocations: 480 bytes)

1.7.0> @time primes_for2()
Number of primes is 216816
  0.691304 seconds (15 allocations: 480 bytes)

1.7.0> @time primes()
Number of primes is 216816
  0.671784 seconds (15 allocations: 480 bytes)

我注意到在我的计算机上每次调用 isqrt 大约需要 8ns，3000000 次 8ns 是 0.024 秒。调用常规 sqrt 大约需要 1ns。

Julia for 循环比 while 慢？

Julia for loops slower than while?

julia