تجزئة الوقواق في C
https://stackoverflow.com/questions/231438
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هل يوجد أحد لديه التنفيذ تجزئة الوقواق شركة؟إذا كان هناك إصدار مفتوح المصدر، وليس إصدار GPL فسيكون مثاليًا!
منذ أن ذكرها آدم في تعليقه، أحد يعرف لماذا لا يستخدم كثيرًا؟هل الأمر مجرد مسألة تنفيذ أم أن الخصائص النظرية الجيدة لا تتجسد في الممارسة العملية؟
نصائح أخرى
وكما أشار إجابات أخرى بها، صحيح أن أبسط جدول هاش الوقواق يتطلب أن الجدول يكون نصف فارغة. ومع ذلك، تم تعميمه على مفهوم <م> د -ary الوقواق التجزئة، والتي في كل مفتاح لديه <م> د الأماكن الممكنة لعش، في مقابل 2 أماكن في نسخة بسيطة.
والزيادات عامل الحمولة مقبولة أسرع وقت <م> د هو زيادة. فقط <م> د = 3، يمكنك استخدامها بالفعل حول الجدول الكامل 75٪. الجانب السلبي هو أن تحتاج <م> د وظائف التجزئة المستقلة. أنا من محبي وظائف التجزئة بوب جنكينز "لهذا الغرض (انظر http://burtleburtle.net /bob/c/lookup3.c )، التي قد تجدها مفيدة في تنفيذ الوقواق التجزئة.
والوقواق التجزئة هي خارج غير المستخدمة نسبيا من الأوساط الأكاديمية (بغض النظر عن مخابئ الأجهزة التي تقترض بعض الأحيان الأفكار من، ولكن لا تنفذ حقا بالكامل). فهو يتطلب جدول التجزئة متفرق جدا للحصول على وقت جيد على الإدراج - كنت حقا بحاجة إلى أن يكون 51٪ من الجدول الخاص بك فارغة على الأداء الجيد. لذلك هو إما سريع ويأخذ الكثير من الفضاء، أو بطيئة ويستخدم الفضاء بكفاءة - أبدا على حد سواء. خوارزميات أخرى هي الوقت والفضاء كفاءة، على الرغم من أنها أسوأ من الوقواق عندما يتم أخذ الزمان أو المكان فقط بعين الاعتبار.
وهنا هو للجداول الوقواق التجزئة . تحقق الترخيص للمولد للتحقق من أن الإخراج هو غير GPL. وينبغي أن يكون، ولكن تحقق أي حال.
و-Adam
وعلى الرغم من انها مسألة قديمة، قد يكون شخص ما يزال مهتما:)
هذه الورقة يصف تنفيذ موازية التجزئة الوقواق د-آرى على وحدات معالجة الرسومات (CUDA / OpenCL). وصفها بشكل جيد للغاية وتنفيذها على أساس وصف في غاية السهولة. عموما تستحق القراءة، إذا كنت مهتما في هذا الموضوع. (سوف تحتاج إلى تسجيل الدخول ACM بالرغم من ذلك.)
واللغة IO لديها واحد، في PHash.c. يمكنك العثور على رمز IO على جيثب. وBSD IO مرخصة.
أرى النقطة المتعلقة بالاستخدام ولكن هذا كان السبب الذي دفعني لتجربة نظام التجزئة هذا بالتحديد.يرجى إعلامي إذا فاتني شيء ما.
على حد علمي، البدائل الممكنة لجداول التجزئة لإنشاء قاموس ديناميكي هي الأشجار الثنائية (المتوازنة) وقوائم التخطي.فقط للمناقشة، دعونا نلخص أنواع المفاتيح والقيم ونفترض أننا سنصل إلى القيم من خلال ملف void *.
بالنسبة للشجرة الثنائية سيكون لدي:
struct node {
void *key;
void *value;
struct node *left;
struct node *right;
}
لذا، بافتراض أن المؤشرات لها نفس الحجم س, ، للتخزين ن العناصر التي سأحتاجها 4 س بايت.
إن Skiplists هي تقريبًا نفس متوسط عدد المؤشرات في العقدة وهو 2.
في جدول التجزئة سيكون لدي:
struct slot {
void *key;
void *value;
}
لذا، فإن كل عنصر سيتطلب 2 فقط س بايت ليتم تخزينها.إذا كان عامل الحمولة 50%، للتخزين ن العناصر التي سأحتاجها هي نفسها 4 س بايت مثل الأشجار.
لا يبدو الأمر سيئًا للغاية بالنسبة لي:سوف يشغل جدول تجزئة الوقواق نفس مقدار الذاكرة تقريبًا مثل الشجرة الثنائية ولكنه سيعطيني وقت وصول O(1) بدلاً من O(log n).
دون احتساب مدى تعقيد الحفاظ على توازن الشجرة والمعلومات الإضافية التي قد تكون مطلوبة لتخزين معلومات الموازنة في العقدة.
يمكن أن تحقق مخططات التجزئة الأخرى عامل تحميل أفضل (على سبيل المثال 75% أو 80%) مع عدم وجود ضمان لوقت الوصول في أسوأ الحالات (والذي يمكن أن يكون حتى O(n) ).
بالمناسبة، تجزئة الوقواق d-ary و "تجزئة الوقواق مع مخبأ"يبدو أنه قادر على زيادة عامل التحميل مع الحفاظ على وقت وصول ثابت.
يبدو أن تجزئة الوقواق أسلوب ذو قيمة بالنسبة لي وأعتقد أنه قد تم استكشافه بالفعل؛هذا هو سبب سؤالي.
لا أستطيع أن أتكلم عن البرنامج ولكن يستخدم التجزئة الوقواق بالتأكيد في الأجهزة وأصبحت شعبية جدا. قد تبحث البائعين الرئيسيين من معدات الشبكات في تجزئة الوقواق واستخدام بعض بالفعل. جذب للتجزئة الوقواق يأتي من وقت البحث المستمر، وبطبيعة الحال، ولكن أيضا القريب الوقت الإدراج المستمر.
وعلى الرغم من أن الإدراج يمكن أن يكون نظريا غير محدود، في واقع الامر انه يمكن يحدها O (سجل ن) من عدد الصفوف في الجدول (ق) وعند قياسها، وهي المرة الإدراج حوالي 1.1 * ذاكرة د يصل في المتوسط. هذا مجرد 10٪ أكثر من الحد الأدنى المطلق! الوصول إلى الذاكرة وغالبا ما يكون العامل المحدد في معدات الشبكات.
وظائف التجزئة المستقلة لا بد منه وتحديدها بشكل صحيح أمر صعب. حظا سعيدا.
وبعد تعليق من "onebyone" لقد تنفيذها واختبارها عدة إصدارات الوقواق تجزئة لتحديد متطلبات الذاكرة الحقيقية.
وبعد بعض التجارب، فإن الادعاء بأن لم يكن لديك لreash حتى الجدول هو يبدو ما يقرب من 50٪ الكاملة ليكون صحيحا، وخاصة إذا كان "<لأ href =" http://research.microsoft.com/pubs /73856/stash-full.9-30.pdf "يختلط =" نوفولو noreferrer "> خبأ " وimplmented خدعة.
والمشكلة هي عند تكبير الجدول. النهج المعتاد هو أن يتضاعف حجمها ولكن هذا يؤدي إلى الجدول الجديد أن يكون 25٪ فقط استخدمت!
في الواقع، تحمل جدول هاش لديها 16 فتحات، عندما أقوم بإدخال رقم العنصر 8TH، وأنا نفدت فتحات جيدة وسوف تضطر إلى reash. سوف يتضاعف أنها الآن والجدول 32 فتحات مع 8 منهم فقط المحتل الذي هو مضيعة 75٪!
وهذا هو الثمن الواجب دفعه لديها "ثابت" وقت استرجاع (من حيث الحد الأعلى لعدد من الوصول / المقارنة).
ولقد وضعت مخطط مختلفة، على الرغم من: بدءا من قوة 2 أكبر من 1، إذا كان الجدول يحتوي على فتحات n و n هو قوة اثنين، إضافة ن / 2 فتحات otherwhise إضافة ن / 3 فتحات:
+--+--+
| | | 2 slots
+--+--+
+--+--+--+
| | | | 3 slots
+--+--+--+
+--+--+--+--+
| | | | | 4 slots
+--+--+--+--+
+--+--+--+--+--+--+
| | | | | | | 6 slots
+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+
| | | | | | | | | 8 slots
+--+--+--+--+--+--+--+--+
وغيرها.
وجنبا إلى جنب مع افتراض أن reashing سيحدث فقط عندما يكون الجدول 50٪ كاملة، وهذا يؤدي إلى حقيقة أن الجدول سيكون فقط 66٪ فارغة (1/3) بدلا من 75٪ فارغ (1/4) بعد وreash (أي أسوأ الحالات).
ولقد برزت أيضا (ولكن ما زلت بحاجة للتحقق من الرياضيات) التي توسيع في كل مرة من قبل الجذر التربيعي (ن)، مساحة مهدرة نهج مقارب 50٪.
وبالطبع الثمن الذي دفع لأقل من استهلاك الذاكرة هو زيادة عدد reash التي ستكون هناك حاجة في نهاية المطاف. للأسف، لا شيء يأتي مجانا.
وانا ذاهب الى مواصلة التحقيق إذا كان أي شخص مهتم.
