الأمراض المنقولة جنسيا::زوج<int, int=""> مقابل البنية مع اثنين الباحث هو

Question

في ACM سبيل المثال ، كان بناء طاولة كبيرة عن البرمجة الديناميكية.كنت قد لتخزين الأعداد الصحيحة اثنين في كل خلية ، لذلك قررت أن تذهب std::pair<int, int>.غير أن تخصيص مجموعة ضخمة من 1.5 ثانية:

std::pair<int, int> table[1001][1001];

بعد ذلك, لقد تغير هذا الكود

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

وتخصيص أخذت 0 ثانية.

ما الذي يفسر هذا الفارق الكبير في الوقت المناسب ؟

Answer 1

وstd::pair<int, int>::pair() منشئ تهيئة الحقول مع القيم الافتراضية (صفر في حالة int) وstruct Cell الخاص بك لا (لأن لديك سوى المنشئ الافتراضي الذي تم إنشاؤه تلقائيا أن لا يفعل شيئا).

وتهيئة يتطلب الكتابة إلى كل حقل الذي يتطلب مجموعة كبيرة من ذاكرة الوصول إلى تلك هي المرة نسبيا طويلا. مع struct Cell يتم أي شيء بدلا من ذلك وتفعل شيئا قليلا أسرع.

Answer 2

إجابات حتى الآن لا شرح كامل حجم المشكلة.

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

هنا هو بلدي المنطق:

على افتراض كنت على آلة قديمة ، ويقول التوالي في 1.33 ghz, ثم 1.5 ثانية 2e9 الساعة دورات.كنت قد حصلت 2e6 أزواج لبناء لذلك بطريقة أو بأخرى كل زوج منشئ هو أخذ 1000 دورة. لأنها لا تأخذ 1000 دورة استدعاء منشئ مجرد مجموعات عددين إلى الصفر. لا أستطيع أن أرى كيف ذاكرة التخزين المؤقت يفتقد تجعل تأخذ هذا الوقت الطويل.أعتقد أنه إذا كان العدد أقل من 100 دورات.

اعتقدت أنه سيكون من المثير للاهتمام أن نرى أين كل هذه دورات وحدة المعالجة المركزية تسير.لقد استخدمت أسوأ أقدم برنامج التحويل البرمجي C++ يمكن أن تجد أن أرى إن كنت أستطيع تحقيق مستوى الهدر المطلوبة.أن المترجم كان VC++ v6.في وضع التصحيح ، فإنه لا شيء أنا لا أفهم.وقد حلقة كبيرة أن يدعو الزوج منشئ لكل عنصر في الجدول عادلة بما فيه الكفاية.أن منشئ مجموعات القيمتين إلى الصفر - عادل بما فيه الكفاية.ولكن قبل القيام بذلك ، فإنه يضع كل بايت في 68 بايت المنطقة 0xcc.تلك المنطقة فقط قبل بدء الطاولة الكبيرة.ثم الكتابة فوق العنصر الأخير من تلك المنطقة مع 0x28F61200.كل مكالمة الزوج منشئ يكرر هذا.ويفترض أن هذا هو نوع من حفظ الكتاب عن طريق المترجم حتى يعرف ما هي المناطق تهيئة عند التحقق من مؤشر الأخطاء في وقت التشغيل.أحب أن أعرف بالضبط ما هو.

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

Answer 3

وتخميني انها وسيلة الأمراض المنقولة جنسيا :: يتم إنشاء زوج. هناك المزيد من النفقات العامة خلال استدعاء منشئ الزوج 1001x1001 مرات مما كانت عليه عندما كنت مجرد تخصيص مجموعة الذاكرة.

Answer 4

وهذه كلها تخمينات جيدة جدا، ولكن كما يعلم الجميع، والتخمينات لا يمكن الاعتماد عليها.

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

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

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

Answer 5

وهو حقا مثال جيد عن واحد يجب أن تكتب C ++ واستخدام STL بعناية. أي أفكار؟

ويعمل مشروعي على C & C ++ أداة اختبار مستوى الرمز القياسي الذي نحن سوف تجعل الكثير من نماذج التعليمات البرمجية لتبين ما هو "جيد" رمز وما هو "سيئة" الترميز العادة. يمكنك الاطلاع على http://effodevel.googlecode.com لمعرفة المزيد عن C9B.M. التخطيط. أي شخص إذا كنت قد شهدت الكثير من مثل هذه الحالات، يرجى التكرم الانضمام للمشروع لمساعدتنا.