والتي المحكمة الحاويات التي يجب استخدامها من أجل FIFO?

Question

والتي المحكمة حاوية يناسب احتياجات بلدي أفضل ؟ أنا في الأساس 10 عناصر واسعة الحاوية التي أنا باستمرار push_back عناصر جديدة في حين pop_front جي أقدم عنصر (حوالي مليون مرة).

أنا حاليا باستخدام std::deque المهمة ولكن أتساءل عما إذا كان std::list سيكون أكثر كفاءة منذ كنت لا تحتاج إلى تخصيص نفسه (أو ربما أنا على خطأ std::deque عن std::vector?).أو هل هناك أكثر كفاءة حاوية حاجتي ؟

P. S.لا تحتاج إلى الوصول العشوائي

Answer 1

وبما أن هناك عدد لا يحصى من الإجابات ، قد يكون الخلط ، ولكن لتلخيص:

استخدام std::queue.والسبب في ذلك بسيط:وهو FIFO هيكل.تريد FIFO, استخدام std::queue.

فإنه يجعل القصد واضحا إلى أي شخص آخر ، وحتى في نفسك.A std::list أو std::deque لا.قائمة يمكن إدراج وإزالة أي مكان ، والذي هو ليس ما FIFO هيكل هو فعله ، deque يمكن إضافة و إزالة من أي طرف ، الذي هو أيضا شيء FIFO هيكل لا يمكن القيام به.

هذا هو السبب يجب عليك استخدام queue.

الآن انت سألت عن الأداء.أولا: تذكر دائما هذه قاعدة مهمة من الإبهام: كود الجيدة أولا ، الأداء الماضي.

والسبب في ذلك بسيط:الناس الذين يسعون جاهدين من أجل الأداء قبل النظافة والأناقة دائما تقريبا الانتهاء الماضي.التعليمات البرمجية الخاصة بهم يصبح اندلق من الهريسة, لأنها قد تخلى عن كل ما هو جيد من أجل الحصول على حقا لا شيء من ذلك.

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

أن كل ما قال ، std::queue هو فقط محول.فإنه يوفر واجهة آمنة ، ولكن يستخدم حاوية مختلفة في الداخل.يمكنك اختيار هذا الكامنة الحاويات ، وهذا يتيح قدرا كبيرا من المرونة.

لذلك ، والتي الأساسية الأخرى الحاوية يجب أن تستخدم ؟ ونحن نعلم أن std::list و std::deque سواء توفير الوظائف اللازمة (push_back(), pop_front(), ، front()), كيف نقرر ؟

أولا نفهم أن تخصيص (و deallocating) الذاكرة ليست سريعة ، عموما ، لأنه ينطوي على الخروج إلى نظام التشغيل ويطلب منها أن تفعل شيئا.A list أن تخصيص الذاكرة في كل مرة يتم إضافة شيء و تخصيص ذلك عندما يذهب بعيدا.

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

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

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

وهذا بخلاف قائمة البيانات المخصصة في وقت واحد.هذا يعني أن البيانات يمكن أن تنتشر في كل مكان في الذاكرة, ذاكرة التخزين المؤقت سوف يكون الأداء سيئا.

لذا تفكر في ذلك ، deque يجب أن يكون خيارا أفضل.هذا هو السبب في حاوية الافتراضي عند استخدام queue.أن كل هذا لا يزال مجرد (جدا) تخمين:سيكون لديك إلى ملف التعريف هذا القانون ، وذلك باستخدام deque في اختبار واحد ، list في الآخر أن تعرف حقا معينة.

ولكن تذكر:الحصول على رمز العمل مع واجهة نظيفة ، ثم القلق حول الأداء.

جون يثير القلق أن لف list أو deque سوف يؤدي إلى انخفاض الأداء.مرة أخرى, ولا أستطيع أن أقول لبعض دون التنميط ذلك بأنفسنا, ولكن هناك احتمالات أن المترجم مضمنة المكالمات التي queue يجعل.هذا هو عندما تقول queue.push(), انه فقط يقول queue.container.push_back(), تخطي استدعاء دالة تماما.

مرة أخرى, هذا هو فقط تكهنا ، ولكن باستخدام queue لن تتحلل الأداء عند مقارنة باستخدام الحاويات الأساسي الخام.كما قلت من قبل, استخدم queue, لأنه نظيفة, وسهلة الاستخدام, و آمن و إذا كان حقا يصبح مشكلة الملف والاختبار.

Answer 2

الدفع std::queue. وبعد يلف نوع الحاويات الأساسية، والحاوية الافتراضية هي std::deque.

Answer 3

حيث الأداء يهم حقا، تحقق من زيادة مكتبة العازلة الدائرية.

Answer 4

أنا باستمرار push_back عناصر جديدة في حين pop_front جي أقدم عنصر (حوالي مليون مرة).

مليون ليس حقا عدد كبير في الحوسبة. كما اقترح الآخرون، استخدم أ std::queue كما الحل الأول الخاص بك. في الحدث غير المرجح أن تكون بطيئا للغاية، حدد عنق الزجاجة باستخدام Profiler (لا تخمن!) وإعادة التنفيذ باستخدام حاوية مختلفة مع نفس الواجهة.

Answer 5

لما لا std::queueب كل ما لديه هو push_back و pop_front.

Answer 6

أ طابور ربما واجهة أبسط من deque. ولكن لمثل هذه القائمة الصغيرة، فإن الفرق في الأداء هو ربما ضئيل.

الشيء نفسه ينطبق على قائمة. وبعد إنه لأسفل فقط إلى اختيار ما تريده.