ما هو أكثر كفاءة حالة التبديل أو STD :: خريطة

Question

أنا أفكر في الممتلكات هنا.
كل رمزي يستدعي وظيفة مختلفة داخل المحلل.
ما هو أكثر كفاءة:

• خريطة STD :: وظائف / دفعة :: وظائف
• حالة التبديل

Answer 1

ستمنحك خريطة STL التي تأتي مع Visual Studio 2008 O (سجل (n)) لكل مكالمة وظيفة لأنها تخفي بنية شجرة تحتها. مع التحويل البرمجي الحديث (حسب التنفيذ)، سيمنحك بيان التبديل O (1)، يترجم الترجمة إلى نوع من طاولة البحث. لذلك بشكل عام، التبديل أسرع.

ومع ذلك ، النظر في الحقائق التالية:

الفرق بين الخريطة والتبديل هو أن: يمكن بناء الخريطة ديناميكيا أثناء التبديل لا. يمكن أن تحتوي الخريطة على أي نوع تعسفي كمفتاح أثناء التبديل يقتصر جدا على أنواع C ++ البدائية (Char، Int، Enum، إلخ ...).

بالمناسبة، يمكنك استخدام خريطة التخصص لتحقيق ما يقرب من O (1) إرسال (على الرغم من ذلك، اعتمادا على تنفيذ جدول التجزئة، يمكن أن يكون في بعض الأحيان O (N) في أسوأ الحالات). على الرغم من أن التبديل ستظل أسرع.

يحرر

أكتب ما يلي فقط للمتعة ولهذه المناقشة

يمكنني أن أقترح تحسين لطيف بالنسبة لك، لكنه يعتمد على طبيعة لغتك وما إذا كان يمكنك توقع كيفية استخدام لغتك.

عند كتابة الرمز: تقوم بتقسيم الرموز الخاصة بك إلى مجموعتين، ستكون مجموعة واحدة عالية الاستخدام بشكل متكرر وآخر منخفض يستخدم بشكل متكرر. يمكنك أيضا فرز الرموز المرتفعة المستخدمة بشكل متكرر. بالنسبة للرموز المرتفعة التي تكتب فيها سلسلة IF-ENER مع أعلى استخدام في كثير من الأحيان القادمة أولا. للمنخفض المستخدم بشكل متكرر، تكتب بيان التبديل.

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

يحرر : نظرا لبعض التعليقات أدناه، غيرت الجملة التي تخبر أن الجوائيات سوف تترجم دائما مفتاح التبديل إلى LUT.

Answer 2

أود أن أقترح القراءة التبديل () مقابل جدول البحث؟ من جويل في البرمجيات. خاصة، هذه الاستجابة مثيرة للاهتمام:

"المثال الرئيسي للأشخاص الذين يضيعون الوقت في محاولة تحسين الشيء الأقل أهمية".

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

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

تمت مناقشة هذه المشكلة على نطاق واسع في مجتمع VM، أود أن أقترح عليك البحث عن أوراق الباحثية في هذا المجال إذا كنت ترغب في قراءة المزيد عنها. كتب Ertl & Gregg مقالا رائعا حول هذا الموضوع في عام 2001، سلوك فعال مترجمي الآلات الافتراضية على البنية الحديثة

ولكن كما ذكرنا، أنا متأكد من أن هذه التفاصيل ليست ذات صلة لك الشفرة. هذه تفاصيل صغيرة، ويجب ألا تركز كثيرا على ذلك. يستخدم Python مترجم مفاتيح، لأنهم يعتقدون أنه يجعل الرمز أكثر قابلية للقراءة. لماذا لا تختار الاستخدام أنت الأكثر راحة؟ سيكون تأثير الأداء صغيرا إلى حد ما، وسوف تركز بشكل أفضل على رمز قراءة التعليمات البرمجية الآن؛)

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

استخدام صفيف حيث يتم تخزين عناوين الوظائف، والوصول إلى استخدام قيم العادة جيدة. ولكن باستخدام جدول التجزئة للقيام بنفس الشيء يضيف النفقات العامة

لتلخيص، لدينا:

• التكلفة (hash_table) >> التكلفة (direct_lookup_table)
• التكلفة (direct_lookup_table) ~ = التكلفة (التبديل) إذا ترجم برنامج التحويل البرمجي الخاص بك التبديل إلى جداول البحث.
• التكلفة (التبديل) >> التكلفة (direct_lookup_table) (o (n) x o (1)) إذا كان برنامج التحويل البرمجي الخاص بك لا يقوم بترجمة مفاتيح التبديل واستخدام الشرطية، ولكن لا يمكنني التفكير في أي مترجم يقوم بهذا.
• لكن الخيوط المباشرة المباشرة تجعل الرمز أقل قابلية للقراءة.

Answer 3

ما هو تعريفك ل "كفاءة"؟ إذا كنت تعني بشكل أسرع، فربما يجب عليك ملف تعريف رمز الاختبار للإجابة المحددة. إذا كنت بعد التعليمات البرمجية المرنة وسهلة تمديد، فذلك، ثم افعل نفسك أيضا واستخدم نهج الخريطة. كل شيء آخر هو مجرد تحسين مبدئيا ...

Answer 4

مثل Yossi1981 قال، قد يتم تحسين مفتاح التبديل من طاولة بحث سريعة ولكن لا يوجد ضمان، يحتوي كل مترجم على خوارزميات أخرى لتحديد ما إذا كنت تريد تنفيذ التبديل كجدول متتالية في حالة أو كجدول بحث سريع، أو ربما مزيج من الاثنين.

لكسب التبديل السريع، يجب أن تفي قيمك بالقاعدة التالية: يجب أن تكون متتالية، على سبيل المثال 0،1،2،3،4. يمكنك ترك بعض القيم ولكن أشياء مثل 0،1،2،34،43 من غير المرجح أن تكون محسنة للغاية.

السؤال حقا هو: هل أداء هذه الأهمية في طلبك؟ ولن تكون خريطة تقوم بتحميل قيمها بشكل حيوي من ملف يكون أكثر قابلية للقراءة وصيانة بدلا من بيان ضخم يمتد صفحات متعددة من التعليمات البرمجية؟

Answer 5

أنت لا تقول ما نوع الرموز الخاصة بك. إذا لم تكن أعداد صحيحة، فلا تملك التبديل فقط العمل فقط مع أنواع الأعداد الصحيحة.

Answer 6

يقول معيار C ++ لا شيء عن أداء متطلباتها، فقط أن الوظيفة يجب أن تكون هناك.

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

وأود أن أذهب حتى بالنسبة للاهم لا يهم بغض النظر عن التنفيذ منذ الوظيفة المقدمة من قبل switch و std::map يختلف (على الرغم من وجود تداخل).

لا يكون هذا النوع من التحسينات الصغرى غير ضرورية تقريبا، في رأيي.