最近のDoubleArrayの性能 - 射撃しつつ前転 改DoubleArrayの性能に関して、最近は少し改善されているかも知れませんとあるので、具体的にどれぐらい改善されているのか、少し書いてみます。もちろん、現実逃避です。 まず、DoubleArrayがなんなのかというところから説明をします。DoubleArrayは、簡単に言うとTrieを実現するためのデータ構造の一種です。日本語ではダブル配列と呼ばれているようです。Trieに関しては横着プログラミング 第6回: chatty: 小うるさい端末あたりを読めば良いでしょうか。要するにTreeを表現するためのデータ構造です。使い道はいろいろありますが、辞書的なものに使われることが多いでしょうか。 Trieを単純に実現しようとすると、すごくたくさんメモリを使ってすごく速い実装をするか、速度を多少犠牲にしてメモリ消費量を削減するかの選択を迫られます。多くの場合はメモリを節約しないと使いものにならない
