آليات اختبار الكود البرمجي – الجزء الثاني: آلية الضغط (stress testing)

معلومات عامة  -  بواسطة:   اخر تحديث:  2020/10/24
آليات اختبار الكود البرمجي – الجزء الثاني: آلية الضغط (stress testing)

في بعض الحالات في سياق البرمجة التنافسية (competitive programming) يتعرض المشاركون لبعض الحالات حيث لا يكون سبب فشل البرنامج معروف. أي أنه هناك مشكلة منطقية في آلية عمل البرنامج، مما يتسبب في عدم تخطيه لبعض الحالات المقررة مسبقاً من قبل لجنة التحكيم. في تلك الحالات، يأتي مفهوم آلية الضغط، وهو مفهوم طوره مجتمع البرمجة التنافسية، لكن يمكن الإستفادة منه في بيئات التطوير الأخرى كذلك.  يعتمد هذا المفهوم على 4 أركان أساسية:


  • طريقة صحيحة لكن بطيئة لحل المشكلة.

  • طريقة سريعة لحل المشكلة، لكننا نشك في صحتها في جميع الحالات.

  • مولّد مدخلات محتملة للمشكلة.

  • تكرار غير نهائي (infinite loop) لتلك المدخلات.

ما جوهر تلك هذه الآلية؟


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


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


الخطوة الأولى: طريقة صحيحة لكن بطيئة لحل المشكلة


والفكرة وراء تلك الطريقة هي فكرة بسيط وبديهية (غالباً ما يطلق على ذلك النوع من الأفكار Naive Solutions)، إذا كنا نريد معرفة أكبر حاصل ضرب لمجموعة أرقام معينة، فلنقوم بحساب حاصل ضرب كل رقمين على حدى في تلك المجموعة ونختار الأكبر بينهم. يبدو ذلك مقنعاً للوهلة الأولى، ولكن لنفكر في ذلك الحل مجدداً. إذا كان لدينا مجموعة من 10 أرقام، فنحن سنقوم بإستهلاك 100 خطوة حسابية لنصل إلى الحل! لأنه لمقارنة كل رقم مع بقية الأرقام فإننا سنقوم بذلك في O(n^2) من الخطوات، حيث n هي عدد الأرقام في تلك المجموعة. يمكنك قراءة المزيد عن كيفية حساب الخطوات اللازمة للوصول للحل من هنا.



long long MaxPairwiseProduct(const vector& numbers) {


long long result = 0;


int n = numbers.size();


for (int i = 0; i < n; ++i) {


for (int j = i + 1; j < n; ++j) {


if (((long long)(numbers[i])) * numbers[j] > result) {


result = ((long long)(numbers[i])) * numbers[j];


}


}


}


return result;


}



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


الخطوة الثانية: طريقة سريعة لكن لسنا متأكدين من صحتها


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



long long MaxPairwiseProductFast(const vector& numbers) {


int n = numbers.size();


int max_index1 = -1;


for (int i = 0; i < n; ++i)


if ((max_index1 == -1) || (numbers[i] > numbers[max_index1]))


max_index1 = i;


int max_index2 = -1;


for (int j = 0; j < n; ++j)


if ((numbers[j] != numbers[max_index1]) && ((max_index2 == -1) || (numbers[j] > numbers[max_index2])))


max_index2 = j;


return ((long long)(numbers[max_index1])) * numbers[max_index2];


}



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


الخطوة الثالثة: مولّد مُدخلات لتلك المشكلة


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


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


الخطوة الرابعة: قارن الطريقتين في نفس الموقف!


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



int main() {


while (true) {


int n = rand() % 10 + 2;


cout << n << “n”;


vector a;


for (int i = 0; i < n; ++i) {


a.push_back(rand() % 100000);


}


for (int i = 0; i < n; ++i) {


cout << a[i] << ‘ ‘;


}


cout << “n”;


long long res1 = MaxPairwiseProduct(a);


long long res2 = MaxPairwiseProductFast(a);


if (res1 != res2) {


cout << “Wrong answer: ” << res1 << ‘ ‘ << res2 << “n”;


break;


}


else {


cout << “OKn”;


}


}


int n;


cin >> n;


vector numbers(n);


for (int i = 0; i < n; ++i) {


cin >> numbers[i];


}


long long result = MaxPairwiseProductFast(numbers);


cout << result << “n”;


return 0;


}



عند محاولة تشغيل الاختبار على الطريقتين بآلية الضغط، يجب أن نرى أن هناك بالفعل خطأ في الطريقة الجديدة:



3


7 3 6


0 2


OK


5


2 9 3 1 9


Wrong answer: 81 27


في هذه الحالة، لدينا الطريقة الأولى تخبرنا أن أكبر حاصل ضرب هو 81 (9*9) وتخبرنا الطريقة الثانية أن أكبر حاصل ضرب هو 27 (9*3)! المشكلة إذاً، أنه في حالة تكرار أكبر قيمة موجبة مرتين، لن تقوم الطريقة الجديدة باعتبارهما قيميتين منفصلتين، وانما ستعاملهما كأنهما قيمة واحدة، ثم ستقوم بالبحث عن ثاني أكبر قيمة موجبة! لأننا افترضنا ذلك في هذا السطر البرمجي:


if ((numbers[j] != numbers[max_index1]) && ((max_index2 == -1) || (numbers[j] > numbers[max_index2])))


بعد القليل من التفكير، ستكتشف أنك لست في حاجة لمقارنة الأرقام نفسها، بل يكفي أن تقارن أن مكان الرقم الأول مختلف عن مكان الرقم التاني (max_index1 != max_index2) وبناءً على ذلك، ستقوم بتغيير الشرط إلى:


if ((j != max_index1) && ((max_index2 == -1) || (numbers[j] > numbers[max_index2])))


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


  • آلية الضغط، تعتمد على 4 مفاهيم أساسية: طريقة بطيئة لكن صحيحة – طريقة سريعة لكن غير مجربة – مولّد مدخلات – تكرار لا نهائي بين الطريقتين بنفس المدخلات.

  • آلية الضغط يمكن استخدامها في بيئات التطوير المختلفة، وربما ستجدها بأسماء أخرى، لكن اعتماداً على نفس النهج وبناءً على نفس الآلية.

  • يعتمد نجاح الآلية في اكتشاف مواطن الخلل بشكل كبير على طريقة تصميمك لمولّد المدخلات بشكل يضمن تغطية كافة الحالات الممكنة.

  • عند وجود مشكلة ما، حاول أن تعيد تجربة الطريقتين على نطاق أصغر من الحلول، حتى تستطيع فهم المشكلة وأسبابها، ومن ثم قم بمراجعة الكود البرمجي، وأعد تشغيل الاختبار.