[解決済み] Project Eulerとの速度比較。CとPythonとErlangとHaskellの比較

質問

私は 問題点その12 から プロジェクト・オイラー プログラミングの練習として、またC、Python、Erlang、Haskellでの私の（きっと最適ではない）実装を比較するために。より高い実行時間を得るために、私は元の問題で述べられている500の代わりに1000以上の約数を持つ最初の三角形を探します。

その結果、以下のようになりました。

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

Pythonです。

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

real    1m16.632s
user    1m16.370s
sys 0m0.250s

PyPyでPython。

lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 
842161320

real    0m13.082s
user    0m13.050s
sys 0m0.020s

Erlangです。

lorenzo@enzo:~/erlang$ erlc euler12.erl 
lorenzo@enzo:~/erlang$ time erl -s euler12 solve
Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.4  (abort with ^G)
1> 842161320

real    0m48.259s
user    0m48.070s
sys 0m0.020s

ハスケル

lorenzo@enzo:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
lorenzo@enzo:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

概要を説明します。

• C: 100%
• パイソン 692% (PyPy使用時 118%)
• Erlang: 436% (RichardCに135%感謝)
• ハスケル 1421%

Cは、他の3つのように任意の長さの整数ではなく、longを使って計算するので、大きなアドバンテージがあると思います。また、ランタイムを最初に読み込む必要もない（他の3つはそうなのか）。

質問1: Erlang、Python、Haskellは任意の長さの整数を使うことで速度が低下するのでしょうか？ MAXINT ?

質問2: Haskellはなぜこんなに遅いのでしょうか？ブレーキをかけるコンパイラのフラグがあるのか、それとも私の実装に問題があるのか？(私にとってHaskellは7つの封印を持つ本なので、後者の可能性が高いです)。

質問3． 要因の決定方法を変えずに、これらの実装を最適化するためのヒントを教えてください。最適化とは、より良いもの、より速いもの、よりネイティブなものなど、どのようなものでもよいのです。

EDITです。

質問4． 私の関数型実装はLCO（last call optimization、別名末尾再帰排除）を許可し、コールスタック上に不要なフレームを追加しないようにしていますか？

HaskellとErlangの知識は非常に限られていますが、4つの言語で同じアルゴリズムをできるだけ同じように実装することを心がけました。

---

使用したソースコード

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square;
    int count = isquare == square ? -1 : 0;
    long candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

---

#! /usr/bin/env python3.2

import math

def factorCount (n):
    square = math.sqrt (n)
    isquare = int (square)
    count = -1 if isquare == square else 0
    for candidate in range (1, isquare + 1):
        if not n % candidate: count += 2
    return count

triangle = 1
index = 1
while factorCount (triangle) < 1001:
    index += 1
    triangle += index

print (triangle)

---

-module (euler12).
-compile (export_all).

factorCount (Number) -> factorCount (Number, math:sqrt (Number), 1, 0).

factorCount (_, Sqrt, Candidate, Count) when Candidate > Sqrt -> Count;

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

factorCount (Number, Sqrt, Candidate, Count) ->
    case Number rem Candidate of
        0 -> factorCount (Number, Sqrt, Candidate + 1, Count + 2);
        _ -> factorCount (Number, Sqrt, Candidate + 1, Count)
    end.

nextTriangle (Index, Triangle) ->
    Count = factorCount (Triangle),
    if
        Count > 1000 -> Triangle;
        true -> nextTriangle (Index + 1, Triangle + Index + 1)  
    end.

solve () ->
    io:format ("~p~n", [nextTriangle (1, 1) ] ),
    halt (0).

---

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' number sqrt candidate count
    | fromIntegral candidate > sqrt = count
    | number `mod` candidate == 0 = factorCount' number sqrt (candidate + 1) (count + 2)
    | otherwise = factorCount' number sqrt (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

解決方法は？

使用方法 GHC 7.0.3 , gcc 4.4.6 , Linux 2.6.29 x86_64 Core2 Duo (2.5GHz)マシン上で、コンパイルは ghc -O2 -fllvm -fforce-recomp はHaskell用で gcc -O3 -lm はC言語用です。

• あなたのCルーチンは8.4秒で実行されます（あなたの実行より速いのは、おそらく -O3 )
• Haskellによる解答は36秒で実行される（原因は -O2 フラグ)
• あなたの factorCount' のコードが明示的に型付けされておらず、デフォルトで Integer (ここで私の誤診を訂正してくれたDanielに感謝！)。 明示的に型署名を与える（これはいずれにせよ標準的なやり方です）には Int に変更され、時間が 11.1秒
• で factorCount' を無駄に呼び出しています。 fromIntegral . しかし、修正しても変化はありません（コンパイラは賢いのです、ラッキー）。
• あなたが使用したのは mod ここで rem の方が高速で十分です。これにより、時間が 8.5秒 .
• factorCount' は、決して変化しない2つの余分な引数を常に適用しています ( number , sqrt ). Worker/Wrapperの変換で、次のようになります。

 $ time ./so
 842161320  

 real    0m7.954s  
 user    0m7.944s  
 sys     0m0.004s  

その通りです。 7.95秒 . 一貫して C言語ソリューションより0.5秒速い . を使用しない場合 -fllvm フラグを使用すると、まだ 8.182 seconds ということで、この場合もNCGバックエンドはうまくいっています。

結論 Haskellはすごい。

結果のコード

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
  where
  go candidate count
    | candidate > sqrt = count
    | number `rem` candidate == 0 = go (candidate + 1) (count + 2)
    | otherwise = go (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1

編集部：さて、ここまでで疑問点を解決していきましょう。

<ブロッククオート

質問1：erlang、python、haskellは、以下のものを使用すると速度が低下するのでしょうか？ それとも、任意の長さの整数値であれば問題ないのでしょうか？ MAXINTより小さいですか？

Haskellでは Integer よりも遅いです。 Int が、どの程度遅くなるかは、実行される演算に依存します。 幸いなことに（64ビットマシンの場合） Int で十分です。 移植性のために、私のコードを書き換えて Int64 または Word64 (C言語だけではありません。 long ).

<ブロッククオート

質問2：なぜhaskellはこんなに遅いのですか？コンパイラのフラグで それとも私の実装に問題があるのでしょうか？(後者はかなり ハスケルは私にとって七つの封印のある本なので、その可能性は高いです)。

質問3：これらを最適化するためのヒントを教えてください。 の実装を、私が要因を決定する方法を変えずに行うことはできますか？ より良い、より速い、よりネイティブな、など、どのような方法でも構いません。

上で回答した内容です。 その回答は

• 0) 経由で最適化を使用する -O2
• 1) 可能な限り高速な（特にアンボックス可能な）型を使用する。
• 2) rem ない mod (よく忘れられる最適化)と
• 3) ワーカー/ラッパー変換 (おそらく最も一般的な最適化)。

<ブロッククオート

質問4：私の関数実装は、LCOを許可していますか？ コールスタックに不要なフレームを追加しないようにするか？

はい、それは問題ではありませんでした。 よくぞ考えてくれました。