أسرع خريطة C++؟




performance data-structures (2)

صححني بأنني مخطئ ولكن std :: map هي خريطة مرتبة ، وهكذا في كل مرة أقوم بإدراج قيمة ، تستخدم الخريطة خوارزمية لفرز عناصرها داخليًا ، الأمر الذي يستغرق بعض الوقت.

يحصل طلبي على معلومات تتعلق ببعض العناصر على فاصل زمني ثابت.

يحتفظ هذا التطبيق بالخريطة التي يتم تعريفها على النحو التالي:

::std::map<DWORD, myItem*>

في البداية تعتبر كل العناصر "جديدة" للتطبيق. يتم تخصيص كائن "العنصر" وإضافته إلى هذه الخريطة ، مع ربط معرفه ومؤشر به.

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

في معظم الأحيان أحصل على التحديثات.

سؤالي هو:
هل هناك أي تنفيذ للخريطة أسرع أم يجب أن أستخدم هذا؟
هل من الأفضل استخدام unordered_map؟


هل من الأفضل استخدام unordered_map؟

ربما.

std:map توفر std:map أداءً ثابتًا في O (log n) لأنه يحتاج إلى التنفيذ كشجرة متوازنة. ولكن std:unordered_map سيتم تنفيذ std:unordered_map كجدول هاش قد يعطيك أداء O (1) (وظيفة هاش جيدة وتوزيع مفاتيح عبر دلاء التجزئة) ، ولكن يمكن أن يكون O (n) (كل شيء في دلو تجزئة واحد ويؤول إلى قائمة). يتوقع المرء عادة شيء ما بين هذه التطرف.

لذا يمكنك الحصول على أداء معقول (O (log n)) طوال الوقت ، أو تحتاج إلى التأكد من أن كل شيء يسير للحصول على أداء جيد مع التجزئة.

كما هو الحال مع أي سؤال من هذا القبيل: تحتاج إلى قياس قبل الالتزام بنهج واحد. ما لم تكن مجموعات البيانات الخاصة بك كبيرة قد تجد أنه لا يوجد فرق كبير.


تحذير هام: ما لم تقاس (ويشير سؤالك إلى أنك لم تقم بذلك) ، فإن أداء الخريطة يؤثر بشكل كبير على أداء التطبيق الخاص بك (نسبة كبيرة من الوقت الذي يتم إنفاقه على البحث وتحديث الخريطة) لا تهتم بجعله أسرع. عصا std::map (أو std::unordered_map أو أي تطبيق hash_map متاح). تسريع تطبيقك بنسبة 1٪ على الأرجح لن يكون مجديًا. جعلها خالية من الأخطاء بدلا من ذلك.

مرددا إجابة ريتشارد: قياس الأداء مع تنفيذ خريطة مختلفة باستخدام الطبقات الحقيقية والبيانات الحقيقية.

بعض الملاحظات الإضافية:

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

  • معرفة أين عنق الزجاجة الحقيقي هو. قد تكون تكلفة البحث في الخريطة ضئيلة مقارنة بتكلفة IO مثلاً.

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

في المثال الخاص بك (مفاتيح صحيحة 32 بت غير موقعة والتي يتم تجميعها بقوة ، على سبيل المثال يتم تعيينها بالتتابع) يمكنك استخدام المقاربة القائمة على أساس rad. مثال بسيط للغاية (قم بتهديده كتوضيح وليس جاهزًا لاستخدام الوصفة):

Item *sentinel[65536];  // sentinel page, initialized to NULLs.
Item (*pages[65536])[65536];  // list of pages,
                              // initialized so every element points to sentinel

ثم البحث هو بسيط مثل:

Item *value = pages[index >> 16][index & 0xFFFF];

عندما تحتاج إلى تعيين قيمة جديدة:

if (pages[index >> 16] == sentinel) {
  pages[index >> 16] = allocate_new_null_filled_page();
}
pages[index >> 16][index & 0xFFFF] = value;
  • قم بتعديل تطبيق خريطتك.

    • على سبيل المثال ، يحب كل hash_map معرفة العدد التقريبي للعناصر مقدمًا. يساعد على تجنب إعادة تخصيص غير ضرورية لجدول التجزئة و (ربما) إعادة صياغة جميع المفاتيح.

    • مع مثالي المتخصص أعلاه ، من المؤكد أنك ستحاول استخدام أحجام مختلفة للصفحة ، أو إصدار ثلاثة مستويات.

    • التحسين المشترك هو توفير مخصص الذاكرة المخصصة لتجنب تخصيصات متعددة من الكائنات الصغيرة.





map