Hatena::ブログ(Diary)

しんちゃんの日記

2012-11-14

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入門以前」と言う電子書籍ブクログパブーより出てますので、読んでみて下さい)

まずは、各言語のコードを書きます。

C言語

#include <stdio.h>
#include <stdlib.h>

#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

何と、コメントでもらったコードを使って、pythonC言語を抜いてしまいました。
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言語も、こちらのアルゴリズムで書き直すと大幅に速くなる可能性を秘めている事も断っておきます。

rokujyouhitomarokujyouhitoma 2012/11/15 16:34 つ[PyPy1.9]
私のcpython2.7環境だと...
$ time python2.7 test.py
15996001
python2.7 test.py  1.11s user 0.31s system 99% cpu 1.427 total

pypay1.9...
$ time pypy1.9 test.py
15996001
pypy1.9 test.py  0.02s user 0.01s system 78% cpu 0.043 total

50倍早い! 実行コードはこちら。
>N = 4000
>given = [range(N * i + 1, N * (i + 1) + 1) for i in xrange(N)]
>print [elem[::-1] for elem in given][-1][-1]

名無しさん名無しさん 2012/11/15 16:35 Ruby は

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]

のように書けば速くなるのでは?

nshinchan01nshinchan01 2012/11/15 17:35 >rokujyouhitomaさん
コメントありがとうございます。
やはり、私の書き方が悪いようですね・・・
xrangeを使ってると言う事は、Python2ですね。
自分の環境ではPython3なので、3用に書き直して結果を反映させて見たいと思います。

linux環境では最初から実行時間計測用コマンドが有るんですね・・・
winだとtimeコマンドは時間設定コマンドになってて自作する羽目になったですよ

nshinchan01nshinchan01 2012/11/15 17:52 >名無しさん
コメントありがとうございます。
Rangeクラスもcollectメソッドの使い方も知りませんでした^^;
PythonはみんPyで、RubyたのしいRubyで勉強しながら書いたので、本当に最低限の知識未満です・・・orz
こちらも書いてみて、速い方を掲載したいと思います。

HaskellもPythonの内包表記の書き方を参考にすれば、まだ速くなる余地があるかも・・・?

リスリス 2012/11/15 18:01 配列とリストは違うデータ構造ですよ。

methanemethane 2012/11/15 18:10 http://methane.hatenablog.jp/entry/2012/11/15/180948
Python風の書き方にしてみました。参考にしてください。

methanemethane 2012/11/15 18:12 あと、スーパーpre記法というのを覚えると、全角スペースとかにしなくてもコード貼れます。はてブロに移行してしまったのでうろ覚えですが、

>|python|
コード
||<

こんな感じだったと思います。

nshinchan01nshinchan01 2012/11/15 20:21 >リスさん
違うデータ構造なのは理解していますが、その言語で普段使っているデータ構造での比較がしたかったので、あえてこうなってます。
と言うか、まだHaskellで配列を使ったことがないのが本音ですw
一応作り方とかはググってはいるんですが・・・結局、最低一回はリストを生成しないといけないらしいので、今回の処理ではあまり必要性を感じなかったというのもあります。

>methaneさん
速いですね。
今回はrokujyouhitomaさんのコードとの速度差が僅かだった事と、コードの短さからrokujyouhitomaさんのコードを採用させて頂きましたが、またコメント頂けると幸いです。
と言うか、コメント頂ける様に私の方が頑張らなければ。

スーパーpre記法と言うの、私、気になります!!

hiratarahiratara 2012/11/15 22:30 こんにちわ。Cのコード、セグフォしてます。sizeof(int *)で確保しないと。
> a = calloc(N, sizeof(int));

以下のコードでHaskellがTOPになりますが、これは反則ですね :p
main = print.last.last.(map reverse) $ map (\n -> let base = (n - 1) * 4000
in [1 + base .. 4000 + base])
[1 .. 4000]

nshinchan01nshinchan01 2012/11/16 01:21 >hirataraさん
参考にしたサイトを見ても同様に書いてました・・・orz
どうやら、寝ぼけていたみたいです・・・

Haskellのコード、こちらで計測して更新しておきました。
まあ、反則といえば反則ですが、Pythonの方も反則のコードでタイム取っていますので・・・
むしろ、無駄なデータをどんどん枝刈りしていく皆さんのコードはとても参考になります。

methanemethane 2012/11/16 01:49 私のコードはもともと list(range()) していたのでズルではないです。
上記のコードも、全体を main() 関数の中に入れてそれを呼び出す、配列の反転をするときに in-place にする (for e in given: e.reverse()) ことで速くなります。

hiratarahiratara 2012/11/16 10:31 > なので3x3に変更して実行してみると・・・
> [ [1],[4,3],[9,8,7] ]
> と表示されます。

ん? さすがにそれはないかと・・・こちらでは [[3,2,1],[6,5,4],[9,8,7]] となってます。反則な点は、遅延評価のためにmatrixの生成やreverseをまったくしてないだろうという点でした(本当にそうかどうかはあんまり検証してないですが)。

nshinchan01nshinchan01 2012/11/16 18:04 >methaneさん&hirataraさん
ええええ!?
でも、お二人から頂いたコードの[-1][-1]やlast.lastを消して、N=3に変えただけなんですが・・・

念のため、私が書き換えた時のコードをこちらに書いておきますので、そちらの思っているコードと違いましたら、ご指摘お願いします。
(特にPythonは慣れてないので変なイジリ方してるかも)

python

N = 3
given = [range(N * i + 1, N * (i + 1) + 1) for i in range(N)]
print([elem[::-1] for elem in given])

Haskell

n = 3
main = print $ (map reverse) $ map (\n -> let base = (n - 1) * n in [1 + base .. n + base]) [1 .. n]

nshinchan01nshinchan01 2012/11/16 18:23 あ、PythonはPython3ですのでお間違えの無きようお願い致します。
なので、methaneさんの使うPython2からPython3にする際に変な書き方をした可能性は大です。

私の環境では

[range(3,0,-1),range(6,3,-1),range(9,6,-1)]と表示されるんですが…

hiratarahiratara 2012/11/16 20:16 nが被ってるのでシャドウイングされちゃってます><

nshinchan01nshinchan01 2012/11/16 20:55 そ、そう言う事だったですかー!!!
と言う事で、ブログの方もコードと実行時間、併せて訂正させて頂きました。
大丈夫です。コード変更後もhirataraさんの宣言通りトップを維持してます。

nshinchan01nshinchan01 2012/11/16 21:09 >methaneさん

>と言う訳で、ズルはいけないので(おい)ちゃんとリストを作るようにコードを変えさせてもらいました。

>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

methaneさんから頂いたコード

50倍早い! 実行コードはこちら。
>N = 4000
>given = [range(N * i + 1, N * (i + 1) + 1) for i in xrange(N)]
>print [elem[::-1] for elem in given][-1][-1]

冷静に読み返してみると、リスト作る様に変更させて頂いたコードがまさに、methaneさんから頂いたコードを素直にPython3に書き直したコードですね・・・
ええと・・・methaneさん、遅くなりますが、リスト作る方に差し替えて良いのでしょうか?

名無し名無し 2012/11/19 11:04 ブログを見比べていたのですが、methane さんのコードは
range(N * i + 1, N * (i + 1) + 1)
はつかっておらず、代わりに
for c in range(1, 1+n**2, n):
a.append(list(range(c, c+n)))
としているようです。
手元の環境で比較すると methane さんのコードの方が速いようです。
range() に step を指定することで、掛け算の回数が減って高速化しているのかもしれません。

気になって、ruby 側のコードも step を指定してみたのですが、速度は変わらないようでした。
N = 4000
given = Range.new(1, N ** 2).step(N).collect{|i| Range.new(i, i + N - 1).to_a}
print given.map{|elem| elem.reverse}[-1][-1]
この違いは何でしょうかね。

khibinokhibino 2012/11/19 11:12 Haskell ですが、 m = 4000 を m = 4000 :: Int のようにすると、さらに速度アップが期待できます。

nshinchan01nshinchan01 2012/11/19 18:30 >名無しさん
残念ながら(?)それはすでに検証済みです。
ズル無しのリストを生成するコードではPythonの中では一番速く、Rubyより高速になりますが、この記事でHaskellに次いで2位に君臨しているリストを全く作らないバージョンよりは遅くなってしまいます。
どうも、Pythonはリストを生成する際に大分コストが掛かるようです。

本当、Rubyはどうして速くならないのでしょうね・・・
Pythonとアルゴリズムは同じに見えるのですが・・・

>khibinoさん
これ以上、覇道を歩ませますかw
確かに、Integer型よりInt型の方が速いですし、4000程度、32bitで表現できますものね!
すぐに検証して結果を反映させてみます。

nshinchan01nshinchan01 2012/11/19 18:34 >khibinoさん
残念な結果です。
Int指定したら、逆に僅かに遅くなりました。
まあ、最適化オプション付けてるので多分最初からInt指定扱いされていたのでしょう。
誤差程度の差ですし。

khibinokhibino 2012/11/21 10:50 なんと! 問題サイズを大きくして手元で試したら (m = 40000, -O2)、少なくとも 1割ぐらいは速くなっているように見えたのでイケると思ったんですが。 あと、私の予想では defaulting で Integer にはなるけど Int にはならないと考えていました。最適化で Integer を Int にするようなものでもあるんですかね。

khibinokhibino 2012/11/21 11:03 って、ちゃんと Integer の話も書いてあるじゃん。よく読んでいなくてすいません。なんか釈迦に説法みたいになってしまいました。 しかし、こういう最適化って難しいですね。

nshinchan01nshinchan01 2012/11/21 18:03 >khibinoさん
いえいえ、自分なんてHaskellについて分からないことばっかりです。
そうですか、さらに大きなデータだとInt指定は効いてきますか・・・
と言うか、-O2とかって効いているんでしょうか?
gccやVisualC++だと-O3や/Oxで最適化するんですが、Haskellのコマンドヘルプ読む限り-Oしかないみたいで、どっかで-O2とかやっても数字部分は無視されるって読んだ気がするんですよね…

khibinokhibino 2012/11/22 10:48 GHC の中をのぞいてみた感じだと、 -O2 にしないと有効にならない最適化もあるようです。意味のあるレベルは 0,1 2 のどれかみたいです。マニュアルページにもユーザーズガイドにも -O2 は載っているように見えます

nshinchan01nshinchan01 2012/11/22 13:19 それは申し訳ないです・・・
英語は本当に苦手で、コードは世界共通さ!!なノリと経験則でホグルぐらいしか英語のページを読まないもので・・・
ghcの--helpも、gccみたいにOの後に0を付けたらどう最適化する。1を付けたら・・・と書いててくれたら、良いのに・・・と、愚痴って見る。

会社から戻ったら、O2でもう一度やって見ます。

nshinchan01nshinchan01 2012/11/22 18:02 >khibinoさん
結果報告。
-O2にしても、やっぱり変わらず、少し遅くなると言う結果でした。
うーん・・・却って、Int指定が最適化の邪魔でもしているんでしょうかね・・・

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証