python - BigInts 在 Julia 中似乎很慢

Question

Julia 给我留下了深刻的印象，因为它在处理器密集型 Euler 项目问题上的运行速度比 D 快。第303章 有兴趣的话

奇怪的是 Julia 中的 BigInts 似乎有多慢。奇怪是因为我看了他们的表现相当不错。

下面是一个 Julia 程序，使用欧拉的递推公式计算 15k 的分区数。

function eu78()
  lim = 15000
  ps = zeros(BigInt, lim)

  function p(n)  #applies Euler recurrence formula
    if n < 0
      return BigInt(0)
    elseif n == 0
      return BigInt(1)
    elseif ps[n] > 0
      return ps[n]
    end
    s = BigInt(0)
    f = BigInt(-1)
    for k = 1 : n
      f *= -1
      t1 = (k * (3k - 1)) ÷ BigInt(2)
      t2 = (k * (3k + 1)) ÷ 2
      s += f * (p(n - t1) + p(n - t2))
    end
    ps[n] = s
  end

  for i = 1 : lim
    p(i)
  end
  println(ps[lim])
end

eu78()

以惊人的 3 分 43 秒运行以生成 132 位数字答案。

使用 pypy 运行的等效 Python 代码仅需 8 秒。

我究竟做错了什么？

Answer 1

BigInts 目前在 Julia 中相当慢。这是因为每个操作都会分配一个新的 BigInt，而不是 Python，其中所有整数都是 BigInt，因此他们花费了相当多的时间来确保基本操作是快速的。 Python 实际上使用了一种混合方法，其中小整数值被内联表示，并且只有当值变得太大时才将它们表示为 BigInt。在 Julia 中绝对可以做到这一点，但还没有人实现这一点——部分原因是标准 Int值是机器整数，因此 BigInts 的性能并不重要。 BigInt 性能的真正提升将来自于将 Julia 的 BigInt 类型与 GC 集成，并允许将小的 BigInt 值分配到堆栈中——并存在于寄存器中。然而，我们还没有到那个程度。