Double Array 実装してみた - 木曜不足今作りかけのもので、素性(文字列片)を格納するのに Trie を使っていたのだけど、50万件を超えたあたりからメモリに載らなくなってきて。 まあ dict を使っためちゃめちゃナイーブな実装だったので、そろそろダメかなあとは思っていたんだけど(苦笑)。 というわけで、それよりきっと省スペース＆きっと高速だろうと期待して Double Array を Python で実装してみた。 参考にしたのは WEB+DB Press vol. 64 の徳永さんの記事。 現時点での実装がこちら。 https://github.com/shuyo/iir/blob/master/trie/da.py ソート済みのテキスト列を与えると、Double Array を構築。 get を呼び出すと、最初に与えたテキスト列の中でのキー文字列のインデックスを返す。 シンプル機能。 trie = da.DoubleAr
