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項について書きたかったことはこれくらいだ。そして、実に３ヶ月にわたって続けてしまった『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 - 第５項：単一要素メンバ関数より範囲メンバ関数を使おう
• 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-2019 project-enigma.
Generated by CL-PREFAB.