DoubleArray(3-2): キーのサイズ縮小(or string型の利用)
今までのDoubleArrayの実装では、当然のように(vector (unsigned-byte 8))をキーとして利用してきた。
文字列(キー)を扱う場合は、1byte(=8bit)を単位として扱うのが自然なので、悪くはない(むしろ良い?)とは思うのだが、2byte以上を単位として扱うのも、それはそれで利点があるのではないかと思う。
例えば、文字列を2byte単位で扱う場合、以下のような利点があるのではないかと思う。 ※ 思いっきり憶測
- BASE(及びCHECK)配列のサイズが小さくなる
- DoubleArrayの場合、その実装が#xFF分木から#xFFFF分木になったとしても、(リストによる実装と同様に)余計な空間を消費することがない。
- そして、キーの長さは1/2になるために、各キーごとに必要な(BASE・CHECK配列の)ノード数は少なくなり、BASE配列全体も小さくなる。
- ただし、各キーの共有可能な部分は減るので、全体のサイズが単純に1/2になることはない。(後、TAIL配列との関係とか...)
- 検索速度が速くなる
- キーの長さが半分になるので、検索時に必要なループ回数も(だいたい)半分となる。
- ただし、1byte配列から2byte配列への変換コストがかかる場合は、そのコストのために全体としては遅くなる可能性もある。
で、今回は特に、上に挙げた利点の内の、前者(サイズ縮小)の方を試してみることにする。
実装方法(?)
上では、「キーを1byte配列として扱っていたのを2byte配列としたら...」というように書いたが、これをそのまま実装するのは面倒なので、今回はcommon lispのstring型をキーとして利用することにする。
今までのDoubleArrayの実装では、引数として渡されたstringを、一旦(vector (unsigned-byte 8))に変換して、挿入や検索を行っていた。
その主な理由は、stringの要素(character)のコード表現が1byte以上となる可能性があるためだったのだが、既に書いたようにDoubleArrayが2byte以上も扱えるのならば、わざわざ一度byte列に変換する必要もなく、stringをそのまま利用することができる。
加えて、日本語を含む大抵のstring型は、以下のように(vector (unsigned-byte 16))にマップできるので(※sbclの場合)、2byte配列だとして考えてもそれほど問題はない。
> (type-of (map '(vector (unsigned-byte 16)) #'char-code "日本語")) --> (SIMPLE-ARRAY (UNSIGNED-BYTE 16) (3))
実装
DoubleArray(2): 挿入速度改善での実装をベースとして使う。
修正を加えた箇所は以下の通り*1。
;; 最大値を変更 ;; (sbclの場合は)characterの最大値は#x110000だが、それだと挿入速度が遅くなりすぎるので、 ;; とりあえず#xFFFFとした(ほとんどの日本語はこの範囲で扱えたはず...)。 (defconstant MAX-CODE #xFFFF) ;;; struct (defstruct (double-array (:conc-name da-)) (base (make-array 32 :element-type 'fixnum :initial-element NULL)) (chck (make-array 32 :element-type 'fixnum :initial-element NULL)) ;; tailの要素はcharacter型に変更 (tail (make-array 32 :element-type 'character :adjustable t :fill-pointer 1))) ;; 文字列->byte列への変換は必要なくなったので、この名前は適切ではないが、 ;; 変更箇所を減らすために、関数名はそのままにする。 ;; (code-char EOS)を末尾に付けたstringを返す (defun eos-terminated-octets (octs &aux (len (length octs))) (adjust-array octs (1+ len) :initial-element #.(code-char EOS))) ;; 以下の二つの関数は、 ;; /=を使っていたところを、char/=を使うように変更 (defun common-prefixes (o1 start1 o2 start2) (do ((i start1 (1+ i)) (j start2 (1+ j))) ((char/= @o1#i @o2#j) (coerce (subseq o1 start1 i) 'list)))) (defun tail=(octs start tail-start &aux (len (length octs))) (do ((i start (1+ i)) (j tail-start (1+ j))) ((= i len) t) (if (char/= @octs#i @*tail*#j) (return nil)))) ;; これ以降の関数は、 ;; 1byteのコード値を使っていたところを、 ;; 適宜(char-code 文字)を使うように変更 (defun get-next (code node) (+ @*base*#node (char-code code))) ;;; (defun set-node (code prev x &aux (next (+ (char-code x) (char-code code)))) ;;; (allocator:alloc next) (setf @*base*?prev (char-code x) ;;; @*chck*?next prev) next) (defun make-char-code (#1=char-or-code) ;;; (if (characterp #1#) (char-code #1#) #1#)) ;;; (defun x-check (set) (setf set (mapcar #'make-char-code set)) ;;; (let ((x (allocator:x-check set))) @*chck*?(+ x (apply #'max set)) (code-char x))) ;;; (defun modify-nodes (current node codes &optional c &aux (old-base @*base*#node)) (let ((new-base (char-code (x-check (if c (cons c codes) codes))))) ;;; (setf @*base*#node new-base) (setf codes (mapcar #'make-char-code set)) ;;; (dolist (code codes) (let ((old (+ old-base (char-code code))) ;;; (new (+ new-base (char-code code)))) ;;; (shiftf @*base*?new @*base*#old NULL) (shiftf @*chck*?new @*chck*#old NULL) (allocator:free old) (allocator:alloc new) (when (plusp @*base*#new) (setf *chck* (nsubstitute new old *chck* :start (1+ @*base*#new) :end (min (length *chck*) (+ @*base*#new MAX-CODE))))) (when (and (/= current node) (= current old)) (setf current new))))) current)
以上。
この実装では、挿入速度が極端に遅くなるが、それ以外は特に1byte配列からstringに変換したことでの問題はなさそうだ。
比較
キーとしてstringを使った場合と、utf-8エンコードの(vector (unsigned-byte 8))を使った場合、euc-jpエンコードの(vector (unsigned-byte 8))を使った場合の、BASE配列サイズを比較する。
結果
キーの型 | 挿入数 | (キーの)平均サイズ | BASE配列サイズ*2 |
string | 5万 | 9.68 | 104,924 |
utf-8エンコードの(vector (unsigned-byte 8)) | 5万 | 22.34 | 168,438 |
euc-jpエンコードの(vector (unsigned-byte 8)) | 5万 | 16.02 | 136,123 |
やはり、BASE配列のサイズはstringを使ったものが一番小さくなっている。
common lispの場合は、一度byte配列にエンコードせずに、stringをそのまま使えるというのも利点*3だと思うので(本当に?)、この方法は(改良の必要はあるが)使えるかもしれない。
追記(2009/10/06)
この記事を書いた後に、実際に上述のアイディアを(C++で)試してみたが、結局使えないことが分かった。
理由は下記の通り。
・速度向上? => 確かにキーの長さは短くなるので、その点では速くなっているようだが、キーを多バイトずつ扱うためのコストのせいで、結局総処理時間は長くなってしまった(試した限りでは、1.2倍くらい)。
・サイズ縮小? => 確かにサイズは縮小できるのだが、これを使うよりはこっちで試した方法の方が、縮小率が良かった。かつ、この二つの方法は両立しないので、それなら後者を使った方が良い。
*1:tail配列のelement-typeを(unsigned-byte 16)にして、make-octets関数内でstringの各要素をchar-codeでmapするようにすれば、こんなにいろいろ修正しなくても良かったのでは、と修正が終わってから気がついた。
*2:末尾の未使用領域は除いている
*3:追記(2010/03/23): 実際上は、このメリットが一番大きいように思う。最近作成したJavaの形態素解析器では、単語の辞書引きに使用しているDoubleArrayを、この考えを反映して(Javaにとって自然な)2byte(UTF-16)単位でキーを扱うよう実装した。そのおかげでキーの検索部分はかなり素直なコードとなった。