最近、祖先について聞いたことがありますが、その実装を試みることに決めましたが、検索操作の複雑さを悩ますものがあります。私はなぜそんなに早くなるはずなのか、私は立証できません。nedtrieでの検索操作の複雑さ（ビット単位のトライ）
私が理解したところでは、検索操作の複雑さは O（m/2）でなければなりません。 あなたが得る 、伝統的なバイナリツリー内の検索操作の複雑さと比較した場合： LOG2（N）> = M/2
レッツは、キーは32ビットの長さである：LOG2（N）> = 16 < => n> = 65536
したがって、nedtriesは、65536個のアイテムから始まるバイナリツリーよりも速くなければなりません。 しかし、著者はバイナリツリーよりも常に高速であると主張しているので、私の前提である の複雑さや、検索の各ステップで実行される計算がnedtrieで非常に高速です。
だから、どうですか？
ツリーが小さい場合は、小さいキーを使用できます。
（注：私はnedtriesの著者です）。 nedtriesページの前の複雑さについての私の説明は意味をなさないと思いますか？おそらくそうではありません。
欠けているキーは、複雑さを決定するビットの間にという差異があります。これは、の違いです。差が大きいほど検索コストは低くなりますが、差が小さいほど検索コストが高くなります。
このことは、現代的なアウトオブオーダープロセッサに起因するという事実が原因です。大幅な簡素化として、メインメモリを避けると、メインメモリに依存している場合よりもコードの実行速度が約40〜80倍速くなります。つまり、メモリから1つのものをロードするのにかかる時間に50〜150 opsを実行できます。つまり、ビットスキャンを実行して、どのノードを次に見るべきかを、そのノードのキャッシュラインをメモリにロードするのに要する時間よりもずっと長くすることができます。
これにより、ロジック、ビットスキャン、およびその他すべてを複雑さの分析から効果的に削除します。彼らはすべてO（N^N）であり、それは問題ではないでしょう。ここで重要なのは、見る次のノードの選択が事実上自由であることです。検査のためにロードする必要があるノードの数はスケーリングの制約なので、ノードの総数はメインメモリの遅さはこれまでのところ最大の複雑さの制約であるため、平均複雑度であるノードの数が増えます。
これは意味がありますか？鍵の一端に密集しているが、鍵のもう一端に詰め込まれているような奇妙な意味では、密集した末端での検索は非常に遅くなる（O（log N）に近づくとN （O（1）に近づいている）よりも、疎な詰め込みの端での検索より
すぐに私はこのビット単位の試行機能を利用する新しい関数を追加することになりますので、「このノードを疎密空間に追加して、選択した鍵を返す」と言うことができます。そのテーマのバリエーション悲しいことに、いつものように、それは時間が掛かり、時間を要する。
ニオール
シンプルで効率的です。完璧な答え。 – fokenrute