2015-12-22-01-STL書籍の掲載コードをCL-STLで書いてみよう-25
>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-22-01-STL書籍の掲載コードをCL-STLで書いてみよう-25
最終更新日付:2015/12/22 01:00:00
STL書籍の掲載コードをCL-STLで書いてみよう-25
2015 年 12 月 22 日
次いこう。「第46項:アルゴリズムのパラメータとして関数の代わりに関数オブジェクトの使用を考えよう」から。もう何度も書いている、ファンクタの性能のお話。
Effective STL のこの項で説明されているのは、要するに「アルゴリズムに渡すならファンクタ。通常そっちの方が速い。」ということだ。理由はインライン展開。例として挙げられているのは以下 のようなコード。std::greater を使ったモノと、
std::vector<double> v; //... std::sort( v.begin(), v.end(), std::greater<double>() );
もうひとつは関数(ポインタ)を渡す場合だ。こっちはポインタ渡しなので関数本体が(インライン宣言されていても)インライン展開されず、結果として関数オブジェクトを渡した方が速くなる‥‥‥と。
inline bool doubleGreater( double d1, double d2 ) { return d1 > d2; } //... std::sort( v.begin(), v.end(), doubleGreater );
当然というかなんというか、CL-STL ではこのへんの事情は大きく異なる。Common Lisp にはテンプレートというものがなく(マクロはあるんだけど)、CL-STL は総称関数とクラスをベースに作成されているからだ。そんなわけで、「CL-STL では関数を渡した方が通常は速い」という残念な話になる。というか、少なくともファンクタの方が速いということにはならない。それを説明するために作成したのが以下のコード。
(let ((v (new stl:vector 1000000))) (stl:generate (stl:begin v) (stl:end v) (lambda () (random 1000000))) (time (stl:sort (stl:begin v) (stl:end v) #'>)))
これは 100万要素のランダムな整数値シーケンスを作成し、それをソートする時間を測るものだ。先の Effective STL の書籍にあわせて降順ソートにしている。一方、以下は同じことを stl:greater で行なうモノだ。
(let ((v (new stl:vector 1000000))) (stl:generate (stl:begin v) (stl:end v) (lambda () (random 1000000))) (time (stl:sort (stl:begin v) (stl:end v) (new stl:greater))))
では、最初に #'> を使ったコードの実行結果を。安直に、『10回動かして一番成績の良かったモノ』を掲載している。
* (let ((v (new stl:vector 1000000))) (stl:generate (stl:begin v) (stl:end v) (lambda () (random 1000000))) (time (stl:sort (stl:begin v) (stl:end v) #'>))) ; => Evaluation took: ; 1.160 seconds of real time ; 1.154407 seconds of total run time (1.154407 user, 0.000000 system) ; 99.48% CPU ; 2,775,723,210 processor cycles ; 0 bytes consed
一方、stl:greater を使ったコードは以下のような実行結果になった。こちらも『10回動かして一番成績の良かったモノ』を掲載。
* (let ((v (new stl:vector 1000000))) (stl:generate (stl:begin v) (stl:end v) (lambda () (random 1000000))) (time (stl:sort (stl:begin v) (stl:end v) (new stl:greater)))) ; => Evaluation took: ; 1.590 seconds of real time ; 1.591210 seconds of total run time (1.591210 user, 0.000000 system) ; 100.06% CPU ; 3,805,356,700 processor cycles ; 0 bytes consed
こんな感じで、ファンクタを使った方が 1.37 倍遅いことがわかる‥‥‥と、ちょっと待てよ。stl:greater ってデフォルトで #'operator_> を使うんではなかったっけ? だとすれば、#'> を使うようにすればもちっとマシな勝負になるのではなかろうか? というわけで以下のようにしてみた。
* (let ((v (new stl:vector 1000000))) (stl:generate (stl:begin v) (stl:end v) (lambda () (random 1000000))) (time (stl:sort (stl:begin v) (stl:end v) (new stl:greater #'>)))) ; => Evaluation took: ; 1.201 seconds of real time ; 1.201207 seconds of total run time (1.201207 user, 0.000000 system) ; 100.00% CPU ; 2,891,532,693 processor cycles ; 0 bytes consed
うーん、ビンゴ。直接関数 #'> を渡した最初の例と比べても 1.04倍遅いだけ。これならなんとか性能面で「ファンクタクラスは使わない方がいい」とまで言われなくてすむかもしれない。とはいえ、ラムダ式を直接書いた方が圧倒的に簡単なので、問題はそこだよね。どうしても値コピーの挙動が必要なファンクタを作成する場合だけ、かな。
というわけで、本日はこれにておしまい。第46項について書きたかったことはこれくらいだ。そして、実に3ヶ月にわたって続けてしまった『Effective STL 掲載コードを CL-STL で書いてみよう』という試みもこれでおしまい。おつかれ自分。
このシリーズのこれまでのエントリ
- 2015-09-19 - 第47項:書き込み専用コードの作成は避けよう
- 2015-09-20 - 第9項:消去オプションは注意して選択しよう
- 2015-09-22 - 第9項:消去オプションは注意して選択しよう - 2
- 2015-09-28 - 第9項:消去オプションは注意して選択しよう - 3
- 2015-09-30 - 第14項:reserve を使って不必要な割り当てを避けよう
- 2015-10-01 - 第17項:余分な容量を取り除くには「swap技法」を使おう
- 2015-10-09 - 第27項:コンテナのconst_iteratorをiteratorに変換するには、distanceとadvanceを使おう
- 2015-10-12 - 第5項:単一要素メンバ関数より範囲メンバ関数を使おう
- 2015-10-14 - 第30項:出力先範囲の大きさを確認しよう
- 2015-10-16 - 第31項:ソートの選択肢を知っておこう
- 2015-10-17 - 第31項:ソートの選択肢を知っておこう - 2
- 2015-10-23 - 第32項:本当に削除したい場合は、remove風アルゴリズムの後にeraseを使おう
- 2015-10-25 - 第33項:ポインタのコンテナには注意してremove風アルゴリズムを使おう
- 2015-10-28 - 第34項:ソート済み範囲を必要とするアルゴリズムに注意しよう
- 2015-10-30 - 第36項:copy_ifの正しい実装について理解しよう
- 2015-11-03 - 第37項:範囲に関する要約情報を取得するには、accumulateまたはfor_eachを使おう
- 2015-11-05 - 第37項:範囲に関する要約情報を取得するには、accumulateまたはfor_eachを使おう - 2
- 2015-11-24 - 第39項:述語を純粋関数にしよう
- 2015-12-02 - 第40項:ファンクタクラスを変換可能にしよう
- 2015-12-03 - 第43項:独自に作成したループよりアルゴリズムの呼び出しを優先して使おう
- 2015-12-04 - 第43項:独自に作成したループよりアルゴリズムの呼び出しを優先して使おう - 2
- 2015-12-08 - 第44項:アルゴリズムより同名のメンバ関数を優先して使おう
- 2015-12-17 - 第45項:count、find、binary_search、lower_bound、upper_bound、およびequal_rangeの違いを理解しよう
- 2015-12-21 - 第45項:count、find、binary_search、lower_bound、upper_bound、およびequal_rangeの違いを理解しよう - 2
- 2015-12-22 - 第46項:アルゴリズムのパラメータとして関数の代わりに関数オブジェクトの使用を考えよう
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2021 project-enigma.
Generated by CL-PREFAB.