أسهل طريقة للعثور على الصحيح kademlia دلو

Question

في Kademlia البروتوكول عقدة معرفات 160 بت الأرقام.العقد يتم تخزينها في الدلاء ، دلو 0 يخزن كل العقد التي لها نفس معرف مثل هذه العقدة ما عدا آخر جزء, دلو 1 يخزن كل العقد التي لها نفس معرف مثل هذه العقدة ما عدا الأخير 2 بت ، وذلك على جميع 160 الدلاء.

ما هي أسرع طريقة للعثور على أي دلو يجب أن تضع عقدة جديدة ؟

لدي دلاء ببساطة المخزنة في صفيف ، وتحتاج إلى طريقة مثل ذلك:

Bucket[] buckets; //array with 160 items

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

نهج واضح هو العمل من أهم بت ، مقارنة شيئا فشيئا حتى أجد فرقا, أنا على أمل هناك أفضل النهج القائم حول ذكي قليلا twiddling.

ملاحظة:بلدي Int160 المخزنة في صفيف بايت مع 20 البنود, الحلول التي تعمل بشكل جيد مع هذا النوع من الهيكل سيكون المفضل.

Answer 1

هل تكون على استعداد للنظر في مجموعة من 5 أعداد صحيحة 32 بت؟ (أو 3 أعداد صحيحة 64 بت)؟ قد يمنحك العمل بكلمات كاملة أداءً أفضل من العمل مع Bytes ، ولكن يجب أن تعمل الطريقة في أي حال.

XOR الكلمات المقابلة لمعرفات العقدة ، بدءًا من الأهم. إذا كانت نتيجة XOR صفرًا ، فانتقل إلى الكلمة الأكثر أهمية التالية.

خلاف ذلك ، ابحث عن أهم بتات تم تعيينها في هذه النتيجة XOR باستخدام طريقة الوقت المستمرة من فرحة هاكر.. ينتج عن هذه الخوارزمية 32 (64) إذا تم تعيين البتات الأكثر أهمية ، و 1 إذا تم تعيين البت الأقل أهمية ، وهكذا. سيخبرك هذا الفهرس ، إلى جانب فهرس الكلمة الحالية ، أي شيء مختلف.

Answer 2

بالنسبة للمبتدئين يمكنك مقارنة بايت بايت (أو كلمة بكلمة), و عندما تجد فرق البحث داخل بايت (أو كلمة) لأول قليلا من الفرق.

يبدو غامضة من غير المعقول بالنسبة لي أن إضافة عقدة إلى مجموعة من الدلاء سوف تكون سريعة بحيث يهم ما إذا كنت تفعل الشيء ذكية-twiddling العثور على أول قليلا من الفرق داخل بايت (أو كلمة) ، أو مجرد زبد في حلقة تصل إلى CHAR_BIT (أو شيء).ممكن, على الرغم من.

أيضا ، إذا معرفات أساسا عشوائية مع توزيع موحد, ثم سوف تجد فرقا في أول 8 بت عن 255/256 من الوقت.إذا كان كل ما يهمني هو متوسط-حالة السلوك ، وليس الأسوأ ، ثم يفعل شيء غبي:فمن المستبعد جدا أن يكون حلقة الخاص بك سيتم تشغيل لفترة طويلة.

للإشارة ، على الرغم من الأولى قليلا من الفرق بين الأرقام x و y هي أول مجموعة بت في x ^ y.إذا كنت البرمجة في GNU C ، __builtin_clz قد يكون صديقك.أو ربما __builtin_ctz, أنا نوع من النعاس...

التعليمات البرمجية الخاصة بك يبدو جافا ، على الرغم من ذلك أعتقد bitfoo كنت تبحث عن صحيح سجل.