ناقلات تهيئة أبطأ من مجموعة ... لماذا؟

Question

وحاولت 2 أشياء: (رمز زائف أدناه)

int arr[10000];
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

و

vector<int> arr(10000);
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

وركضت كل من البرامج وتوقيت ذلك باستخدام "الوقت" شل القيادة. يعمل البرنامج 1 في 5 ثواني، البرنامج 2 أشواط في 30 ثانية. ركضت كلا البرنامجين مع المترجم الأمثل قيد التشغيل، وركض كلا البرنامجين في نفس الوقت تقريبا (0.38s). فأنا في حيرة من هذه النتائج. يمكن للشخص الرجاء شرح لي لماذا يحدث هذا؟

وشكرا!

Answer 1

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

Answer 2

في وضع التصحيح، تطبيقات std::vector توفر الكثير من وقت التشغيل التحقق من سهولة الاستخدام. هذا الفحص غير متوفر للصفائف الأم. على سبيل المثال، في VC2008، إذا كنت تجميع سبيل المثال vector في وضع التصحيح، وسيكون هناك range-checking <م> حتى في حالة operator[].

Answer 3

إذا تنفيذ غير الأمثل ناقلات الخاص بك هو المنفذ حدود التحقق، التي من شأنها أن تمثل التناقض.

Answer 4

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

وأنت ترى فرقا 6 إلى 1 في الأداء، أليس كذلك؟ فقط تشغيل بطيء واحد واضغط على زر "توقف". بعد ذلك ننظر في مكدس الاستدعاءات. الاحتمال هو 5 من 6 (83٪) التي سوف ترى بالضبط كيف تنفق هذه 25 ثانية إضافية. تفعل ذلك عدة مرات للحصول على أكبر قدر من البصيرة كما تريد.

لحالة الأمثل، وتفعل الشيء نفسه مع برنامج 1. نظرا لأنه 13 مرات أبطأ من البرنامج الأمثل، وسترى السبب على كل "وقفة"، مع احتمال 12/13 = 92٪.

وهذا هو تطبيق هذه التقنية .

Answer 5

ولأنه عندما كنت أكتب وصول ناقلات (10000)؛ إنشاء كائن، الذي يطلق عليه من وظائف ... عندما وسيكون أبطأ من عرج إنشاء الباحث آر [10000]؛

Answer 6

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

من ناحية أخرى، في حين أن vector على المكدس، يتم توزيع البيانات لstd::vector مكان آخر (افتراضيا هو المخصصة على كومة عبر std::allocator). الوصول إلى البيانات في vector ينطوي على الوصول إلى البيانات على الكومة. هذا هو أبطأ بكثير من الوصول إلى البيانات على المكدس.

ويمكنك الحصول على شيء للعقوبة الأداء، وإن كان. std::vector هو growable، في حين أن مجموعة منتظمة ليست كذلك. أيضا، لا يكون حجم std::vector أن يكون تجميع وقت ثابت، في حين أن حجم صفيف على المكدس لا. وهناك مجموعة و-تخصيص كومة (عبر operator new[]) ليس من الضروري أن يكون ثابت وقت الترجمة. إذا كنت مقارنة خصصت مجموعة كومة مع std::vector ستجد أداء هو أقرب من ذلك بكثير.

int* arr = new int[10000];
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

delete[] arr; // std::vector does this for you