C vs Python vs Ruby vs Haskell(無意味な処理deベンチマーク)
「Haskell入門以前」のネタバレになってしまいますが、[ [1,2,3],[4,5,6],[7,8,9] ]を受け取って、各要素を反転させた[ [3,2,1],[6,5,4],[9,8,7] ]を受け取り、その最後尾の要素の最後尾(このデータでは7)を表示する処理を作り、なるべく大きなデータを渡して実行時間を計測してみました。
(自分のPCでは4000x4000のデータを渡してます)
Haskellのコードは他の言語のコードとは全く違う発想で書かれています。どうして同じ結果になるかを考えてみたりすると関数型言語と手続き型言語の違いに気付くかも知れません。
(この辺が「Haskell入門以前」のネタバレ。気付けなかったら、「Haskell入門以前」と言う電子書籍がブクログのパブーより出てますので、読んでみて下さい)
まずは、各言語のコードを書きます。
#include
#include
#define N 4000
void reverse_i(int arry, int length)
{
int i,temp;
for(i = 0; i < length / 2; i++)
{
temp = arry[i];
arry[i] = arry[length - i - 1];
arry[length - i - 1] = temp;
}
}
void main(void)
{
int i, j, count = 1, **a = NULL;
a = calloc(N, sizeof(int));
for(i = 0; i < N; i++)
{
a[i] = calloc(N, sizeof(int*));
for(j = 0; j < N; j++)
{
a[i][j] = count++;
}
}
for(i = 0; i < N; i++)
{
reverse_i(a[i], N);
}
printf("%d\n",a[N - 1][N - 1]);
for(i = 0; i < N; i++)
{
free(a[i]);
}
free(a);
}
※Cは普通の配列だと、4000x4000はスタックが溢れるので、動的配列でヒープ領域に作成。
Python
n = 4000
a =
count = 1
for x in range(n):
a.append([])
for y in range(n):
a[x].append(count)
count += 1
list(map(lambda e: e.reverse(), a))
print(a[-1][-1])
N = 4000
given = [range(N * i + 1, N * (i + 1) + 1) for i in range(N)]
print([elem[::-1] for elem in given][-1][-1])
Ruby
n = 4000
count = 0
a = Array.new(n){Array.new(n){count += 1 }}
print a.map{|i| i.reverse}[-1][-1]
N = 4000
given = Range.new(0, N - 1).collect{|i| Range.new(N * i + 1, N * (i + 1)).to_a}
print given.map{|elem| elem.reverse}[-1][-1]
Haskell
mylist n = take n $ iterate (map (+n)) [1..n]
main = print.last.last.(map reverse) $ mylist 4000
m = 4000
main = print.last.last.(map reverse) $ map (\n -> let base = (n - 1) * m in [1 + base .. m+ base]) [1 .. m]
さてそれでは、それぞれの実行時間を前回作ったdifftimeコマンドで見てみましょう。
C言語
difftime mapreverse_c
>15996001
>0.083059s
Python
difftime python mapreverse.py
>15996001
>0.0740583s
Ruby
difftime ruby mapreverse.rb
>15996001
>2.5532892s
Haskell
difftime mapreverse_hs
>15996001
>0.0170152s
順位的には
1位 C言語
2位 Haskell
3位 Ruby
4位 Python
でした。
自分の書き方が悪いのか、Pythonが11秒台とかなり遅いです。
と言うか、実は、4000x4000と言うデータの数は、pythonの処理時間が基準になってます。
(こう書けば速くなるよ!と言うコメントお待ちしております)
C言語はさすがの速さです。ここまで速いと、ちょっとHaskellへの思いがぐらついてしまいます…。
Rubyは、スクリプト言語の割に検討している印象です。
Haskellは、さすがにPython/Rubyのスクリプト言語勢には勝っていますが、C言語には遠く及びません。
(でも、実はリストと相性の悪いreverseに大きいデータを渡すので、スクリプト言語とは言え、配列に負けるのでは?と思っていたので、杞憂に終わってよかった…)
しかし、2chと同じで半角スペースとTabは消えてしまうんですね…。全角スペースに直すのが面倒臭いです。
2012年11月15日追記
コメントで頂いたコードを採用した結果
1位 Python
2位 C言語
3位 Haskell
4位 Ruby
何と、コメントでもらったコードを使って、pythonはC言語を抜いてしまいました。
Rubyも、約1秒時間短縮できてます。
Pythonの速さの秘密はなんでしょう?
自分なりに考察してみました。
みんPyによるとPython2のrangeはその範囲を要素に持つリストを返していたそうですが、それでは無駄が多いのでxrangeと言うのがあったそうです。
これがpython3ではxrangeを廃止して、rangeに統一。その際、rangeはリストではなく、ジェネレータを返すようになったそうです。
(要するに機能はxrangeに統一して、名前はrangeに統一している?)
つまり、Pythonだけ、リスト。あるいは配列に相当するものを作っていないから、Cを超える速さを実現できたと言う事ではないでしょうか。
と言う訳で、ズルはいけないので(おい)ちゃんとリストを作るようにコードを変えさせてもらいました。
N = 4000
given = [list(range(N * i + 1, N * (i + 1) + 1)) for i in range(N)]
print([elem[::-1] for elem in given][-1][-1])
結果は
difftime python mapreverse.py
>15996001
>2.8304995s
Rubyより少し遅いという結果になりました。
ジェネレータの大切さが分かるコードでしたね。
どっかで見かけた気がするのですが、最近のC++規格にもジェネレータみたいなの無かったでしたっけ?
もしかして、C++で書いたらさらに最速記録を塗り替えられそうですかね?
いや、Haskellerな自分はもうここまででお腹一杯ですが。
まとめてみると、勝負の決め手は配列とリストと言うデータ構造の違いではなく、そういう構造をいかに作らずに処理をするか?が結果を左右した印象でした。
新参者のブログにコメント下さり、rokujyouhitomaさん、名無しさん、リスさん、methaneさん、本当にありがとうございました。
2012年11月16日追記
C言語版のバグ報告とHaskellのコードを頂けたので更新しました。
コメントで頂いたコードを採用した結果
1位 Haskell
2位 Python
3位 C言語
4位 Ruby
順位変動が激しすぎますw
ただ、コメント下さったhirataraさんが自白している通り、これもPython版同様ズルです。
print.last.lastのlast.lastを取り、全要素を表示するようにして、4000x4000だと見るのが大変なので3x3に変更して実行してみると・・・
[ [1],[4,3],[9,8,7] ]
と表示されます。
4x4にすると・・・
[ [1],[4,3],[9,8,7],[16,15,14,13] ]
どうも、nxnの各数字の最後のリストのみをリストにしているようですね。
元々は、冒頭に書いた通り、[ [1,2,3],[4,5,6],[7,8,9] ]を受け取って、[ [3,2,1], [6,5,4],[9,8,7] ]を返す関数でベンチマークしてて、数字が大きくなってくると表示処理の方が時間が掛かる様になって来たので、最後のリスト(または配列)の最後の要素で正しく動作してることを確認しつつ、処理時間を計測する。と言うのが本来の趣旨でした。
が、こうしてその処理に特化して無駄を省く手法が見れてとても参考になっています。
hirataraさん、素晴らしいコード、ありがとうございました。
2012年11月16日21時追記
順位は変わりませんが、hirataraさんのコードで4000と書かれたところをn = 4000として置き換えたら、ラムダ式の引数のnと被って、変なことになっていました><
hirataraさんのご指摘通り、被らないように今度はm = 4000として置き換えた所、m = 3に変えて、要素を全部表示させても、ちゃんと[ [3,2,1],[6,5,4],[9,8,7] ]と表示される事を確認しました。
にもかかわらず、0.0180367s→0.0170152sと若干高速になってます。
(誤差かも知れないですが、一応3回実行して、一番速かったタイムをここに掲載してます)
hirataraさん、閲覧に来て下さった方々、大変申し訳ございませんでしたm(_ _)m
あとは、methaneさんの方です・・・(ドキドキ)
こっちの方が、私が間違ってる率400%超えてるんですけど・・・
2012年11月18日追記
2日待ってもmethaneさんから返事がないので、このままのコード&順位で確定させて頂きます。
1位 Haskell
2位 Python
3位 C言語
4位 Ruby
ただ、range(N * i + 1, N * (i + 1) + 1) みたいなコードが速くなった言語に共通のアルゴリズムみたいなので、C言語も、こちらのアルゴリズムで書き直すと大幅に速くなる可能性を秘めている事も断っておきます。