3

Kademliaプロトコルでは、ノードIDは160ビットの数値です。ノードはバケットに格納され、バケット0は最後のビットを除いてこのノードと同じIDを持つすべてのノードを格納し、バケット1は最後の2ビットを除いてこのノードと同じIDを持つすべてのノードを格納します。 160個のバケットすべてでオンになります。

新しいノードを配置する必要があるバケットを見つけるための最速の方法は何ですか？

バケットを単純に配列に格納しているので、次のようなメソッドが必要です。

Bucket[] buckets; //array with 160 items

public Bucket GetBucket(Int160 myId, Int160 otherId)
{
    //some stuff goes here
}

明らかなアプローチは、最上位ビットから作業を進め、違いが見つかるまでビットごとに比較することです。巧妙なビットの調整に基づいたより良いアプローチがあることを望んでいます。

実用上の注意：私のInt160は20項目のバイト配列に格納されているため、この種の構造で適切に機能するソリューションが推奨されます。

4

2 に答える 2

3

5つの32ビット整数の配列を検討してもよろしいですか？（または3つの64ビット整数）？単語全体を操作すると、バイトを操作するよりもパフォーマンスが向上する場合がありますが、このメソッドはどのような場合でも機能するはずです。

2つのノードIDの対応する単語を、最も重要なものから順にXORします。XORの結果がゼロの場合は、次に重要な単語に進みます。

それ以外の場合は、 Hacker's Delightの一定時間法を使用して、このXOR結果に設定されている最上位ビットを見つけます。。このアルゴリズムは、最上位ビットが設定されている場合は32（64）になり、最下位ビットが設定されている場合は1になります。このインデックスを現在の単語のインデックスと組み合わせると、どのビットが異なるかがわかります。

于 2010-04-17T00:31:29.763 に答える
2

手始めに、バイトごと（または単語ごと）を比較し、そのバイト（または単語）内で違いを見つけたら、違いの最初のビットを検索します。

バケットの配列にノードを追加するのが非常に高速であるため、バイト（またはワード）内の最初のビットの違いを見つけるために巧妙なビットをいじるのか、ループでチャーンするのかが重要になることは、私には漠然と信じられないようです。 CHAR_BIT（または何か）まで。ただし、可能です。

また、IDが本質的にランダムで均一に分布している場合、最初の8ビットに約255/256の時間の違いがあります。気になるのが最悪の場合ではなく平均的な場合の振る舞いだけである場合は、愚かなことをしてください。ループが長時間実行される可能性はほとんどありません。

xただし、参考までに、数値との差の最初のビットyは、で設定された最初のビットですx ^ y。もしあなたがGNUCでプログラミングしていたなら、__builtin_clzあなたの友達かもしれません。または、おそらく__builtin_ctz、私はちょっと眠いです...

ただし、コードはJavaのように見えるので、探しているbitfooは整数ログだと思います。

于 2010-04-17T00:17:35.967 に答える