大人物在朱莉看来很慢

Question

我对Julia印象很深，因为它在一个处理器密集的Euler项目问题上比D快。#如果有人感兴趣的话。在

奇怪的是茱莉亚的大人物看起来有多慢。奇怪，因为我看他们的表演相当不错。在

下面是一个Julia程序，用Euler递推公式计算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

大人物现在在茱莉亚是相当缓慢的。这是因为每个操作都分配一个新的BigInt，而Python中所有的整数都是BigInt，因此它们花了相当多的时间来确保基本操作的速度。Python实际上使用了一种混合方法，在这种方法中，小的整数值被内联表示，只有当值太大时，它们才会被表示为大人物。在Julia中完全可以做到这一点，但还没有人实现这一点，部分原因是标准的Int值是机器整数，因此bigint的性能并不重要。BigInt性能的真正提升将来自于将Julia的BigInt类型与GC集成，并允许对小的BigInt值进行堆栈分配并驻留在寄存器中。不过，我们还没有完全达到目的。在

Answer 2

以下版本在我的机器上运行不到12秒，Julia 0.4：

const lim = 6*10^4
const ps = zeros(Int64, lim)
ps[1] = 1

function p(n)  #applies Euler recurrence formula for the number of partitions
    n < 0 && return 0
    n == 0 && return 1

    ps[n] > 0 && return ps[n]

    s, f = 0, -1

    for k = 1:n
      f *= -1
      t1 = (k * (3k - 1)) ÷ 2
      t2 = (k * (3k + 1)) ÷ 2
      s += f * (p(n - t1) + p(n - t2))
    end

    siz = 10^9
    ps[n] = mod(s, siz)
end

function eu78(lim=6*10^4)

    for i = 10:lim
        a = p(i)
        if mod(a, 1000000) == 0
            return (i, a)
        end
    end
end

@time eu78(10)  # warm-up

@time eu78(6*10^4)

Answer 3

感谢Stefan的快速反应。在

不过，我觉得还有别的原因，因为没有bigints的Julia版本运行速度仍然比pypy慢几个数量级。在

所以这与其说是一个答案，不如说是一个不同的问题。在

这个欧拉项目的问题是要找到第一个，它的分裂总数是一百万的倍数。所以我们只需要超过6个有效数字，这样就可以使用机器整数来完成。在

这是朱莉娅的这个版本，在2分44秒内完成。在

function eu78()
  const lim = 6 * 10 ^ 4
  ps = zeros(Int64, lim)
  ps[1] = 1
  const siz = 10 ^ 9

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

 for i = 10 : lim
   a = p(i)
   if mod(a, 1000000) == 0
     println(i,'\n', a)
     break
   end
 end
end

eu78()

（顺便说一句，感谢各位使用Julia中的%来给出余数，而不是更常见的模。：）我花了整整一个晚上的时间试图让它返回一个答案，任何%$\%&；！而不是什么都没有。）

在pypy中运行的python版本只需41秒就可以完成，这是时间的四分之一。（公平地说，用Python2跑，需要13分48秒。）

有什么问题吗？第20行的双递归？我怎样才能加快速度？阅读本文的人并不在意，但是projecteuler中有一个关于程序执行的一分钟规则。在