最近、nedtriesについて聞いて、それらを実装してみることにしましたが、検索操作の複雑さについて何か気になります。なぜこんなに速いのか我慢できない。
私が理解したことから、彼らの検索操作の予想される複雑さは、ビット単位のキーのサイズがmのO（m / 2）であるはずです。これを従来の二分木の検索操作の複雑さと比較すると、次のようになります。log2（n）> = m / 2
キーを32ビット長にしましょう：log2（n）> = 16 <=> n> = 65536
したがって、nettriesは、65536アイテムから始まるバイナリツリーよりも高速である必要があります。ただし、著者は、それらは常に二分木よりも高速であると主張しているため、それらの複雑さに関する私の仮定が間違っているか、検索の各ステップで実行される計算がnedtrieで非常に高速です。
それで、それはどうですか？
（私はnedtriesの作者であることに注意してください）。nedtriesページの前面にある複雑さの説明は理にかなっていると思いますか？おそらくそうではありません。
あなたが見逃している鍵は、複雑さを決定するのはビット間の違いであるということです。差が大きいほど検索コストは低くなり、差が小さいほど検索コストは高くなります。
これが機能するという事実は、最新のアウトオブオーダープロセッサに由来します。大幅に簡略化すると、メインメモリを回避すると、メインメモリに依存している場合よりもコードの実行速度が約40〜80倍速くなります。つまり、メモリから1つのものをロードするのにかかる時間で50〜150の操作を実行できます。つまり、ビットスキャンを実行して、そのノードのキャッシュラインをメモリにロードするのにかかる時間よりもはるかに長くなく、次にどのノードを調べる必要があるかを把握できます。
これにより、ロジック、ビットスキャン、その他すべてが複雑さの分析から効果的に削除されます。それらはすべてO（N ^ N）である可能性があり、それは問題ではありません。ここで重要なのは、次に調べるノードの選択が事実上自由であるということです。したがって、検査のためにロードする必要があるノードの数はスケーリングの制約であり、したがって、メインメモリの速度がはるかに最大の複雑さの制約であるため、ノードは平均的な複雑さです。
これは意味がありますか？これは、一部のビットがキーの一方の端に密にパックされているが、キーのもう一方の端に緩くパックされている場合、密にパックされた端での検索が非常に遅くなる（Nが数値であるO（log N）に近づく）などの奇妙なことを意味します密集した要素の）、ゆるく詰め込まれた端（O（1）に近づく）での検索よりも。
いつの日か、ビット単位の試行のこの機能を利用する新しい関数の追加に取り掛かるので、「このノードをゆるく/密集したスペースに追加して、選択したキーを返す」と言うことができます。テーマ。悲しいことに、いつものように、それは時間に帰着し、自分の時間に要求します。
ニール
小さい木がある場合は、小さいキーを使用できます。