لماذا هو بطيء جدا بالتكرار على كبير std::القائمة ؟

Question

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

لا أحد يملك تفسيرا لهذا ؟ هو بعض كومة/ذاكرة التخزين المؤقت السلوك ؟

(حل المشكلة عن طريق تغيير قوائم std::ناقلات الأمراض المنقولة جنسيا::deque (مذهلة بنية البيانات بالمناسبة) و كل شيء فجأة ذهبت أسرع بكثير)

تحرير:أنا لست أحمق و لا الوصول إلى العناصر في منتصف القوائم.الشيء الوحيد الذي فعلته مع القوائم إلى إزالة/إضافة عناصر في نهاية/بداية و تكرار خلال كل عناصر القائمة.وأنا دائما استخدام التكرار تكرار أكثر من قائمة.

Answer 1

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

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

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

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

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

في قائمة ، نحن بحاجة إلى تتبع مؤشر من عقدة i إلى عقدة i+1, و حتى i+1 تم تحميل, نحن لا نعرف حتى من أين للبحث عن i+2.لدينا الاعتماد على البيانات ، وبالتالي فإن وحدة المعالجة المركزية يضطر إلى قراءة العقد في وقت واحد ، وأنه لا يمكن أن تبدأ في قراءة المستقبل العقد قبل الوقت ، لأنه لا يعرف حتى الآن أين هم.

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

Answer 2

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

Answer 3

إلقاء نظرة على ما يلي ستاكوفيرفلوو الموضوع.

Answer 4

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

Answer 5

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

أرى أن هذا هو علامة++ C وليس C, ولكن لأنها تفعل الشيء نفسه تحت الأغطية تجدر الإشارة إلى أنه يمكنك إضافة عناصر إلى بداية ونهاية مجموعة من خلال تخصيص كبيرة بشكل تعسفي ، realloc()ing و memmove()ing بين 2 رفيق المصفوفات إذا كنت قد نفد من الغرفة.سريع جدا.

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

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

C++ يعني كل هذا بالنسبة لك مع ناقلات المحكمة الدرجة, ولكن لا يزال يستحق التذكر ماذا يحدث تحت الأغطية.

Answer 6

[تحرير:أنا أعترف بخطئي.الأمراض المنقولة جنسيا::قائمة لا يكون المشغل[].آسف.]

فإنه من الصعب أن أقول من الوصف ، ولكن أظن أنك تحاول الوصول إلى العناصر بشكل عشوائي (أي مؤشر):

for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }

بدلا من استخدام التكرار:

for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }

كل من "ناقلات" & "deque" جيدة في الوصول العشوائي ، وذلك إما سوف تؤدي على نحو كاف لتلك الأنواع---س(1) في كلتا الحالتين.ولكن "قائمة" ليست جيدة في الوصول العشوائي.الوصول إلى القائمة من خلال مؤشر سيستغرق O(n^2) الوقت ، مقابل O(1) عند استخدام التكرار.