04/27

(0:45) 昨日は自室に帰ったとたんに疲れのあまり寝てしまって日記が書けなかった。

まあ、特に何かしたというわけでもないけど。

(結婚と人生の両立が急務)

 

今日は久しぶりに darts-clone-java のソースを引っ張り出して見ていた。

どうもこれについては頭が整理されていなくて、無駄にいろいろ考えてしまう。

 

何が難しいか。

まず、darts-clone-java では、バイト配列の形式で文字列を扱うようにしている。

それには、いろいろ事情がある。

 

まず、darts-clone を UTF-16 で扱うと効率が悪くなる。

Unicode でも大丈夫みたい - やた@はてな日記

大丈夫は大丈夫でも、いいところがない。

 

ところで、元の darts-clone では、格納する文字の型が何ビットのものでもいいようになっている(テンプレートを使っている)が、Java ではそれができない。

というのは、Javaジェネリックではプリミティブ型が使えないからだ(プリミティブ型の配列は使える)。

だから、文字を表す型として、char(16ビット)か byte(8ビット)を選ばないといけない(char を選ぶ場合は文字列に String が使えるが、byte を使う場合は byte[ ]になる)。

この場合、Java との親和性を考えたら前者だが、効率から言うと後者だ。

 

しかし、効率よりも Java との親和性を優先するというなら、すでに優れたライブラリはいろいろある。

Komiya Atsushi さんの darts-java や、Takao Nakaguchi さんの trie4j などだ。

 

darts-java はシンプルな darts の移植、trie4j は総合的な trie ライブラリ。

特に trie4j ではパトリシア木からダブル配列、LOUDS などがものすごく綺麗に実装されていて、わかりやすさという意味では群を抜いている。

 

しかし、効率を考えると、やたさんの変態的な実装のほうがいいには決まっている。

特に、キーに対応する値を格納しない(キーワードリンクを張る場合などにはよくあることだ)場合などには、DAWG を使っていることもあり、非常にコンパクトになる。

この「効率」という長所をフルに生かすとなると、byte 型一択だ。

 

だが、そうすると今度は使うのが難しくなる。

これもまた複雑な事情がある。

 

darts-clone の構築時には、ソート済みのキーのリストを渡す。

内部では byte[ ][ ] を使うにせよ、List<String> のラッパーメソッドでもかぶせて、人間にやさしくしたいところだ。

だが、それはうまくいかない。

 

というのは、String と byte[ ] ではソート順が変わるからだ。

UTF-8 はよくできているので、UTF-32UTF-8 ならソート順は変わらない(はず)。

しかし、UTF-16 というのは実にファッキンなもので、「文字なんて 16 ビットでいけるっしょ〜(ヘラヘラ)」という時代の残滓を引きずっている感じで、BMP 外への対応がいかにもとってつけたような感じだ。

まあとにかく、UTF-16 では BMP 外の文字でソート順が変わってしまう。

これはダブル配列の構築には致命的だ。

 

というわけで、ユーザのほうで byte[ ] をソートしないといけない。

(内部でソートするという手もあるが、上で書いたように効率を重視しないと意味がないのでやらない)

しかし、byte[ ] の Comparator なんてないので(Guava にはあるらしい。参考: 

sorting - Java Comparator for byte array (lexicographic) - Stack Overflow )、その辺をうまくやってもらわないといけない。

 

さらに言うと、CommonPrefixSearch などでも String のメソッドを用意するのはまずい。

というのは、String のメソッドを用意してしまうと、それが何も考えずに使えるもののように思われてしまいそうだが、そうはならないからだ。

上で書いたように、内部では byte[ ] を使うので、呼び出しのたびに変換する必要がある。

しかし、これは CommonPrefixSearch の典型的なユースケースを考えると、非常にまずい。

 

CommonPrefixSearch というのは、「めっちゃ長い文字列を、開始位置をずらしながら繰り返し渡す」というやり方で文字列に含まれるキーワードなどを探すというのがよくある使い方だ。

String のメソッドを用意してしまうと、そういう使い方をされてしまう可能性があるが、それだとめっちゃ長い文字列が毎回 byte[ ] に変換されるという悪夢が起こってしまう。

もちろん効率は最悪だ。

そんな可能性は前もって防いでおいたほうがいい、つまり String のメソッドなんかないほうがいいということだ。

 

(しかし、現在のバージョンではそのメソッドを用意していて、さらにテストもそちらのをメインに使っているので、書き換えないといけない。めんどくさい)

 

ほかに気が進まない原因としては、まあゲスい発想だけど、技術力アピールにならないというのがある。

確かに移植は面倒だったけど、C++Java をそこそこ知っていればできる単純作業だ。

クリエイティビティのかけらもない。

それに、上でさんざん書いたように非常に使いにくく、よっぽど効率を重視したい場合でもなければ使われないだろうし、使うことを推奨したくもない。

 

そもそも、なんでわざわざ Java に移植するのか。

効率を求めるなら、ネイティブのライブラリを呼び出せばいいんじゃないか。

 Java でやるなら、効率はある程度あきらめるのがいいんじゃないか。

どちらも至極もっともだ。

 

しかし、Java 界隈にはできるだけ Java で完結させるという文化のようなものがある(気がする)。

これは、Java のパフォーマンスがかなりいい(わざわざネイティブのものを使いたくなるほどに遅くない)ということもあるんじゃないかと思う。

 

かといって、Java だから効率をあきらめられるかというと、その辺はいろいろあって結局性能が求められることになったりする。

そうすると、どっかの企業内で darts-clone を再移植するという悲劇が起こらないとも限らない。

それくらいなら、自分の移植版を公開して悲劇のコストを下げたほうがマシじゃないだろうか。

 

ところで、パフォーマンスがいいからという理由でわざわざ darts-clone の Java 移植版を公開するとなると、そのパフォーマンスの良さを計測しないと説得力がない。

しかし、上に挙げたような諸事情によって(アピールにならない・あまり使われないと予測できる)、そこまでのモチベーションが湧かない。

それぐらいなら公開しないでおいたほうがいいんじゃないかと思えてしまう。

 

でも、やっぱり悲劇を和らげるためには、こんなものでも一応公開しておいたほうがいいんじゃないかとも思う。

ジレンマだ。

 

まあ、ここに書いたような諸事情についてブログで言い訳しながら、一応公開だけはしようかな。

広告を非表示にする