حاوية سريعة لإعداد البتات في مجال متفرق ، والتكرار (C ++)؟
https://stackoverflow.com/questions/311297
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أحتاج إلى حاوية سريعة مع عمليتين فقط. تم تعيين مفاتيح إدراج من مجال متفرق للغاية (يتم تعيين جميع أعداد صحيحة 32 بت ، وحوالي 100 في وقت معين) ، وتكرار على المفاتيح المدرجة. يجب أن تتعامل مع كثير من الإدراج التي ضربت نفس الإدخالات (مثل ، 500 كيلو ، ولكن فقط 100 منها مختلفة).
حاليًا ، أستخدم STD :: SET (أدخل فقط وواجهة التكرار) ، وهو أمر لائق ، لكنه لا يزال سريعًا بما فيه الكفاية. كان std :: unordered_set بطيئًا ، نفسه بالنسبة لخرائط تجزئة Google. أتساءل ما هي بنية البيانات التي تم تحسينها لهذه الحالة؟
المحلول
اعتمادًا على توزيع المدخلات ، قد تتمكن من الحصول على بعض التحسن دون تغيير الهيكل.
إذا كنت تميل إلى الحصول على الكثير من أشواط قيمة واحدة ، فيمكنك على الأرجح تسريع الإدراج عن طريق الحفاظ على سجل آخر القيمة التي أدخلتها ، ولا تهتم بالقيام بالإدراج إذا كانت متطابقة. يكلف مقارنة إضافية لكل إدخال ، ولكنه يوفر بحثًا لكل عنصر في الجري الذي يتجاوز الأول. لذلك يمكن أن يحسن الأشياء بغض النظر عن بنية البيانات التي تستخدمها ، اعتمادًا على تواتر التكرارات والتكلفة النسبية للمقارنة مقابل الإدراج.
إذا لم تحصل على تشغيل ، لكنك تميل إلى العثور على أن القيم لا يتم توزيعها بالتساوي ، فإن شجرة الطيران تجعل الوصول إلى العناصر الأكثر استخدامًا أرخص. إنه يعمل من خلال إنشاء شجرة غير متوازنة عمدا مع العناصر المتكررة بالقرب من الأعلى ، مثل رمز هوفمان.
نصائح أخرى
لست متأكدًا من أنني أفهم "الكثير من الإدراج التي ضربت نفس الإدخالات". هل تقصد أن هناك 100 قيم فقط من الأعضاء على الإطلاق ، لكن 500 ألف عملية في الغالب تُدرج إحدى هذه القيم المائة؟
إذا كان الأمر كذلك ، فأعتقد أن أسرع حاوية ستكون لإنشاء تجزئة خالية من التصادم على هذه القيم المائة ، ثم الحفاظ على صفيف (أو متجه) من الأعلام (int أو بت ، وفقًا لما يعمل في أسرعها على بنية بنية ).
أترك توليد التجزئة كتمرين للقارئ ، لأنه شيء أدركه موجود كأسلوب ، لكنني لم أبحث عنه بنفسي. النقطة المهمة هي الحصول على تجزئة سريعة على أنها نطاق صغير قدر الإمكان ، بحيث لكل n ، m في 100 القيم ، تجزئة (n)! = التجزئة (m).
لذلك يبدو الإدراج array[hash(value)] = 1;, ، يبدو الحذف مثل array[hash(value)] = 0; (على الرغم من أنك لا تحتاج إلى ذلك) ، وتعدادك على الصفيف ، ولكل قيمة محددة في الفهرس n ، فإن عكس_hash (n) موجود في مجموعتك. بالنسبة لمجموعة صغيرة ، يمكنك بسهولة الحفاظ على جدول البحث لأداء التجزئة العكسية ، أو بدلاً من مسح الصفيف بأكمله بحثًا عن علم تعيين ، يمكنك تشغيل القيم التي يحتمل أن تكون في كل المقبل.
آسف إذا أسيء فهم الموقف وهذا عديم الفائدة بالنسبة لك. ولكي نكون صادقين ، فهي ليست أسرع بكثير من علامة التصنيف العادية ، حيث من الناحية الواقعية لـ 100 قيمة ، يمكنك بسهولة حجم الجدول بحيث يكون هناك عدد قليل أو معدوم تصادم ، دون استخدام الكثير من الذاكرة لتفجير ذاكرة التخزين المؤقت.
بالنسبة لمجموعة قيد الاستخدام ، من المتوقع أن تكون هذه صغيرة ، فقد يكون جدول التجزئة غير المقيد على ما يرام. إذا تمكنت من العيش مع عملية توسع عرضية ، فقم بتنميتها في قوى 2 إذا كانت أكثر من 70 ٪ ممتلئة. hashoh cuckoo كان تمت مناقشته على Stackoverflow من قبل وقد يكون أيضًا نهجًا جيدًا لمجموعة هذه صغيرة. إذا كنت بحاجة حقًا إلى تحسين السرعة ، فيمكنك تنفيذ وظيفة التجزئة والبحث في Assembler - على هياكل البيانات الخطية ، سيكون ذلك بسيطًا للغاية ، لذا لا ينبغي الحفاظ على جهد الترميز والصيانة لتنفيذ المجمع.
قد ترغب في التفكير في تنفيذ ملف Hashtree باستخدام وظيفة التجزئة الأساسية 10 في كل مستوى بدلاً من وظيفة التجزئة الثنائية. يمكنك إما أن تجعلها غير محفوظة ، وفي هذه الحالة سيكون أدائك حتميًا (LOG10) أو ضبط حجم الجرافة الخاصة بك بناءً على توزيعك المتوقع بحيث يكون لديك فقط بضع مفاتيح/دلو.
قد يكون بنية البيانات العشوائية مثالية لعملك. ألق نظرة على قائمة تخطي - على الرغم من أنني لا أعرف أي تنفيذ C ++ له. كنت أنوي تقديم واحد لتعزيز ولكن لم أتمكن من القيام بذلك.
لاحظ أنه أثناء الإدراج في جدول التجزئة سريعًا ، فإن التكرار أكثر من ذلك ، ليس سريعًا بشكل خاص ، نظرًا لأنك تحتاج إلى التكرار على الصفيف بأكمله.
أي عملية بطيئة بالنسبة لك؟ هل تفعل المزيد من الإدراج أو التكرار؟
ماحجم الذاكرة لديك؟ 32 بتات تأخذ "فقط" 4 جيجابايت/8 بايت ، والتي تصل إلى 512 ميجابايت ، وليس الكثير لخادم متطور. من شأنه أن يجعل إدخالاتك o (1). ولكن هذا يمكن أن يجعل التكرار بطيئة. على الرغم من أن تخطي جميع الكلمات بأصفار فقط من شأنه أن يحسن معظم التكرارات. إذا كانت الأرقام المائة الخاصة بك في نطاق صغير نسبيًا ، فيمكنك التحسين أكثر من خلال الحفاظ على الحد الأدنى والحد الأقصى.
أعلم أن هذه مجرد قوة وحشية ، ولكن في بعض الأحيان تكون القوة الغاشمة جيدة بما فيه الكفاية.
بما أنه لم يذكرها أحد بشكل صريح ، هل فكرت في منطقة الذاكرة؟ بنية بيانات رائعة حقًا مع خوارزمية للإدراج التي تسبب خطأ في الصفحة لن يكون جيدًا. في الواقع ، من المحتمل أن تكون بنية البيانات ذات الإدانة التي تسبب مجرد تفويت ذاكرة التخزين المؤقت سيئة للغاية بالنسبة لـ Perf.
هل تأكدت من مجموعة من العناصر غير المرتبة معبأة في صفيف ثابت مع مبادلة بسيطة إلى الأمام عندما تكون كوليسيدات إدراج بطيئة جدًا؟ إنها تجربة بسيطة قد تظهر أن لديك مشكلات في منطقة الذاكرة بدلاً من المشكلات الخوارزمية.
