هل لديك وظيفة تجزئة جيدة لجدول تجزئة C++؟

Question

أنا في حاجة إلى تنفيذ دالة التجزئة الموجهة نحو الأداء في لغة C++ لجدول التجزئة الذي سأقوم بترميزه.لقد نظرت حولي بالفعل ولم أجد سوى أسئلة تطرح ما هي وظيفة التجزئة الجيدة "بشكل عام".لقد فكرت في CRC32 (ولكن أين يمكنني العثور على التنفيذ الجيد؟) وبعض خوارزميات التشفير.لكن طاولتي لها متطلبات محددة للغاية.

إليك ما سيكون عليه الجدول:

100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
     examples: "become"    "and he"    ", not "

ال الأولوية رقم واحد جدول التجزئة الخاص بي هو البحث السريع (الاسترجاع).الإدراج السريع ليس مهما، ولكنه سيأتي مع البحث السريع.الحذف ليس مهمًا، وإعادة التجزئة ليس شيئًا سأبحث فيه.للتعامل مع الاصطدامات، سأستخدم على الأرجح تسلسل منفصل كما وصفت هنا.لقد نظرت بالفعل في هذا المقال, ولكن أود الحصول على رأي أولئك الذين تعاملوا مع هذه المهمة من قبل.

Answer 1

الآن لنفترض أنك تريد التجزئة، وتريد شيئا اشتعلت فيه النيران بسرعة قد ينجح ذلك في حالتك، نظرًا لأن سلاسلك يبلغ طولها 6 أحرف فقط، يمكنك استخدام هذا السحر:

size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
   return (*(size_t*)str)>> precision;
}

اتفاقية حقوق الطفل مخصصة للأشخاص البطيئين ;)

توضيح:يعمل هذا عن طريق تحويل محتويات مؤشر السلسلة إلى "تبدو وكأنها" size_t (int32 أو int64 بناءً على التطابق الأمثل لجهازك).لذلك يتم تفسير محتويات السلسلة كرقم أولي، فلا داعي للقلق بشأن الأحرف بعد الآن، ثم تقوم بعد ذلك بتغيير هذا الرقم بالدقة المطلوبة (تقوم بتعديل هذا الرقم للحصول على أفضل أداء، لقد وجدت 2 يعمل بشكل جيد لتجزئة السلاسل في مجموعة من بضعة آلاف).

كما أن الجزء الأنيق حقًا هو أن أي مترجم لائق على الأجهزة الحديثة سوف يقوم بتجزئة سلسلة مثل هذه في تعليمات تجميع واحدة، ومن الصعب التغلب على ذلك؛)

Answer 2

هذا كثير الحدود البسيط يعمل بشكل جيد بشكل مدهش.حصلت عليها من بول لارسون من Microsoft Research الذي درس مجموعة واسعة من وظائف التجزئة ومضاعفات التجزئة.

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

salt ينبغي تهيئة لبعض بشكل عشوائي القيمة المختارة قبل إنشاء جدول التجزئة للدفاع ضدها هجمات جدول التجزئة.إذا لم تكن هذه مشكلة بالنسبة لك، فما عليك سوى استخدام 0.

حجم الجدول مهم أيضًا لتقليل الاصطدامات.يبدو وكأنه لك على ما يرام.

Answer 3

Boost.Functional/Hash قد تكون ذات فائدة لك.لم أجربه، لذا لا أستطيع أن أضمن أداءه.

يحتوي Boost أيضًا على مكتبة اتفاقية حقوق الطفل.

سأبدو أ دفعة.غير مرتبة أولا (أيدفعة::unordered_map<>).يستخدم خرائط التجزئة بدلاً من الأشجار الثنائية للحاويات.

أعتقد أن بعض تطبيقات STL تحتوي على حاوية hash_map<> في مساحة الاسم stdext.

Answer 4

سيحدد حجم الجدول الخاص بك حجم التجزئة الذي يجب عليك استخدامه.ترغب في تقليل الاصطدامات بالطبع.لست متأكدًا مما تحدده من خلال الحد الأقصى للعناصر والسعة (يبدو أنها نفس الشيء بالنسبة لي) على أي حال، يشير أي من هذه الأرقام إلى أن تجزئة 32 بت ستكون كافية.قد تفلت من CRC16 (حوالي 65000 احتمال) ولكن من المحتمل أن يكون لديك الكثير من الاصطدامات للتعامل معها.من ناحية أخرى، قد يكون التعامل مع التصادم أسرع من التعامل مع تجزئة CRC32.

أود أن أقول، اذهب مع CRC32.لن تجد نقصًا في الوثائق ونموذج التعليمات البرمجية.نظرًا لأنك قد حددت الحد الأقصى الخاص بك وأن السرعة هي الأولوية، فاستخدم مجموعة من المؤشرات.استخدم التجزئة لإنشاء فهرس.عند الاصطدام، قم بزيادة المؤشر حتى تصل إلى دلو فارغ.سريعة وبسيطة.

Answer 5

نظرًا لأنك تقوم بتخزين الكلمات الإنجليزية، فإن معظم الأحرف الخاصة بك ستكون عبارة عن أحرف ولن يكون هناك اختلاف كبير في أهم جزأين من بياناتك.بالإضافة إلى ذلك سأبقي الأمر بسيطًا جدًا، فقط باستخدام XOR.بعد كل شيء، أنت لا تبحث عن قوة التشفير ولكن فقط عن توزيع متساوٍ بشكل معقول.شيء على هذا المنوال:

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

بالإضافة إلى ذلك، هل نظرت إلى std::tr1::hash كوظيفة تجزئة و/أو std::tr1::unordered_map كتطبيق لجدول التجزئة؟من المحتمل أن يؤدي استخدام هذه الأشياء إلى توفير الكثير من العمل مقابل تنفيذ الفصول الدراسية الخاصة بك.

Answer 6

الأولوية الأولى لجدول التجزئة الخاص بي هي البحث السريع (الاسترجاع).

حسنًا، فأنت تستخدم بنية البيانات الصحيحة، حيث أن البحث في جدول التجزئة هو O(1)!:)

يجب أن يكون أداء CRC32 جيدًا.التنفيذ ليس بهذا التعقيد، فهو يعتمد بشكل أساسي على XORs.فقط تأكد من أنه يستخدم كثيرة الحدود جيدة.

Answer 7

ماذا عن شيء بسيط:

// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];

// Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

هذا يفترض 32 بت int.ويستخدم 5 بتات لكل حرف، وبالتالي فإن قيمة التجزئة تحتوي على 30 بت فقط.ربما يمكنك حل هذه المشكلة عن طريق إنشاء ستة بتات للحرف الأول أو الحرفين الأولين.إذا كانت مجموعة الأحرف لديك صغيرة بما يكفي، فقد لا تحتاج إلى أكثر من 30 بت.

Answer 8

إذا كنت بحاجة إلى البحث عن سلاسل قصيرة ولم يكن الإدراج مشكلة، فربما يمكنك استخدام شجرة B، أو شجرة 2-3، فلن تكسب الكثير من التجزئة في حالتك.

الطريقة التي يمكنك بها القيام بذلك هي عن طريق وضع حرف في كل عقدة، لذا عليك أولاً التحقق من العقدة "a"، ثم التحقق من العناصر الفرعية لـ "a" بحثًا عن "p"، ومن العناصر الفرعية لـ "p"، ثم " ل" ثم "ه".في المواقف التي يكون لديك فيها "apple" و"apply"، فإنك تحتاج إلى البحث عن العقدة الأخيرة (نظرًا لأن الاختلاف الوحيد هو في آخر "e" و"y")

ولكن في معظم الحالات، ستتمكن من الحصول على الكلمة بعد بضع خطوات فقط ("إكسيليفون" => "x"->"ylophone")، لذا يمكنك التحسين بهذه الطريقة.يمكن أن يكون هذا أسرع من التجزئة

Answer 9

منذ C++ 11، قدمت C++ std::hash< string >( string ).من المحتمل أن تكون هذه وظيفة تجزئة فعالة توفر ملف التوزيع الجيد لرموز التجزئة لمعظم السلاسل.

علاوة على ذلك، إذا كنت تفكر في تنفيذ جدول التجزئة، فيجب أن تفكر الآن في استخدام لغة C++ std::unordered_map بدلاً من.