2013-10-29-01-CL-STLの話 - project-enigma

2013-10-29-01-CL-STLの話

>> Site top >> weblog >> 月別アーカイブ >> 2013年10月のlog >> 2013-10-29-01-CL-STLの話

最終更新日付:2014/01/06 19:50:39


CL-STLの話

2013 年 10 月 29 日

以前書いたとおり、Common Lisp をがりがりと書いている。やっているのは CL-STL というライブラリの開発で、C++ 標準ライブラリの STL を移植するというものだ。

今年の夏くらいまでは、CLSTL という名前で開発をしていた。これはレキシカルクロージャ(だけ)を使ってコンテナから反復子、ファンクタまで実装したもので、アルゴリズムは関数で実装。全体としてほぼ完成していたのだが、いくつか理由があって CLOS を使って全面的に書き直すことになった。これが夏以降の話。

何故 CLOS で書き直すことになったかというと、理由は大きく3つある。レキシカルクロージャによる実装よりもパフォーマンスが良かったことと、STLヘッダごとに分割していたパッケージを CL-STL パッケージに統一するには総称関数による分配が必要だったこと。そして最後に、総称関数を最適化に使うことができそうだったことだ。これについて書いてみよう。

STL アルゴリズムは、通常2つの反復子でシーケンスを与えるが、それが何の反復子かはわからない。だから(当たり前だが)反復子のインターフェースを経由して処理を行うが、CLOS の総称関数であれば、例えば vector-iterator で特定化できるだろう。その場合、vector のイテレータから参照先の vector オブジェクト(のさらに内部の配列)にまで手を伸ばして高速に処理を行うことができる‥‥‥というわけだ。

これに気付いたため、最初に defun で作成していたアルゴリズムを全て総称関数に書き換えた。そして、とりあえずは vector についてだけ専用の高速アルゴリズム実装を追加した。複雑なアルゴリズムについてはまだ vector に特定化した実装はできていないが。

で、全体の進捗はどうかというと、(通常の)アルゴリズムは完成しており、コンテナはシーケンシャルコンテナのみほぼ完成で連想コンテナは手付かず。一日の中で使える時間は少ない。少しずつ。

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

 

 


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