2015-12-08-01-STL書籍の掲載コードをCL-STLで書いてみよう-22

>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-08-01-STL書籍の掲載コードをCL-STLで書いてみよう-22

最終更新日付：2015/12/08 01:00:00

STL書籍の掲載コードをCL-STLで書いてみよう-22

2015 年 12 月 08 日

まだちょいちょいと直すべきところがみつかる、CL-STL。そして裏では unordered系連想コンテナの実装に着手しはじめてしまってちょっと後悔中。それでもこの連載（？）は続ける。今回は、「第44項：アルゴリズムより同名のメンバ関数を優先して使おう」から。コードはちょっとだけ。

この第44項の趣旨は、「アルゴリズムと同名のメンバ関数がそのコンテナにあるならそっちを使え。効率がいいし、そのコンテナにより密着しているから」というものだ。例として、set の find メンバ関数と find アルゴリズムの比較が挙げられている。今回は面倒なので書籍のコードは掲載しない。

で、CL-STL では実際どうなの、という話になるわけだ。そういえば、先日 Lisp Meetup の後の食事で、「CL-STL って計算量は保持されているんですか？」という質問を頂いた。多少なりとも興味を持って頂けたことは正直嬉しかった。もちろん STL と同じ仕様で極力やっておりますよ？　今回のコードはそのごく簡単な例にもなるだろう。

今回やったのは、100万要素の stl:set を作成し、find メソッドと find アルゴリズムそれぞれの時間を測ることだ。まずは作成。愚直に 100万要素を突っ込んでみる。

(defparameter s (new stl:set #'<))
(stl:for (((i 0)) (< i 1000000) (incf i))
  (stl:insert s i))

で、まずは set のメソッドから。ランダムな値を検索する、というのを 100回繰り返す。

(time (stl:for (((i 0)) (< i 100) (incf i))
        (stl:find s (random 1000000))))

;Evaluation took:
;   0.000 seconds of real time
;   0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;   100.00% CPU
;   731,553 processor cycles
;   32,768 bytes consed

次に、まぁ同じような（ random 使ってるから同じとは言えない）ことを find アルゴリズムでやってみる。

(let ((i1 (stl:begin s))
      (i2 (stl:end   s)))
  (time (stl:for (((i 0)) (< i 100) (incf i))
        (stl:find i1 i2 (random 1000000)))))

;Evaluation took:
;  8.596 seconds of real time
;  8.595655 seconds of total run time (8.595655 user, 0.000000 system)
;  100.00% CPU
;  20,573,190,453 processor cycles
;  59,040 bytes consed

processor cycles で何倍の差があるかなんだけど、えぇと‥‥‥うん、計算もやってもらおう。

* (coerce (/ 20573190453 731553) 'single-float)

=> 28122.625

なんていうか、まぁそもそも勝負になっていないよね。本来であれば検索に使用する値は２つのコードで同一であるべきなのだけれど、『まぁいいか』というくらい差があるのでこんな感じでおしまい。

このシリーズのこれまでのエントリ

• 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項：アルゴリズムより同名のメンバ関数を優先して使おう

コメント

このページにコメントする

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

Copyright(C) 2005-2018 project-enigma.
Generated by CL-PREFAB.