JuliaでBigIntsが遅くなっている

Question

プロセッサ集約型Eulerプロジェクトの質問で、Dより速く走ったので、Juliaには本当に感銘を受けた。 ＃303誰かが興味があれば。

ジュリアの遅いBigIntsのように見えますか？私は彼らのパフォーマンスを読むので奇妙なはかなり良いです。

以下は、オイラーの漸化式を使用して15kのパーティション数を計算するJuliaプログラムです。

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桁の応答が生成されます。

同等のPythonコードでpypyを実行するとわずか8秒かかります。

私は間違っていますか？

Answer 1

現在、BigIntsはJuliaでかなり遅いです。これは、すべての整数がBigIntであるPythonではなく、各演算が新しいBigIntを割り当てるため、基本的な演算が高速になるようにかなりの時間を費やしているからです。 Pythonは実際には、小さな整数値がインラインで表現され、値が大きすぎる場合にのみBigIntとして表現されるハイブリッドアプローチを使用します。ジュリアでも同じことが絶対に行われるかもしれませんが、標準化されたIntの値は機械整数なので、BigIntsの性能は重要ではありません。 BigIntのパフォーマンスへの真の後押しは、JuliaのBigInt型をGCと統合し、小さなBigInt値をスタックに割り当ててレジスタに入れることができるようにすることです。しかし、私たちはまだそこにはいません。

Answer 2

すばらしい対応がありがとうStefanに感謝します。

私は、bigintsのないJuliaバージョンはまだpypyよりも遅いオーダーを実行しているので、何かが続いていると感じています。

これは別の質問としてあまり答えはありません。

そのオイラー・プロジェクトの質問は、最初の数が何百万分の1であるかを調べることです。したがって、機械定数を使用して行うことができるように、有効桁数が6桁を少し上回る必要があります。

Juliaのこのバージョンは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() 

残りの部分ではなく、より一般的な弾性を与えるためにジュリアに％を使用する（ちなみに、みんなありがとう。:)それが答えを返すために取得しようとしている私に全体の夜の費用がかかり、何％$＃％ &！ ）

pypyで動作しているpythonのバージョンは、4分の1秒で41秒で完了します。 （公平にpython2で動くには13分48秒かかる）

だから何が問題なの？ 20行目の二重回帰？どうすればスピードアップできますか？これを読んだ人は気にしませんが、プロジェクトオイラーのプログラム実行には1分のルールがあります。

Answer 3

次のバージョンは、ジュリア0.4で私のマシン上で12秒の下で実行されます：

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)