أداء الخوارزميات Algorithms Performance

أداء الخوارزميات Algorithms Performance

كيف يمكن تقييم أداء الخوارزميات Algorithms Performance ...؟! وما طُرق تحليل الخوارزميات Algorithms Analysis..؟ و كيف يؤثر حجم المدخلات على أداء الخوارزمية…؟؟!! وما تقنيات ُتحسين أداء الخوارزميات ..!!!

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

في هذا المقال سنتعرف على :

• مفاهيم في تصميم الخوارزميات.
• أداء الخوارزميات Algorithms Performance.
• تحليل أداء الخوارزميات Algorithms analysis.
• مفاهيم في تحليل أداء الخوارزميات.
• تقنيات ُتحسين أداء الخوارزميات.

مفاهيم في تصميم الخوارزميات

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

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

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

أداء الخوارزميات Algorithms Performance

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

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

تحليل أداء الخوارزمية يساعد على تحديد الخوارزمية الأفضل لحل المشكلة وتقييم أداء النظام الحاسوبي في العملية. ويمكن استخدام التحليل لتحديد النقاط الضعيفة في الخوارزمية وتحسين الأداء العام للنظام الحاسوبي.

وتتوفر عدة طرق لتحليل أداء الخوارزميات. واحدة من هذه الطرق هي تحليل الحد الأعلى للوقت والذاكرة. يستخدم هذا النوع من التحليل لتقدير أسوأ حالة من حيث الوقت والذاكرة التي يمكن للخوارزمية أن تستهلكها في العملية الأسوأ. ويتم تحليل هذا الحد الأعلى للوقت والذاكرة باستخدام مفاهيم النمو الرياضي، مثل (Big-O) notation.

تحليل أداء الخوارزميات Algorithms analysis

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

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

الآن مقدار المساحة الإضافية التي تتطلبها الخوارزمية ليس مصدر قلق كبير ، ومع هذا فالقلق حيال مساحة الذاكرة لا يزال قائم ، وبالطبع يتفاوت بين الذاكرة الرئيسية ROM ، والذاكرة الثانوية RAM الأبطأ ، وذاكرة التخزين المؤقت cache .

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

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

قياس حجم المدخلاقياس حجم المدخلات Measuring Inputs Size

نبدأ بالملاحظة الواضحة التي مفادها أن جميع الخوارزميات تقريبًا تعمل لفترة أطول على مدخلات أكبر. على سبيل المثال ، يستغرق الأمر وقتًا أطول لفرز المصفوفات الأكبر وضرب المصفوفات الأكبر وما إلى ذلك. لذلك ، من المنطقي لنحقق في كفاءة الخوارزمية نفرض دالة فيها n تشير إلى حجم إدخال الخوارزمية لهذا فإن n لابد ان تكون عدد صحيح موجب (n = number of inputs) ويقاس حجم المدخلات بعدد البتات bits ويمثل بـ b لتحسب كالتالي:

وحدات قياس وقت التشغيل Units for Measuring Running Time

المسألة التالية تتعلق بوحدات قياس وقت تشغيل الخوارزمية بالطبع ، يمكننا ببساطة استخدام بعض الوحدات القياسية لقياس الوقت - ثانية ، أو ميلي ثانية ، وهكذا - لقياس وقت تشغيل برنامج يقوم بتطبيق الخوارزمية. ومع ذلك ، هناك عيوب واضحة لمثل هذا النهج:

• الاعتماد على سرعة كمبيوتر معين .
• والاعتماد على جودة البرنامج الذي ينفذ الخوارزمية والمجمع Compiler المستخدم في إنشاء كود الآلة.
• وصعوبة تسجيل وقت التشغيل الفعلي نظرًا لأننا نتبع مقياسًا لكفاءة الخوارزمية ، نود الحصول على مقياس لا يعتمد على هذه العوامل الخارجية.

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

على سبيل المثال ، تعمل معظم خوارزميات الفرز من خلال مقارنة عناصر (مفاتيح keys ) قائمة يتم فرزها مع بعضها البعض ، لمثل هذه الخوارزميات ، العملية الأساسية هي مقارنة رئيسية.

وكمثال آخر ، تتضمن خوارزميات المشكلات الرياضية عادةً بعض أو كل العمليات الحسابية الأربع: الجمع (+) والطرح (-) والضرب (*) والقسمة (/). من بين العمليات الأربعة ، فإن العملية الأكثر استهلاكا للوقت هي القسمة ، يليها الضرب ثم الجمع والطرح ، مع مراعاة الأخيرين معًا.

مع أن هذا لا ينطبق على الخوارزميات غير التكرارية والعودية. لكن طريقة احتساب كفاءة الخوارزمية في حالات مثل الأمثلة السابقة يعتمد على عدد المرات التي يتم فيها تنفيذ العملية الأساسية للخوارزمية على مدخلات بحجم n . من هنا جاءت دراسة ترتيب النمو Orders of Growth.

ترتيب النمو Orders of Growth

لكي نفهم مصطلح تريب النمو او Orders of Growth يجب ان نرى بعض الامثلة:

انظر /ي لهذا الجزء من خوارزمية 1:

........
Int  n = 100
Int [] counts  = new int [n]
For (int  i=0; i<counts.length; i++)
........ 

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

لننظر إلى هذا الجزء من هذه الخوارزمية 2

........
Int  n = 100
Int [] [] counts  = new int [n]
For (int  i=0; i<counts.length; i++)
		For(int j=0; j<counts[i].length; i++)
........ 

في هذه الخوارزمية تتمثل العملية الاساسية في التكرار إلا أن التكرار هنا لايمثل خوارزمية خطية فهو حلقتين متداخلتين من التكرار (Nested Loop ) ولازال وقت التنفيذ هنا يعتمد على قيمة n ... وهذا لأن عدد تكرار الحلقة الداخلية يعتمد على عدد مرات تكرار الحلقة الخارجية المرتبط بـ n .

الخلاصة هذه الحالات وغيرها انتهت دراستها إلى سبع دوال  g(n)  تُمثل الدوال ترتيب النمو للخوارزميات تعتمد هذه الداول على هيكل البيانات Data Structure المستخدم وتصف هذه الدوال طول وقت التنفيذ للخوارزمية و هي:

• الثوابث Constant ≈ 1


• اللوغاريتم Logarithmic ≈ log n


• الخطية Linear ≈ n


• لوغاريتمية خطية Log linear ≈ n log


• التربيعية Quadratic ≈ n²


• التكعيبية Cubic ≈ n³


• الاسية Exponential ≈ 2 ⁿ

لاحظ /ي تأثير مقدار النمو في قيمة n في الجدول التالي :

f(n)	n=1	n=2	n=4	n=8	n=16	n=32
1	1	1	1	1	1	1
log n	0	1	2	3	4	5
n	1	2	4	8	16	32
n log n	0	2	8	24	64	160
n2	1	4	16	64	256	1024
n3	1	8	64	12	4096	32768
2n	2	4	16	256	65536	4294967296

مفاهيم في تحليل أداء الخوارزميات

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

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

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

تقنيات ُتحسين أداء الخوارزميات

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

• التخزين المؤقت (Caching): يتم استخدام التخزين المؤقت لتخزين النتائج السابقة للعمليات الحسابية المكررة. عندما يتم تنفيذ الخوارزمية مرة أخرى مع نفس البيانات الدخل، يمكن استخدام النتائج المخزنة في التخزين المؤقت بدلاً من إعادة حسابها من الصفر، مما يوفر وقتًا وموارد.
• تقديم البيانات (Data Preprocessing): يمكن تحسين أداء الخوارزميات عن طريق تنقية وتحضير البيانات قبل تنفيذ الخوارزمية. يمكن تطبيق تقنيات مثل تحويل البيانات، تجميع البيانات، وإزالة القيم المفقودة لتحسين كفاءة الخوارزمية وتقليل الضوضاء.
• التوازي (Parallelism): يتعلق الأمر بتنفيذ عمليات متعددة في نفس الوقت لتحسين أداء الخوارزميات. يمكن تقسيم المشكلة إلى عدة أجزاء وتنفيذها متزامنة على عدة معالجات أو خيوط (Threads)، مما يؤدي إلى زيادة سرعة التنفيذ وتحسين أداء الخوارزمية.
• الخوارزميات المتقدمة: في بعض الحالات، يمكن استخدام خوارزميات متقدمة أو محسنة لتحسين أداء الخوارزميات الأساسية. على سبيل المثال، يمكن استخدام خوارزميات البحث أو الفرز المحسنة التي تعتمد على هياكل بيانات (Data Structures) مخصصة مثل الأشجار أو القوائم المرتبة.
• تحليل وتحسين الوقت التنفيذي (Time Complexity Analysis): يمكن تحسين أداء الخوارزميات عن طريق تحليل وفهم وقت التنفيذ المتوقع لكل خوارزمية. يمكن تحسين الخوارزميات عن طريق اختيار أكثر الخوارزميات فعالية وأقل تكلفة وتعديل الخوارزميات الحالية لتقليل وقت التنفيذ.
• التحسين الذكي (Heuristic Optimization): تستخدم هذه التقنية في حل المشاكل التي تتطلب البحث عن أفضل حل ممكن في مجالات ضخمة من الحلول المحتملة. تستند هذه التقنية إلى استخدام الخوارزميات التي تقدم تقديرًا ذكيًا للحل بدلاً من فحص جميع الحلول المحتملة. هذا يسمح بتوفير وقت التنفيذ وموارد الحاسوب وتحقيق أداء مقبول في الوقت نفسه.

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

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