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

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 08:49:04


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

2015 年 12 月 08 日

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

この第44項の趣旨は、「アルゴリズムと同名のメンバ関数がそのコンテナにあるならそっちを使え。効率がいいし、そのコンテナにより密着しているから」というものだ。例として、setfind メンバ関数と 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

 

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

 

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

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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