sileのブログスマートフォン用の表示で見るsileのブログこの広告は、90日以上更新していないブログに表示しています。目的は六回目で作成したtrieをベースとし、検索速度を向上させること。最初に結果から載せる。入力データや計測方法等は七回目のそれらに準拠。3.35106slouds-trie-less-nodeおよびlouds-trie-node-optが今回の追加分。(今回の入力データでは)ベースとしたlouds-trie-tailに比べて、検索に要する時間が2/3程度に短縮されている。louds-trie-less-node上で書いた通りlouds-trie-less-nodeは、六回目に作成したlouds-trie-tailをベースとしている。louds-trie-tailでは、各キーにユニークな末尾文字列を(ノードとして保持する代わりに)TAIL配列に格納していた。兄弟がいない)ノードがtrie木上から除去されることになるので、総ノード数を減らすことが可能となる。ノード数が減ると、コストが高いselect1(これはノードの子ノードを取得する際に必要)の呼び出しも減るので、結果検索速度が速くなる*1。louds-trie-less-nodeは、louds-trie-tailでのTAIL配列利用を一般化しており、末端に続くかどうかに関係なく全ての無分岐ノード(に対応する文字)をTAIL配列*2に格納するようになっている。することで、louds-trie-tailよりもさらにtrieに必要なノード数を抑えることが可能となり、結果的に検索速度も向上することが期待できる*3。参考までに、louds-trie/louds-trie-tail/louds-trie-less-nodeのそれぞれで、wiki.titleファイル*4に含まれるキーセットをtrieとして表現する場合に必要なノード数を載せておく。740万ノードlouds-trie-less-nodeの実装。louds-trie-tailから変更がある箇所のみ。TAIL配列用のID。tail;};#endiflouds-trie-less-node-optlouds-trie-less-node-optは、基本louds-trie-less-nodeと同じだが、キー検索関数に以下の二つの変更が施されている。Nは任意の定数first_childメソッドは、select1とrank1を一回ずつ呼び出しているので、その分のコストを削除できる子ノード検索方法を、今までの線形検索から二分検索に(部分的に)変更select1呼び出しの削減に比べて、劇的な速度向上はないが、最悪のケース*5での処理時間の悪化を抑えることが可能という意味で有用"部分的に"とは、メモ化と併用することを想定しており、N番目以降のノードに対しては従来の線形検索を行うためメモ化と併用しないと(first_childとlast_childを呼び出す必要があるため)かえって遅くなってしまうまた、(たぶん)大抵のtrieではレベルが深くなるに従って、個々のノードに属する子どもの数は少なくなるので、Nを十分大きくとれば二分検索よりも線形検索の方が高速になると予想される変更分のソース。}};#endif感想これで試したいことはだいたい試し終えた。後はbit-vectorの実装を変更/チューニングすることで、1〜2秒程度なら速くできるかもしれないが、もう劇的に速くなるといったようなことはないのではないかと思う。現時点で(キーセットに大きく依存するが)DoubleArray(というかdoar)に比べて、サイズが半分で速度が1/4。これからdoarのサイズ縮小も試すつもりなので、もしそれが上手くいってしまったら、trieの実装においてLOUDSを使う意義はなくなってしまうな、とも思う。ソースコード現時点までに作成したソースコード一式は、もう少し整理してどこかにアップする予定。思っていたけど時間がないので、中止。機会)があったらいつか...(2010/07/12)。*1:例えば、極端な例として、"abcde"という文字列一つからなるtrieがあるとする。TAIL配列を使えばキーの検索が一回の文字列比較で済む(select1呼び出しは0回)が、通常のtrieではselect1を5回呼び出す必要がある(成功検索の場合)。*2:この名前は適切ではない*3:ただし、実際に検索速度が向上するかどうかはキーセットに依存すると思われる。読者になる検索リンクgithub最新記事RustでMD5ハッシュを計算するRustとSBCLでのDAWG構築性能の比較メモEmacsのファイル保存時に自動的にrustfmtが適用されるようにする現在時刻をUNIXタイムスタンプ形式で取得するloglevelとseverityの使い分けメモ月別アーカイブ最新記事RustでMD5ハッシュを計算するRustとSBCLでのDAWG構築性能の比較メモEmacsのファイル保存時に自動的にrustfmtが適用されるようにする現在時刻をUNIXタイムスタンプ形式で取得するloglevelとseverityの使い分けメモ注目記事ブクログqiitasileのtips人気エントリーはてなブログをはじめよう!sileさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。