الخوارزميات وبنى المعطيات في بايثون: الدرس الأول تحليل الخوارزميات

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

ماذا يعني تحليل الخوارزميات ؟

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

 للإجابة عن هذا السؤال، يجب علينا اولا ان نفهم الخوارزمية التي يقوم هذا المقطع البرمجي بتنفيذها. 

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

لكي نستطيع فهم أكثر كيف يمكن مقارنة المقاطع البرمجية من وجهة نظر خوارزمية، لننظر إلى المقطع البرمجي التالي في لغة بايثون

def sumOfN(n):
   theSum = 0
   for i in range(1,n+1):
       theSum = theSum + i

   return theSum

print(sumOfN(10))

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

الآن لننظر إلى مقطع برمجي آخر

def foo(tom):
    fred = 0
    for bill in range(1,tom+1):
       barney = bill
       fred = fred + barne

    return fred

print(foo(10))

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

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

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

ماهي معايير اختيار الخوارزمية الأفضل؟

بشكل عام, هناك نقطتين يجب أخذهما بعين الاعتبار عند تقييم خوارزمية ما وهما:

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

مقارنة الخوارزميات في بايثون

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

import time

def sumOfN2(n):
   start = time.time()
   theSum = 0
   for i in range(1,n+1):
      theSum = theSum + i

   end = time.time()

        return theSum,end-start

كما تلاحظ، قمنا بتسجيل قيمة الوقت عند البداية في المتحول start ثم تسجيل قيمة الوقت عند نهاية التنفيذ في المتحول end وبما ان قيمة الوقت دوما تزداد، نقوم بطرح البداية من النهاية لحساب الوقت المستغرق لتنفيذ التابع، يعيد التابع tuple تحوي قيمة المجموع والزمن اللازم لحسابه.

لنقم بتنفيذ التابع ٥ مرات من أجل حساب المجموع لأول ١٠ ألاف رقم، سنحصل على مايلي:

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(10000))
Sum is 50005000 required  0.0018950 seconds
Sum is 50005000 required  0.0018620 seconds
Sum is 50005000 required  0.0019171 seconds
Sum is 50005000 required  0.0019162 seconds
Sum is 50005000 required  0.0019360 seconds

بشكل وسطي، نلاحظ ان الزمن لم يتغير بشكل كبير في كل مرة، وهذا التغيير يعتمد على مايقوم به المعالج في لحظة تنفيذ التعليمة, ولكن يمكن اهمال الفرق لصغره واعتبار اننا نحتاج إلى حوالي 0.0019 ثانية لتنفيذ المقطع البرمجي.

ماذا لو اردنا حساب المجموع لأول 100 ألف رقم صحيح؟

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(100000))
Sum is 5000050000 required  0.0199420 seconds
Sum is 5000050000 required  0.0180972 seconds
Sum is 5000050000 required  0.0194821 seconds
Sum is 5000050000 required  0.0178988 seconds
Sum is 5000050000 required  0.0188949 seconds

نلاحظ ان الزمن ازداد مع زيادة الدخل, واصبح البرنامج يحتاج إلى ١٠ أضعاف مقارنة مع التنفيذ السابق، ماذا لو نفذنا نفس التابع من أجل اول مليون عدد صحيح؟

>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
Sum is 500000500000 required  0.1948988 seconds
Sum is 500000500000 required  0.1850290 seconds
Sum is 500000500000 required  0.1809771 seconds
Sum is 500000500000 required  0.1729250 seconds
Sum is 500000500000 required  0.1646299 seconds

أيضا نلاحظ مرة أخرى ان التابع يحتاج إلى ١٠ أضعاف من الزمن مقارنة مع المثال السابق.

الأن سنحاول تنفيذ الخوارزمية بشكل أخر، مستفيدين من المعادلة الرياضية الشهيرة التي تقوم بحساب مجموع الأعداد من ١ إلى N  

يمكن تمثيل هذه المعادلة في بايثون كمايلي:

def sumOfN3(n):
   return (n*(n+1))/2

print(sumOfN3(10))

نلاحظ أننا استغنينا عن الحلقة التكرارية لحساب المجموع. عند تنفيذ البرنامج بنفس القيم (١٠ الف, ١٠٠ ألف, مليون, ١٠ مليون, مليار) سنحصل على الخرج التالي:

Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds

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

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

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

يوجد طرق ممنهجة وقياسية لتقييم أداء خوارزمية ما سنقوم بشرحها في دروس لاحقة, حيث كان الهدف من هذا الدرس إعطاء لمحة عامة عن مفهوم التحليل الخوارزمي لمقطع برمجي ما في لغة البرمجة بايثون وكيف يزداد زمن تنفيذ البرنامج بازدياد الدخل عند وجود حلقات تكرارية.