Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

97 lines (69 sloc) 4.864 kb
コーディングテーマ: 赤黒木ベンチマーク
Groovy、Scala、JRubyの各言語で以下のベンチマーク値を取得し、比較する。
1) RBTreeMapクラスの実装
・RBTreeMapクラスは最低限以下の4つのAPIを実装する。
・RBTreeMap.newInstance() => RBTreeMap
新たにRBTreeMapクラスのインスタンスを生成する。
・RBTreeMap#put(String key, String value) => void/Object
keyに対してvalueを結びつける。keyがnullの場合例外。valueはnull許可。
既にkeyに別の値が割り当てられていた場合、valueで置き換える。keyの同
値性の意味はJavaのStringのものに従う。またkeyには順序性を期待できる
ものとする。順序性の意味はJavaのStringのものに従う。戻り値は未定義
で、何を返しても返さなくてもよい。
・RBTreeMap#get(String key) => String
keyに対して割り当てられている値を返す。keyがnullの場合例外。値が割り
当てられていない場合はnullを返す。
・RBTreeMap#height() => int
内部の赤黒木の最大の高さを返す。高さは、生成直後で要素数0の時に0、
後は、内部の赤黒木の全ての枝で黒の数を数えた際の、最大の数とする。
・引数および戻り値の型については、各言語における上記相当の型を扱えればよ
く、型をString相当に制限する必要はない。ただしkeyには、JavaのStringと
同じ意味の順序性が求められることに注意。また、height()の戻り値も、リテ
ラル数値と同値性を比較できる型であれば、intでなくなんでもよい。
・引数および戻り値のnullは、各言語のnull相当の値で構わない。
・RBTreeMapが格納できる要素数に上限があってもよい。ただしベンチマークの
ため、2**25個は格納できること。(2**25とか適当に書きましたが、繰り返し
ベンチマークを取り易い程度の個数に抑える予定です)
・RBTreeMapクラスのAPIに対してマルチスレッドからアクセスされた場合の挙動
は未定義。何が起こってもよい。ケアしなくてよい。してもよい。
2) 動作確認
・RBTreeMap.newInstance()を呼び、RBTreeMapをインスタンス化する。
・用意されたファイルを開き、全てを読み終わるまで以下を繰り返す。
・ファイルから1行読み込み、key、value、height文字列を取り出す。
・RBTreeMap#put(key, value)を呼ぶ。
※height文字列はRBTreeMap#height()と比較するための参考値とする。
・ファイルを閉じる。
・再度同じファイルを開き、全てを読み終わるまで以下を繰り返す。
・ファイルから1行読み込み、key、value文字列を取り出す。
・RBTreeMap#get(key)を呼び、valueと一致することを確認する。
・ファイルを閉じる。
用意するファイルフォーマットは、改行"\n"、区切り","、エスケープなしの簡
易CSVフォーマット。文字列にはUS-ASCIIの範囲の文字しか入っていないものと
する。
----
key,value,0[\n]
key2,value2,1[\n]
...
keyn,valuen,15[\n][EOF]
----
3) ベンチマーク
以下のベンチマークを行う前提とする。
・RBTreeMap.newInstance()を呼び、RBTreeMapをインスタンス化する。
・用意されたファイルを開き、全てを読み終わるまで以下を繰り返す。
・ファイルから1行読み込み、key、value文字列を取り出す。
・RBTreeMap#put(key, value)を呼ぶ。
・ファイルを閉じる。
・再度同じファイルを開き、全てを読み終わるまで以下を繰り返す。
・ファイルから1行読み込み、key、value文字列を取り出す。
・RBTreeMap#get(key)を呼び、valueと一致することを確認する。
・ファイルを閉じる。
上記の処理全体にかかる時間を計測しつつ、5回繰り返して実行し、ベスト値と
ワースト値を除いた3回の処理時間の平均を、各言語のベンチマーク値とする。
入力するファイルは、動作確認用のものと同じ。
4) ベンチマークの実施
各言語のソースコード、実行方法(パラメータ指定方法、専用オプション、言語
のバージョン、専用ブランチのビルド方法など?)を教えてもらい、私が同一マ
シンで実行した結果を用意します。当日用のグラフも適当に作ります。
GCが結果に影響するようであれば、適当にGCパラメータもいじるかもしれません。
早目にもらえれば、早目に計測結果をお渡しするようにします。
以上。
Jump to Line
Something went wrong with that request. Please try again.