charseq

common lisp library

charseq。
こことここで書いたことを実際に試しているライブラリ。
大体以下のようなことを目標としている。

  • 部分文字列の作成が容易かつ低コスト
  • 使用者はそれが部分文字列だということを意識せずに扱える
  • 大抵のケース*1で効率的な文字列操作が行われる ※ sbclでoptimize宣言を適切に指定した場合

メモを兼ねてソースコードも載せようかと考えていたが、上述のリンク先(github)でソースコードは公開されている*2し、最低限必要な情報もwikiに記載してあるので、今回は簡単な使用例とcreoleへの適用結果(速度の変化)を書くに留めることにする。

例

;;;; charseq-0.1.7

;; 作成
> (charseq:make "ソースコード")
--> #S(CHARSEQ:CHARSEQ :STR "ソースコード" :BEG 0 :END 6)

> (charseq:make "ソースコード" :start 2 :end 5)
--> #S(CHARSEQ:CHARSEQ :STR "ソースコード" :BEG 2 :END 5)

> (defvar *cs* *)

;; string = (simple-array character *)に変換
> (charseq:to-string *cs*)
--> "スコー"

;; 長さ
> (charseq:length *cs*)
--> 3

;; 文字参照
> (charseq:ref *cs* 1);;;; sbcl-1.0.37
--> #\KATAKANA_LETTER_KO ; = #\コ

;; each
> (charseq:each (char *cs* 'done)
    (format t "~A~%" char))
ス
コ
ー
--> DONE

;; 動的エクステントで作成
;;  - 構造体作成の際にヒープを消費しない(sbclのみ)
> (charseq:with-dynamic-extent (cs "ソースコード" :start 1)
    (print (charseq:to-string cs))
    (print (charseq:to-string cs 2))
    (print (charseq:to-string (charseq:sub cs 2)))
    'done)
"ースコード" 
"コード" 
"コード" 
--> DONE

creoleでの計時

以下、charseqの使用前(0.0.2)と使用後(0.1.1)のcreoleでの計時結果の比較(sbcl-1.0.37)。
※ 条件などは、前の時と同様。

UTF-8UTF-16LEEUC-JP
creole:string-to-octets (0.0.2)0.048s0.031s0.072s
creole:string-to-octets (0.1.1)0.048s0.023s0.054s
UTF-8では両者の結果は等しく、残りはcharseq使用版の方が速くなっている。
多分、0.0.2では各エンコード毎*3に個別に最適化を行っていたので、その力の入れ具合に差があった*4が、0.1.1では基本的な文字列操作に関する最適化をcharseqパッケージが担当したために、各エンコード関数間でのバラツキがなくなり、結果的にUTF-8以外での処理速度が向上したのだと思われる。
現バージョンのcharseqは、creoleでしか試していない(かつ、creoleの場合にはたまたま効果があった場当たり的な最適化コードも含まれている)ので他の場面で使った場合に、どの程度の効率的かは分からない。
ただ、charseqのようなパッケージを使うことで、以前の(冒頭の二つのリンク元の)記事で書いたような煩雑な処理*5をそのパッケージに任せられるというのはやはり楽なので、charseqをそのまま使うかどうかはともかく、今後はこの方向性で開発をしていきそうな気がする。

*1:charseqは、(simple-array character *)型の文字列を扱うことに特化している。
そのため、(not sipmle-array)あるいはbase-stringの副型であるような文字列を専ら対象とするような場面では、(主にcharseq構造体作成時の)コストが高くなる可能性がある。
ただし、速度が重要な場面ではそもそも(not simple-array)を使うべきではないと思うし、日本で書かれるプログラムでbase-stringが頻繁に使われることもないような気がするので、あまり大きな問題ではないと考えている。

*2:ソースコード自体もファイル一個で行数が150程度。各関数の定義にも特に難しいところはない。

*3:正確には、UTF-8とUTF-16系とその他のエンコード

*4:sbclのsb-ext:string-to-octets関数はUTF-8以外のエンコードに対する処理が比較的低速なので、それと対照することで最適化を行っていたcreoleも結果的にUTF-8以外への最適化が甘くなっていた

*5:部分文字列を作成する際の範囲チェックや効率性への配慮