لوحة المتصدرين

لا يملك الكثير من المبرمجين الذين يصنعون أروع البرامج وأكثرها فائدةً اليوم -مثل العديد من الأشياء التي نراها على الإنترنت أو نستخدمها يوميًا- خلفيةً نظريةً في علوم الحاسوب، لكنهم لا يزالون مبرمجين رائعين ومبدعين ونقدِّر ما يبنونه، حيث تملك علوم الحاسوب النظرية استخداماتها وتطبيقاتها، ويمكن أن تكون عمليةً تمامًا. يستهدف هذا المقال المبرمجين الذين يعرفون عملهم جيدًا ولكنهم لا يملكون خلفيةً نظريةً في علوم الحاسوب، وذلك من خلال واحدة من أكثر أدوات علوم الحاسوب واقعيةً، وهي: صيغة O الكبير Big O notation، وتحليل تعقيد الخوارزمية algorithm complexity. تُعَدّ هذه الأداة واحدةً من الأدوات المفيدة عمليًا للأشخاص العاملين في المجال الأكاديمي لعلوم الحاسوب، وفي إنشاء برامج على مستوى الإنتاج في الصناعة، لذلك نأمل أن تتمكن من تطبيقها في الشيفرة الخاصة بك لتحسينها بعد قراءة هذا المقال، كما يُفتَرض أن تكون قادرًا على فهم جميع المصطلحات الشائعة التي يستخدمها المختصون في علوم الحاسوب، مثل مصطلحات: التعقيد "Big O"، و"السلوك المقارب asymptotic behavior"، و"تحليل الحالة الأسوأ worst-case analysis" بعد قراءة هذا المقال. يستهدف هذا المقال أيضًا طلاب المدارس الإعدادية والثانوية في أي مكان في العالم، والذين يتنافسون دوليًا في الأولمبياد الدولي للمعلوماتية، أو مسابقة الخوارزميات الطلابية، أو مسابقات أخرى مماثلة. لا يحتوي هذا المقال على أي متطلبات رياضية مسبقَة، كما سيمنحك الخلفية التي ستحتاجها لمواصلة دراسة الخوارزميات مع فهمٍ أقوى للنظرية الكامنة وراءها، وننصح الأشخاص الذين يشاركون في هذه المسابقات الطلابية بشدة بقراءة هذا المقال التمهيدي بأكمله ومحاولة فهمه تمامًا، لأنه سيكون ضروريًا أثناء دراسة الخوارزميات وتعلُّم المزيد من التقنيات المتقدِّمة. سيكون هذا المقال مفيدًا للمبرمجين الصناعيين الذين ليس لديهم خبرة كبيرة في علوم الحاسوب النظرية، ونظرًا لتخصيص هذا المقال للطلاب، فقد يبدو في بعض الأحيان مثل كتاب مدرسي، حيث قد ترى بعض الموضوعات شديدة الوضوح لأنك رأيتها خلال سنوات دراستك على سبيل المثال، لذلك يمكنك تخطيها إذا شعرت أنك تفهمها. تصبح الأقسام الأخرى أقل عمقًا ونظريًا، حيث يحتاج الطلاب المشاركون في هذه المسابقات إلى معرفة المزيد عن الخوارزميات النظرية أكثر من ممارس المهنة العادي، ولا تزال معرفة هذه الأشياء أمرًا جيدًا بما أنها ليست صعبةً كثيرًا، لذا يستحق ذلك الأمر إعطاءه بعضًا من وقتك. لا تحتاج إلى خلفية رياضية لأن النص الأصلي لهذا المقال قد استهدف طلاب المدارس الثانوية، لذلك سيكون أي شخصٍ لديه بعض الخبرة في البرمجة -أي إن عرف ما هي العَودية recursion على سبيل المثال- قادرًا على المتابعة دون أي مشكلة. ستجد خلال هذا المقال العديد من الروابط التي تنقلك للاطلاع على مواد مهمة خارج نطاق موضوع المقال، إذ يُحتمل درايتك بمعظم هذه المفاهيم إذا كنت مبرمجًا صناعيًا؛ أما إذا كنت طالبًا مشاركًا في المسابقات، فسيعطيك اتباع هذه الروابط أفكارًا حول مجالات أخرى من علوم الحاسوب أو هندسة البرمجيات التي ربما لم تستكشفها بعد، والتي يمكنك الاطلاع عليها لتوسيع اهتماماتك. يصعب على الكثير من المبرمجين والطلاب فهم تحليل تعقيد الخوارزمية وصيغة Big O، أو يخافون منه، أو يتجنبونه تمامًا ويعدّونه عديم الفائدة، لكنه ليس صعبًا أو نظريًا كما قد يبدو للوهلة الأولى. يُعَدّ تعقيد الخوارزمية طريقةً لقياس سرعة تشغيل برنامج ما أو خوارزمية ما، لذلك يُعَد أمرًا عمليًا. الدافع Motivation يوجد أدوات لقياس مدى سرعة تشغيل البرنامج، فهناك برامج تسمى المشخِّصات profilers، حيث تقيس وقت التشغيل بالميلي ثانية ويمكنها مساعدتنا في تحسين الشيفرة الخاصة بنا عن طريق تحديد الاختناقات bottlenecks، وعلى الرغم من فائدة هذه الأداة إلا أنها ليست ذات صلة فعلية بتعقيد الخوارزمية، فتعقيد الخوارزمية مصمَّمٌ لمقارنة خوارزميتين ضمن المستوى المثالي، أي تجاهل التفاصيل منخفضة المستوى، مثل: لغة برمجة التطبيق، أو العتاد الذي تعمل عليه الخوارزمية، أو مجموعة تعليمات وحدة المعالجة المركزية CPU. عندما نريد مقارنة الخوارزميات من حيث ماهيتها -أي الأفكار التي تُعرّفنا كيفية حساب شيءٍ ما-، فلن يساعدنا العد بالميلي ثانية في ذلك، إذ يُحتمَل أن تعمل الخوارزمية السيئة والمكتوبة بلغة برمجة منخفضة المستوى مثل لغة التجميع Assembly، بصورة أسرع بكثير من خوارزمية جيدة مكتوبة بلغة برمجة عالية المستوى مثل بايثون، أو روبي، لذلك يجب تحديد معنى "الخوارزمية الأفضل". بما أن الخوارزميات هي برامج تجري عمليات حسابية فقط، ولا تجري أشياءً أخرى تقوم بها الحواسيب، مثل: مهام الشبكات، أو دخل المستخدم، وخرجه؛ فسيسمح لنا ذلك بتحليل التعقيد بقياس مدى سرعة البرنامج عند إجراء العمليات الحسابية. تتضمن أمثلة العمليات الحسابية البحتة العمليات العشرية العددية numerical floating-point operations، مثل: الجمع والضرب، أو البحث داخل قاعدة بيانات متناسبة مع الذاكرة العشوائية RAM عن قيمة معينة، أو تحديد المسار الذي ستمر به شخصية ذكاء اصطناعي في لعبة فيديو، بحيث يتعين عليها فقط السير مسافةً قصيرةً داخل عالمها الافتراضي (كما في الشكل الآتي)، أو تشغيل تطابق نمط تعبير نمطي regular expressions مع سلسلة، فالعمليات الحسابية موجودة في كل مكان في البرامج الحاسوبية. تستخدم شخصيات الذكاء الاصطناعي في ألعاب الفيديو الخوارزميات لتجنب العقبات عند تنقّلها في العالم الافتراضي يُعَدّ تحليل التعقيد أداةً لشرح كيفية تصرّف الخوارزمية مع زيادة حجم الدخل. وهنا نتساءل، إذا زدنا الدخل، فكيف ستتصرّف الخوارزمية؟ أي إذا كانت الخوارزمية الخاصة بنا تستغرق ثانيةً واحدةً للتشغيل بالنسبة إلى دخلٍ بحجم 1000، فكيف ستتصرف الخوارزمية إذا ضاعفنا حجم الدخل؟ هل ستعمل بالسرعة نفسها، أم بنصف السرعة، أم أبطأ بأربع مرات؟ يُعَدّ هذا مهمًا في البرمجة العملية لأنه سيسمح لنا بالتنبؤ بسلوك الخوارزمية عندما تصبح بيانات الدخل أكبر؛ فمثلًا، إذا أنشأنا خوارزميةً لتطبيق ويب يعمل جيدًا مع 1000 مستخدِم، وقِسنا وقت تشغيله باستخدام تحليل تعقيد الخوارزمية، فيمكننا توقُّع ما سيحدث بمجرد حصولنا على 2000 مستخدِم بدلًا من ذلك. يمنحنا تحليل التعقيد في مسابقات الخوارزميات رؤيةً عن المدة التي سيستغرقها تشغيل الشيفرة لأكبر حالات الاختبار التي تُستخدَم لاختبار صحة البرنامج، لذلك إذا قِسنا سلوك برنامجنا مع دخل صغير، فسنعرف سلوكه مع الدخل الأكبر. لنبدأ بمثال بسيط هو إيجاد العنصر الأكبر في مصفوفة. عد التعليمات سنستخدم لغات برمجة مختلفة لأمثلة هذا المقال، لكن لا تيأس إن لم تعرف لغة برمجة معينة، وبما أنك تعرف البرمجة، فيجب أن تكون قادرًا على قراءة الأمثلة دون أي مشكلة حتى إن لم تكن على دراية بلغة البرمجة المختارة، لأنها ستكون بسيطةً ولن نستخدم أية ميزات خاصة بلغة معينة. إذا كنت طالبًا منافسًا في مسابقات الخوارزميات، فيُرجَّح استخدمك لغة C++‎، لذلك لن تواجه مشكلة، وبالتالي نوصي في هذه الحالة التدرّب باستخدام لغة C++‎. يمكن البحث عن العنصر الأكبر في مصفوفة باستخدام شيفرة لغة جافا سكريبت التالية، بافتراض أن مصفوفة الدخل هي A، وحجمها n: var M = A[ 0 ]; for ( var i = 0; i < n; ++i ) { if ( A[ i ] >= M ) { M = A[ i ]; } } أول شيء سنفعله هو حساب عدد التعليمات الأساسية التي ينفذها هذا الجزء من الشيفرة، حيث سنفعل هذا مرةً واحدةً فقط، ولن يكون ضروريًا لاحقًا، لذلك تحمَّل لبضع لحظات. نقسّم الشيفرة إلى تعليماتٍ بسيطة عندما نحللها، فهذه التعليمات البسيطة هي ذات التعليمات، أو قريبة منها، والتي يمكن لوحدة المعالجة المركزية من تنفيذها مباشرةً، كما سنفترض أن معالجنا يمكنه تنفيذ العمليات التالية على أساس تعليمة واحدة لكل منها: إسناد قيمة لمتغير. البحث عن قيمة عنصر معين في مصفوفة. مقارنة قيمتين. زيادة قيمة. العمليات الحسابية الأساسية، مثل: الجمع، والضرب. سنفترض أن التفرع -أي الاختيار بين جزئي if وelse بعد تقييم شرط if- سيحدث على الفور ولن يحسب هذه التعليمات. السطر الأول من الشيفرة السابقة هو: var M = A[ 0 ]; يتطلب هذا السطر تعليمتين: إحداهما للبحث عن العنصر A[ 0 ]، والأخرى لإسناد قيمته إلى M، حيث سنفترض أن قيمة n تساوي 1 على الأقل دائمًا، كما تتطلّب الخوارزمية هاتين التعليمتين دائمًا، بغض النظر عن قيمة n، ويجب أيضًا تشغيل شيفرة تهيئة حلقة for دائمًا، ويعطينا هذا تعليمتين أخريين، هما: الإسناد assignment، والمقارنة comparison: i = 0; i < n; ستشغَّل هاتان التعليمتان قبل أول تكرار من حلقة for، كما نحتاج إلى تعليمتين إضافيتين للتشغيل بعد كل تكرار لحلقة for، وهما: زيادة المتغير i، ومقارنة للتحقق من أننا ما زلنا ضمن الحلقة، أي كما يلي: ++i; i < n; إذا تجاهلنا جسم الحلقة، فسيكون عدد التعليمات التي تحتاجها هذه الخوارزمية هو 4 + 2n، أي 4 تعليمات في بداية حلقة for، وتعليمتين في نهاية كل تكرار من n تكرار. يمكننا الآن تحديد دالة رياضية f( n )، حيث تعطينا عدد التعليمات التي تحتاجها الخوارزمية عند إعطاء n، أي لدينا f( n ) = 4 + 2n عندما يكون جسم حلقة for فارغًا. تحليل الحالة الأسوأ Worst-case analysis لدينا بالنظر إلى جسم حلقة for عملية بحث في مصفوفة، وعملية مقارنة تحدث دائمًا، كما يلي: if ( A[ i ] >= M ) { … أي يوجد تعليمتان، ولكن اعتمادًا على قيم المصفوفة، فقد يعمل جسم تعليمة if وقد لا يعمل. فإذا تحقق A[ i ] >= M، فسنشغّل هاتين التعليمتين الإضافيتين -أي البحث في مصفوفة والإسناد-، كما يلي: M = A[ i ] لكن لا يمكننا الآن تحديد الدالة f( n ) بسهولة، وذلك لعدم اعتماد عدد التعليمات على n فقط، وإنما على الدخل أيضًا، فإذا كان الدخل A = [ 1, 2, 3, 4 ] مثلًا، فستحتاج الخوارزمية إلى تعليمات أكثر مما إذا كان الدخل A = [ 4, 3, 2, 1 ]. نفكر عند تحليل الخوارزميات في أسوأ سيناريو غالبًا، فما هو أسوأ شيء يمكن حدوثه لخوارزميتنا؟ ومتى تحتاج الخوارزمية إلى معظم التعليمات لإكمالها؟ في هذه الحالة، يحدث ذلك عندما يكون لدينا مصفوفة بترتيب تصاعدي مثل A = [ 1, 2, 3, 4 ]، حيث يجب استبدال المتغير M في كل مرة، وبالتالي، سينتج عن ذلك تنفيذ معظم التعليمات، ويُطلَق على هذه الحالة اسم تحليل الحالة الأسوأ Worst-case analysis؛ وهذا ليس أكثر من مجرد التفكير في الحالة التي تحدث عندما نكون الأقل حظًا. لدينا في أسوأ الحالات 4 تعليمات للتشغيل داخل جسم حلقة for، لذلك لدينا f( n ) = 4 + 2n + 4n = 6n + 4، حيث تعطينا الدالة f عدد التعليمات التي قد تكون مطلوبةً في الحالة الأسوأ بالاعتماد على حجم المشكلة n. السلوك المقارب Asymptotic behavior تمنحنا الدالة السابقة فكرةً جيدةً عن مدى سرعة الخوارزمية، ولكن كما وعدناك، فلن تحتاج إلى القيام بالمهمة الشاقة المتمثلة في عد التعليمات في البرنامج. يعتمد عدد تعليمات وحدة المعالجة المركزية الفعلية اللازمة لكل عبارة لغة برمجة، على مُصرِّف compiler لغة البرمجة، وكذا على مجموعة تعليمات وحدة المعالجة المركزية المتاحة، سواءً كان معالج AMD أو Intel Pentium على حاسوبك، أو كان معالج MIPS على Playstation 2 الخاصة بك، وسنتجاهل ذلك أيضًا كما ذكرنا سابقًا. سنشغّل الآن الدالة "f" الخاصة بنا من خلال "مرشِّح filter" ليساعدنا في التخلص من التفاصيل الصغيرة التي يفضّل المتخصصون في علوم الحاسوب تجاهلها. يوجد قسمان في الدالة f التي تساوي 6n + 4، وهما: 6n، و4، كما لا نهتم في تحليل التعقيد إلا بما يحدث لدالة عد التعليمات عندما يكبر دخل البرنامج (n)، ويتماشى هذا مع الأفكار السابقة لسلوك "السيناريو الأسوأ" الذي ينص على الاهتمام بكيفية تصرّف الخوارزمية عند معالجتها بصورة سيئة، أي عندما تفعل هذه الخوارزمية شيئًا صعبًا، وهذا مفيد حقًا عند مقارنة الخوارزميات. إذا تغلبت خوارزمية على خوارزمية أخرى عند استخدام دخل كبير، فيُرجَّح أن الخوارزمية الأسرع ستبقى أسرع عند إعطاء دخلٍ أسهل وأصغر. سنحذف الأقسام التي تنمو ببطء ونبقي فقط الأقسام التي تنمو بسرعة عندما تصبح n أكبر، ومن الواضح أن 4 ستبقى 4 لأن n تنمو بصورة أكبر؛ أما 6n فتنمو بصورةٍ أكبر وأكبر، لذلك تميل إلى كونها أهم بالنسبة للمشكلات الأكبر، وبالتالي، أول شيء سنفعله هو حذف 4 والاحتفاظ بالدالة على صورة f( n ) = 6n. يُعَدّ ما سبق منطقيًا، وذلك لأنّ الرقم 4 هو "ثابت التهيئة initialization constant" ببساطة، وقد تتطلب لغات البرمجة المختلفة وقتًا مختلفًا لعملية الإعداد، فمثلًا، تحتاج لغة جافا إلى بعض الوقت لتهيئة آلتها الافتراضية virtual machine، وبما أننا نتجاهل الاختلافات في لغات البرمجة، فمن المنطقي تجاهل هذه القيمة فقط. الشيء الثاني الذي سنتجاهله هو معامل الضرب الثابت أمام n، وبالتالي ستصبح الدالة f( n ) = n، مما يجعل الأمور أكثر بساطةً. يُعَدّ إهمال معامل الضرب أمرًا منطقيًا إذا فكرنا في كيفية تصريف لغات البرمجة المختلفة، فقد تُصرَّف عبارة "البحث في المصفوفة" في إحدى لغات البرمجة إلى تعليمات مختلفة عن لغات برمجةٍ مختلفة، كما لا يتضمّن الإجراء A[ i ] التحقق من عدم تجاوز المتغير i لحجم المصفوفة المُصرَّح عنها في لغة سي C على سبيل المثال، ولكنه يتضمّن ذلك في لغة باسكال Pascal؛ إذًا فالشيفرة التالية المكتوبة بلغة باسكال: M := A[ i ] تكافئ الشيفرة التالية المكتوبة بلغة سي: if ( i >= 0 && i < n ) { M = A[ i ]; } لذلك نتوقّع أن لغات البرمجة المختلفة ستنتج عوامِلًا مختلفةً عندما نعُد تعليماتها. تستخدِم لغة باسكال مصرِّفًا غبيًا يغفَل عن التحسينات الممكنة في هذا المثال، كما تتطلب ثلاث تعليمات لكل وصول إلى مصفوفة، في حين تتطلب لغة سي تعليمةً واحدةً. يُطبَّق إهمال هذا العامل على جميع الاختلافات بين لغات البرمجة والمصرِّفات أيضًا، وبالتالي، تُحلَّل فكرة الخوارزمية فقط. يُسمَّى المرشِّح المتمثِّل بعمليتَي "إهمال جميع العوامل"، و"الإبقاء على القسم الذي يكبر أكثر" كما هو موصوف أعلاه بالسلوك المقارب asymptotic behavior، ولذلك نمثِّل السلوك المقارب للدالة f( n ) = 2n + 8 من خلال الدالة f( n ) = n. نهتم رياضيًا بنهاية الدالة f لأن n يميل إلى اللانهاية؛ ولكن إن لم تفهم ما تعنيه هذه العبارة، فلا تقلق لأنّ هذا كل ما تحتاج إلى معرفته، كما لن نستطيع إهمال الثوابت في النهاية في إطار رياضي صارم، ولكننا نفعل ذلك لأغراض علوم الحاسوب وللأسباب الموضَّحة أعلاه. سنحل بعض الأمثلة لفهم الفكرة أكثر، فمثلًا، لنجد السلوك المقارب لدوال المثال التالي بإهمال العوامِل الثابتة، والحفاظ على الأقسام التي تكبر بسرعة: تعطي الدالة f( n ) = 5n + 12 الدالة f( n ) = n باستخدام الاستنتاج نفسه بالضبط كما هو مذكور أعلاه. تعطي الدالة f (n) = 109 الدالة f( n ) = 1، حيث سنهمل معامل الضرب 109 * 1، لكن لا يزال يتعين علينا وضع 1 هنا للإشارة إلى أنّ لهذه الدالة قيمة غير صفرية. تعطي الدالة f( n ) =n2 + 3n + 112 الدالة f( n ) = n2، حيث تكبرn2 أكثر من 3n بالنسبة لقيمة n كبيرة بدرجة كافية، لذلك نحتفظ بها. تعطي الدالة f( n ) = n3 + 1999n + 1337 الدالة f( n ) = n3، فعلى الرغم من أنّ العامل الموجود أمام n كبير جدًا، لكن لا يزال بإمكاننا العثور على قيمة n كبيرة بما يكفي، بحيث يكون n3 أكبر من 1999n، وبما أننا مهتمون بسلوك قيم n الكبيرة جدًا، فسنبقي على n3 فقط، أي تصبح الدالة n3 المرسومة باللون الأزرق في الشكل التالي أكبر من الدالة 1999n المرسومة باللون الأحمر بعد القيمة n = 45، كما تبقى هي الأكبر بعد هذه النقطة إلى الأبد. تعطي الدالة f( n ) = n +√n الدالة f (n) = n، وذلك لأنّ n تنمو أسرع من ‎√n كلما زادتn ويمكنك تجربة الأمثلة الآتية بنفسك. تمرين 1 f( n ) = n6 + 3n f( n ) = 2n + 12 f( n ) = 3n + 2n f( n ) = nn + n (اكتب نتائجك، وسترى الحل أدناه). إذا واجهتك مشكلة مع أحد العناصر المذكورة أعلاه، فجرِّب بعض قيم n الكبيرة لمعرفة القسم الأكبر، وهذا بسيط جدًا، أليس كذلك؟ التعقيد Complexity بما أنه يمكننا إهمال كل هذه الثوابت "الشكلية"، فمن السهل جدًا معرفة السلوك المقارب لدالة عدّ تعليمات البرنامج، حيث يملك البرنامج الذي لا يحتوي على حلقات، الدالة f( n ) = 1، لأن عدد التعليمات التي يحتاجها هو مجرد عددٍ ثابت -إلا في حالة استخدامه العودية كما سنرى لاحقًا-. يملك البرنامج الذي يحتوي حلقةً واحدةً تمتد من 1 إلى n، الدالة f( n ) = n، حيث سينفِّذ عددًا ثابتًا من التعليمات قبل الحلقة، وعددًا ثابتًا من التعليمات بعد الحلقة، وعددًا ثابتًا من التعليمات داخل الحلقة التي تُشغَّل جميعًا n مرة. يجب أن يكون هذا أكثر سهولةً وأقل مللًا من عدّ التعليمات الفردية، لذلك لنلقِ نظرةً على بعض الأمثلة لفهم ذلك أكثر. يتحقق البرنامج التالي المكتوب بلغة PHP من وجود قيمة معيَّنة داخل مصفوفة A لها الحجم n: <?php $exists = false; for ( $i = 0; $i < n; ++$i ) { if ( $A[ $i ] == $value ) { $exists = true; break; } } ?> تسمَّى هذه الطريقة للبحث عن قيمة داخل مصفوفة البحث الخطي linear search، وهذا اسم معقول لاحتواء هذا البرنامج على الدالة f( n ) = n، كما سنحدد بالضبط ما تعنيه كلمة "خطي" في القسم التالي. لاحظ وجود عبارة "break" هنا، والتي قد تؤدّي إلى إنهاء البرنامج في وقت قريب، وربما بعد تكرارٍ واحد؛ لكن تذكّر اهتمامنا بالسيناريو الأسوأ، وهو بالنسبة لهذا البرنامج عدم احتواء المصفوفة A على القيمة التي نبحث عنها، لذلك لا يزال لدينا الدالة f( n ) = n. تمرين 2 حلّل عدد التعليمات التي يحتاجها برنامج PHP أعلاه بالنسبة إلى n في الحالة الأسوأ للعثور على الدالة ( f( n، وذلك على غرار الطريقة التي حلّلنا بها البرنامج الأول المكتوب بلغة جافا سكريبت، ثم تحقق من أنه لدينا f( n ) = n بصورةٍ مقاربة. لنلقِ نظرةً على البرنامج المكتوب بلغة بايثون Python، والذي يجمع عنصرين من مصفوفة معًا لينتج مجموع يُخزَّن في متغير آخر: v = a[ 0 ] + a[ 1 ] لدينا هنا عددٌ ثابت من التعليمات، لذلك f (n) = 1. يتحقق البرنامج التالي المكتوب بلغة C++‎ من احتواء متّجه -مصفوفة مختارة أو جزء من مصفوفة- يُسمَّى A، وذو حجم n على قيمتين متماثلتين في أي مكان ضمنه: bool duplicate = false; for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { if ( i != j && A[ i ] == A[ j ] ) { duplicate = true; break; } } if ( duplicate ) { break; } } بما أنه توجد هنا حلقتان متداخلتان داخل بعضهما البعض، فسيكون لدينا سلوكًا مقاربًا موصوفًا بالدالة f( n ) = n2. إذا استدعى برنامج دالةً داخل حلقة وعرفنا عدد التعليمات التي تجريها الدالة المستدعاة، فمن السهل تحديد عدد تعليمات البرنامج بأكمله. لنلقِ نظرةً على المثال التالي المكتوب بلغة ? int i; for ( i = 0; i < n; ++i ) { f( n ); } إذا علمنا أن f( n ) هي دالة تنفِّذ n تعليمة بالضبط، فيمكننا حينئذٍ معرفة أن عدد تعليمات البرنامج بأكمله هو n2 بصورةٍ مقاربة، حيث تُستدعى الدالة n مرة تمامًا. ننتقل الآن إلى الصيغة التخيُّلية التي يستخدمها علماء الحاسوب للسلوك المقارب، حيث سنقول أن برنامجنا هو Θ ( f( n )) عندما نحدِّد الدالة f بصورة مقاربة، فمثلًا، البرامج المذكورة أعلاه هي Θ (1) وΘ( n2 ) وΘ( n2 ) على التوالي، حيث تُقرَأ Θ( n ) "ثيتا بالنسبة إلى n". نقول أحيانًا أنّ f( n ) -وهي الدالة الأصلية التي تحسب عدد التعليمات بما في ذلك الثوابت- هي شيء ما Θ، حيث نقول مثلًا أنّ f( n ) = 2n هي دالة Θ( n )، كما يمكننا كتابة 2n ∈ Θ (n)‎ أيضًا، والتي تُنطَق "2n هي ثيتا بالنسبة إلى n". لا ترتبك بشأن هذا الصيغة، فكل ما تنص عليه هو أنه إذا حسبنا عدد التعليمات التي يحتاجها البرنامج وهي 2n، فسيُوصَف السلوك المقارب للخوارزمية بـ n والذي نتج بإهمال الثوابت. فيما يلي بعض العبارات الرياضية الصحيحة باستخدام هذا الصيغة: n6 + 3n ∈ Θ( n6 ) 2n + 12 ∈ Θ( 2n ) 3n + 2n ∈ Θ( 3n ) nn + n ∈ Θ( nn ) بالمناسبة، إذا حللت التمرين 1 السابق، فهذه هي بالضبط الإجابات التي يجب أن تصل إليها. نسمّي ما نضعه ( هنا )Θ التعقيد الزمني time complexity، أو تعقيد complexity الخوارزمية، لذلك فللخوارزمية التي تحتوي على الصيغة Θ( n ) تعقيدٌ هو n. لدينا أيضًا أسماءً خاصةً للصيغ التالية: Θ( 1 )، وΘ( n )، وΘ( n2 ) وΘ( log( n ) )، وذلك لكثرة ظهورها، حيث نقول أنّ خوارزمية Θ( 1 ) هي خوارزمية ذات وقت ثابت constant-time algorithm، والخوارزمية Θ( n ) خطية linear، وΘ( n2 ) تربيعية quadratic؛ أما الخوارمية Θ( log( n ) ) فهي لوغاريتمية logarithmic. لا تقلق إن لم تعرف ما هي اللوغاريتمات حتى الآن، سنشرح ذلك لاحقًا. صيغة O الكبير Big-O notation قد تكون معرفة سلوك الخوارزمية بهذه الطريقة كما فعلنا أعلاه أمرًا صعبًا، خاصةً بالنسبة للأمثلة الأعقد، ولكن يمكننا القول بأن سلوك خوارزميتنا لن يتجاوز أبدًا حدًا معينًا، وبالتالي لن نضطر إلى تحديد السرعة التي تعمل بها الخوارزمية، وذلك حتى عند تجاهل الثوابت بالطريقة التي طبّقناها سابقًا، فكل ما علينا فعله هو إيجاد حدٍ معين، حيث سنشرح ذلك بمثال. مشكلة الفرز (sorting problem) هي إحدى المشكلات الشهيرة التي يستخدمها علماء الحاسوب لتدريس الخوارزميات، حيث تُعطَى مصفوفة A بحجم n في مشكلة الفرز، ويُطلَب منا كتابة برنامج لفرز أو ترتيب هذه المصفوفة، وتُعَدّ هذه المشكلة مشكلةً مهمةً كونها مشكلةً واقعيةً في الأنظمة الحقيقية، إذ يحتاج مستكشف الملفات إلى فرز الملفات التي يعرضها حسب الاسم حتى يتمكن المستخدِم من التنقل بينها بسهولة، أو قد تحتاج لعبة فيديو إلى فرز الكائنات ثلاثية الأبعاد المعروضة في العالم بناءً على بعدها عن عين اللاعب داخل العالم الافتراضي من أجل تحديد ما هو مرئي وما هو غير مرئي، وهو ما يسمى مشكلة الرؤية Visibility Problem، فالكائنات التي تكون أقرب للاعب هي المرئية، في حين أنّ الكائنات البعيدة قد تخفيها الكائنات الموجودة أمامها، ويوضّح الشكل الآتي هذه المشكلة، إذ لن يرى اللاعب الموجود في النقطة الصفراء المناطق المظلَّلة، كما يُعَدّ تقسيم العالم إلى أجزاء صغيرة وفرزها حسب المسافة التي تفصلها عن اللاعب إحدى طرق حل مشكلة الرؤية. يُعَدّ الفرز أيضًا مهمًا بسبب وجود العديد من الخوارزميات لحله، كما يكون بعضها أسوأ من البعض الآخر، وهي أيضًا مشكلة سهلة التحديد والشرح، لذلك لنكتب جزءًا من شيفرة تفرز مصفوفة. الطريقة التالية هي طريقة غير فعالة لفرز مصفوفة في لغة روبي Ruby، حيث تدعم لغة روبي فرز المصفوفات باستخدام دوال مبنيّة مسبقًا يجب استخدامها بدلًا من ذلك، وهي بالتأكيد أسرع مما سنراه هنا، ولكن ما سنستخدمه هنا هي شيفرة بغرض التوضيح فقط: b = [] n.times do m = a[ 0 ] mi = 0 a.each_with_index do |element, i| if element < m m = element mi = i end end a.delete_at( mi ) b << m end تسمى هذه الطريقة الفرز الانتقائي Selection sort، حيث تجد هذه الخوارزمية الحد الأدنى من المصفوفة -يُرمَز إلى المصفوفة بالمتغير a في الشيفرة السابقة، بينما يُرمَز إلى الحد الأدنى بالمتغير m، والمتغير mi هو دليله في المصفوفة-، وتضعه في نهاية مصفوفة جديدة -أي المصفوفة b في حالتنا-، ثم تزيله من المصفوفة الأصلية، وبعدها تجد الحد الأدنى بين القيم المتبقية للمصفوفة الأصلية، وتلحِقه بالمصفوفة الجديدة التي تحتوي على عنصرين الآن، ثم تزيله من المصفوفة الأصلية؛ وتستمر هذه العملية إلى حين إزالة جميع العناصر من المصفوفة الأصلية وإدخالها في المصفوفة الجديدة، مما يعني فرز المصفوفة. نلاحظ وجود حلقتين متداخلتين في الشيفرة السابقة، حيث تعمل الحلقة الخارجية n مرة، وتعمل الحلقة الداخلية مرةً واحدةً لكل عنصر من عناصر المصفوفة a. تحتوي المصفوفة a في البداية على n عنصر، ونزيل عنصر مصفوفة واحد في كل تكرار، لذلك تتكرر الحلقة الداخلية n مرة خلال التكرار الأول للحلقة الخارجية، ثم n - 1 مرة، وبعدها n - 2 مرة، وهكذا دواليك حتى التكرار الأخير للحلقة الخارجية التي تعمل خلالها مرةً واحدةً فقط. من الصعب قليلًا تقييم تعقيد هذا البرنامج، حيث يجب معرفة المجموع 1 + 2 + … +(n+(n-1، ولكن يمكننا بالتأكيد إيجاد "الحد الأعلى" لهذا المجموع، وهذا يعني أنه يمكننا تغيير برنامجنا - أي يمكنك فعل ذلك في عقلك، وليس في الشيفرة الفعلية- لجعله أسوأ مما هو عليه، ومن ثم إيجاد تعقيد هذا البرنامج الجديد، فإذا تمكّنا من العثور على تعقيد البرنامج الأسوأ الذي أنشأناه، فسنعلم أنّ برنامجنا الأصلي أسوأ أو ربما أفضل. بالتالي إذا أوجدنا تعقيدًا جيدًا لبرنامجنا المعدَّل الذي هو أسوأ من برنامجنا الأصلي، فيمكننا معرفة أنه سيكون لبرنامجنا الأصلي تعقيدًا جيدًا جدًا أيضًا، أي إما جيدًا بمستوى برنامجنا المعدَّل أو أفضل منه. لنفكّر في طريقة تعديل هذا البرنامج لتسهيل معرفة تعقيده، ولكن ضع في بالك أنه لا يمكننا سوى جعل الأمر أسوأ هكذا، إذ سيأخذ البرنامج مزيدًا من التعليمات، وبالتالي سيكون تقديرنا مفيدًا لبرنامجنا الأصلي. يمكن تغيير الحلقة الداخلية للبرنامج بجعلها تتكرر n مرة دائمًا بدلًا من تكرارها عددًا متغيرًا من المرات، كما ستكون بعض هذه التكرارات عديمة الفائدة، لكنها ستساعدنا في تحليل تعقيد الخوارزمية الناتجة؛ وإذا أجرينا هذا التغيير البسيط، فمن الواضح أن الخوارزمية الجديدة التي أنشأناها هي Θ( n2 ) وذلك لوجود حلقتين متداخلتين بحيث يتكرر كل منهما n مرة بالضبط، وبالتالي، يمكننا القول أنّ الخوارزمية الأصلية هي O( n2 ). تُنطَق O( n2 ) "أوه كبيرة لمربع n، أي big oh of n squared"، وهذا يقودنا للقول بأن برنامجنا ليس أسوأ من n2 بصورةٍ مقاربة، فقد يكون أفضل من ذلك أو مثله. إذا كان برنامجنا هو بالفعل Θ( n2 ) فلا يزال بإمكاننا القول أنه O( n2 ) أي تخيل تغيير البرنامج الأصلي بطريقة لا تغيره كثيرًا، لكنها لا تزال تجعله أسوأ قليلًا مثل إضافة تعليمات لا معنى لها في بداية البرنامج، بحيث سيؤدي فعل ذلك إلى تغيير دالة عدّ التعليمات بواسطة ثابت بسيط، والذي سنتجاهله عندما يتعلق الأمر بالسلوك المقارب، وبالتالي فالبرنامج Θ( n2 ) هو O( n2 ) أيضًا. قد لايكون البرنامج O( n2 ) هو Θ( n2 ) أيضًا، فأيّ برنامج Θ( n ) مثلًا هو O( n2 ) وO( n ) كذلك، وإذا تخيلنا أن برنامج Θ( n ) هو عبارة عن حلقة for بسيطة تتكرر n مرة، فيمكن جعلها أسوأ بتغليفها ضمن حلقة for أخرى تتكرر n مرة أيضًا، وبالتالي ينتج برنامج له دالة f( n ) = n2، كما يمكن تعميم ذلك بالقول أنّ أي برنامج Θ( a ) هو O( b ) عندما يكون b أسوأ من a. لا يحتاج التغيير الذي أجريناه على البرنامج إلى إعطائنا برنامجًا له معنى أو مكافئًا لبرنامجنا الأصلي، حيث يحتاج فقط إلى تنفيذ تعليمات أكثر من التعليمات الأصلية بالنسبة إلى قيمة n معينة، أي نستخدم هذا التغيير من أجل حساب عدد التعليمات فقط وليس لحل مشكلتنا. لذا يمكن القول بأن برنامجنا هو O( n2 ) بطريقةٍ آمنة، وذلك لأننا حلّلنا خوارزميتنا، ووجدناها ليست أسوأ من n2، ولكنها في الواقع قد تساوي n2، وبالتالي يمكننا تقدير سرعة تشغيل برنامجنا. لنستعرض بعض الأمثلة لتساعدك على التعرف على هذه الصيغة الجديدة. تمرين 3 أيٌّ مما يلي صحيح؟ خوارزمية Θ( n ) هي O( n ) خوارزمية Θ( n ) هي O( n2 ) خوارزمية Θ( n2 ) هي O( n3 ) خوارزمية Θ( n ) هي O( 1 ) خوارزمية O( 1 ) هي Θ( 1 ) خوارزمية O( n ) هي Θ( 1 ) الحل هذا صحيح لأنّ برنامجنا الأصلي كان Θ( n )، ويمكننا تحقيق O( n ) دون تغيير برنامجنا على الإطلاق. هذا صحيح لأنّ n2 أسوأ من n. هذا صحيح لأنّ n3 أسوأ من n2. هذا خطأ لأنّ 1 ليس أسوأ من n، فإذا أخذ البرنامج n تعليمةً بصورةٍ مقاربة -أي عددًا خطيًا من التعليمات-، فلا يمكننا جعله أسوأ ولا يمكن جعله يأخذ تعليمةً واحدةً بصورةٍ مقاربة -أي عددًا ثابتًا من التعليمات-. هذا صحيح لأنّ التعقيدان متماثلان. قد يكون هذا صحيحًا أو غير صحيح وذلك اعتمادًا على الخوارزمية، لكنه خاطئ في الحالة العامة، فإذا كانت الخوارزمية Θ( 1 )، فمن المؤكد أنها O( n )؛ أما إذا كانت O( n ) فقد لا تكون Θ( 1 )، فمثلًا، خوارزمية Θ( n ) هي O ( n ) وليست Θ( 1 ). تمرين 4 استخدم متتالية الجمع الحسابية arithmetic progression sum لإثبات أنّ البرنامج أعلاه ليس O( n2 ) فقط، وإنما Θ( n2 ) أيضًا، ويمكنك البحث عن معنى المتتالية الحسابية في ويكيبيديا في حالة عدم معرفتك بها. يعطي التعقيد O-complexity لخوارزمية ما حدًا أعلى لتعقيد الخوارزمية الفعلي - أي الوقت الأكبر الذي قد تستغرقه الخوارزمية-، بينما تعطي الصيغة Θ تعقيد الخوارزمية الفعلي، حيث نقول أحيانًا أن الصيغة Θ تعطينا حدًا تامًا، وإذا علمت أننا وجدنا حد تعقيدٍ غير تام، فيمكنك استخدام الحرف الصغير o للإشارة إلى ذلك، فمثلًا، إذا كان للخوارزمية التعقيد Θ( n )، فسيكون تعقيدها التام n، وبالتالي سيكون لهذه الخوارزمية O( n ) و O( n2 ) معًا. بما أن الخوارزمية هي Θ( n )، فسيكون حد O( n ) هو الحد التام؛ أما حد O( n2 ) فليس تامًا، ولذلك يمكننا كتابة أن الخوارزمية هي o( n2 ) والتي تُنطق "o الصغير بالنسبة إلى مربع n"، وذلك لتوضيح أن الحد ليس تامًا. كما يُفضَّل إيجاد حدود تامة للخوارزميات لأنها تعطينا مزيدًا من المعلومات حول سلوكها، ولكنه ليس أمرًا سهلًا دائمًا. تمرين 5 حدّد أيًا من الحدود التالية هي حدودًا تامةً وأيها لا، ثم تحقق من صحتها أو خطئها، ويجب عليك استخدام الصيغة o لتحديد الحدود غير التامة: خوارزمية Θ (n) التي لها الحد الأعلى O (n). خوارزمية Θ (n2) التي لها الحد الأعلى O (n3). خوارزمية Θ(1) التي لها الحد الأعلى O (n). خوارزمية Θ (n) التي لها الحد الأعلى O (1). خوارزمية Θ (n) التي لها الحد الأعلى O (2n). الحل الحد تام لأنّ تعقيد Θ وتعقيد O متماثلان في هذه الحالة. الحد غير تام لأنّ تعقيد O أكبر من تعقيد Θ، وقد يكون حد O( n2 ) تامًا، لذلك يمكننا كتابة أن الخوارزمية هي o( n3). الحد غير تام، لأنّ تعقيد O أكبر من تعقيد Θ، وقد يكون حد O( 1 ) تامًا، لذلك يمكننا الإشارة بأنّ الحد O( n ) ليس تامًا من خلال كتابته بالشكل o( n ). الحد خاطئ، فقد اُرتكِب خطأ في حسابه، فلا يمكن أن يكون لخوارزمية Θ( n ) حد أعلى من O( 1 )‎، وذلك لأنّ التعقيد n أكبر من التعقيد 1 -تذكر أنّ O تعطي حدًا أعلى. الحد تام، فقد يبدو مثل حد غير تام، لكن هذا ليس صحيحًا في الواقع، -تذكر أنّ سلوك 2n وn المقارب هو نفسه، وأنّ الصيغتَين O وΘ تهتمان بالسلوك المقارب؛ إذًا لدينا O( 2n ) = O( n )، وبالتالي، فهذا الحد تام لأن التعقيد هو نفس Θ. قد تجد نفسك تائهًا قليلًا في هذه الصيغة الجديدة، ولكن سنقدم صيغتين آخرين بسيطتين بالنسبة للصيغ Θ، وO، وo قبل انتقالنا إلى بعض الأمثلة، ويُستحسَن أن تعرف هاتين الصيغتَين الآن، حيث لن نستخدمهما كثيرًا في هذا المقال لاحقًا. عدّلنا برنامجنا في المثال أعلاه ليصبح أسوأ -أي أخذ المزيد من التعليمات، وبالتالي المزيد من الوقت- وأنشأنا الصيغة O، حيث تُعَدّ الصيغة O ذا مغزىً لأنها تخبرنا بأن برنامجنا لن يكون أبدًا أبطأ من حدٍ معين، ولهذا فهي توفر معلومات قيّمةً تمكننا من القول بأن برنامجنا جيد بما فيه الكفاية، وإذا فعلنا العكس وعدّلنا برنامجنا ليصبح أفضل، ثم أوجدنا تعقيد البرنامج الناتج، فنستخدم الصيغة Ω التي تعطينا تعقيدًا يخبرنا بأن برنامجنا لن يكون أفضل، وهذا مفيد إذا أردنا إثبات أن البرنامج يعمل ببطء أو أن الخوارزمية سيئة، وقد يكون هذا مفيدًا للقول بأن الخوارزمية بطيئة جدًا عند استخدامها في حالة معينة، فمثلًا، خوارزمية Ω( n3 ) ليست أفضل من n3. قد تكون الصيغة Θ( n3 ) سيئًة مثل Θ (n4) أو أسوأ منها، لكننا نعلم أنها سيئة إلى حد ما على الأقل. إذًا تعطينا الصيغة Ω حدًا أدنى لتعقيد خوارزمية، كما يمكننا كتابة الصيغة ω على غرار الصيغة ο عندما يكون الحد ليس تامًا، فمثلًا، خوارزمية Θ ( n3 ) هي ο( n4 ) وω( n2 ) وتُقرَأ Ω( n ) "أوميغا كبيرة بالنسبة إلى n"، بينما تُقرَأ ω( n ) "أوميغا صغيرة بالنسبة إلى n". تمرين 6 اكتب حد O تام وآخر غير تام، وحد Ω تام وآخر غير تام من اختيارك للتعقيدات التالية، ولكن بشرط وجودهما طبعًا: Θ( 1 ) Θ(√n) Θ( n ) Θ( n2 ) Θ( n3 ) الحل هذا هو تطبيق مباشر للتعاريف أعلاه: الحدود التامة هي O( 1 ) وΩ( 1 )، كما يكون حد O غير التام هو O( n ) -تذكّر أن O تعطينا حدًا أعلى-، وبما أن n أكبر من 1، فسيمثِّل حدًا غير تام يمكننا كتابته بالشكل o( n ) أيضًا، كما لا يمكننا إيجاد حد غير تام للصيغة Ω لعدم تمكننا من الحصول على أقل من 1 لهذه الدوال، إذًا يجب تعاملنا مع الحد التام فقط. يجب أن تكون للحدود التامة تعقيد Θ نفسه، لذا فهي O(√n) وΩ(√n) على التوالي؛ أما الحدود غير التامة فقد تكون O( n )، حيث تُعَدّ n أكبر من ‎√n وبالتالي فهي حد أعلى لها. وبما أننا نعلم أن هذا حدًا أعلى غير تام، فيمكننا أيضًا كتابته بالصورة o( n )؛ أما الحد الأدنى غير التام، فيمكننا ببساطة استخدام Ω( 1 )، وبما أننا نعلم أن هذا الحد ليس تامًا، فيمكننا كتابته بالصورة ω( 1. 3 ). الحدود التامة هي O( n ) وΩ( n ). قد يكون الحدان الغير تامين هما ω( 1 ) وo( n3 ) وهي في الواقع حدودٌ سيئة للغاية، لأنها بعيدة كل البعد عن التعقيدات الأصلية، إلا أنها لا تزال صالحة باستخدام التعاريف. الحدود التامة هي O( n2 ) وΩ( n2 ) ويمكننا استخدام ω( 1 ) وo( n3 ) بالنسبة للحدود غير التامة كما في المثال السابق. الحدود التامة هي O( n3 ) وΩ( n3 ) على التوالي، وقد يكون الحدان غير التامَين هما ω(‎n2 √n)‎ وω(n3 √n)، وعلى الرغم من أنّ هذه الحدود ليست تامة، إلا أنها أفضل من تلك الموجودة في جواب رقم 3 و4 من هذا التمرين أعلاه. قد تعطي الصيغتان O وΩ أيضًا حدودًا تامة، وسبب استخدامنا لهما بدلًا من الصيغة Θ هو أننا قد لا نكون قادرين على معرفة ما إذا كان الحد الذي أوجدناه تامًا أم لا، أو ربما لا نرغب في متابعة العملية باستخدام الصيغة Θ التي تحتاج تدقيقًا عميقًا. إذا لم تتذكر تمامًا جميع الرموز المختلفة واستخداماتها، فلا تقلق بشأنها كثيرًا الآن، حيث يمكنك دائمًا العودة والبحث عنها، وأهم الرموز هي O وΘ. لاحظ أيضًا أنه على الرغم من كون الصيغة Ω تعطينا سلوكًا ذو حدٍ منخفض للدالة -أي تحسّن برنامجنا وأصبح ينفّذ تعليماتٍ أقل-، إلا أننا ما زلنا نشير إليها بتحليل "الحالة الأسوأ"، لأننا نزوّد برنامجنا بأسوأ دخلٍ ممكن من n ونحلّل سلوكه في ظل هذا الافتراض. يوضح الجدول التالي الرموز التي قدمناها للتو وتوافقاتها مع الرموز الرياضية المعتادة للمقارنات التي نستخدمها مع الأعداد، كما يعود السبب في عدم استخدامنا للرموز المعتادة هنا واستخدام الأحرف الإغريقية بدلًا منها، إلى الإشارة إلى إجراء مقارنة سلوك مقارب وليس مقارنة بسيطة: table { width: 100%; } thead { vertical-align: middle; text-align: center; } td, th { border: 1px solid #dddddd; text-align: right; padding: 8px; text-align: inherit; } tr:nth-child(even) { background-color: #dddddd; } عامل المقارنة المقارب Asymptotic comparison operator عامل المقارنة العددي Numeric comparison operator الخوارزمية هي ( شيء ما )o يوجد عدد < هذا الشيء الخوارزمية هي ( شيء ما )O يوجد عدد ≤ هذا الشيء الخوارزمية هي ( شيء ما )Θ يوجد عدد = هذا الشيء الخوارزمية هي ( شيء ما )Ω يوجد عدد ≥ هذا الشيء الخوارزمية هي ( شيء ما )ω يوجد عدد > هذا الشيء اللوغاريتمات Logarithms هل تعرف ما هي اللوغاريتمات؟ إن كانت إجابتك نعم، فلا تتردد في تخطي هذا القسم، فهذا القسم هو مقدمة لمن ليس على دراية باللوغاريتمات، أو لمن لم يستخدمها كثيرًا مؤخرًا، فهو موجَّهٌ للطلاب الأصغر سنًا، والذين لم يروا اللوغاريتمات في المدرسة بعد. تُعَدّ اللوغاريتمات مهمة بسبب ظهورها بكثرة عند تحليل التعقيد، ويُعَدّ اللوغاريتم عمليةً تُطبَّق على رقم ما ليصبح أصغر، حيث تشبه هذه العملية الجذر التربيعي لرقم إلى حد كبير؛ لذلك إذا كان هناك شيء واحد تريد تذكره حول اللوغاريتمات، فهو أنها تأخذ رقمًا وتجعله أصغر بكثير من الأصل. يوضِّح الشكل الآتي مقارنةً بين الدوال n، و‎√n، وlog( n )، إذ تنمو الدالة n -أو كما تُسمَّى الدالة الخطية linear function- المرسومة باللون الأخضر في أعلى الشكل، أسرع بكثير من دالة الجذر التربيعي المرسومة باللون الأحمر في المنتصف، والتي بدورها تنمو أسرع بكثير من الدالة log( n ) المرسومة باللون الأزرق في الجزء السفلي من هذا الرسم البياني، ويكون الفرق واضحًا تمامًا حتى بالنسبة إلى n صغيرة مثل n = 100. تُعَدّ اللوغاريتمات عمليةً عكسيةً لرفع شيءٍ ما إلى أس مثل الجذور التربيعية التي هي عملية عكسية لتربيع شيءٍ ما، وسنشرح ذلك بمثال. ضع في بالك المعادلة التالية: 2x = 1024 نريد حل هذه المعادلة لإيجاد قيمة x، لذلك لنسأل أنفسنا: ما هو الرقم الذي يجب رفع الأساس 2 إليه حتى نحصل على 1024؟ هذا الرقم هو 10. بالفعل لدينا ‎210 = 1024، وهو أمر سهل التحقق منه؛ كما تساعدنا اللوغاريتمات من خلال الإشارة إلى هذه المشكلة باستخدام صيغة جديدة، فالرقم 10 في هذه الحالة هو لوغاريتم 1024 ونكتبه بالصورة ( log( 1024 ونقرأه "لوغاريتم 1024". بما أننا نستخدم العدد 2 أساسًا، فتسمى هذه اللوغاريتمات لوغاريتمات الأساس 2، كما توجد لوغاريتمات لها أساسات أخرى، ولكننا سنستخدم فقط لوغاريتمات الأساس 2 في هذا المقال، وإذا كنت طالبًا منافسًا في مسابقات دولية ولا تعرف شيئًا عن اللوغاريتمات، فنوصيك بشِدة بالتدرّب على اللوغاريتمات بعد الانتهاء من هذا المقال. تُعَدّ لوغاريتمات الأساس 2 أكثر أنواع اللوغاريتمات شيوعًا في علوم الحاسوب لأنه غالبًا ما يكون لدينا كيانان مختلفان فقط هما: 0 و1، كما نميل أيضًا إلى تقسيم مشكلة كبيرة واحدة إلى نصفين، لذلك ما عليك سوى معرفة لوغاريتمات الأساس 2 لمتابعة هذا المقال. تمرين 7 حُلّ المعادلات أدناه، وأوجد اللوغاريتم في كل حالة باستخدام اللوغاريتمات ذات الأساس 2 فقط: 2x = 64 ‎(22)x= 64 4x = 4 2x = 1 2x + 2x = 32 ‎(2x) * (2x) = 64 الحل لا يتضمن الحل أكثر من تطبيق الأفكار المُعرَّفة أعلاه: يمكننا باستخدام طريقة التجربة والخطأ إيجاد أن x = 6، وبالتالي، log( 64 ) = 6. يمكن كتابة ‎(22)x بالصورة 22x من خلال تطبيق خصائص الأس، إذًا لدينا 2x = 6 لأن log( 64 ) = 6 من النتيجة السابقة، وبالتالي، x = 3. يمكننا كتابة 4 بالشكل 22 باستخدام معرفتنا من المعادلة السابقة، وبهذا تصبح المعادلة ‎(22)x= 4 وهي 22x = 4 نفسها، ونلاحظ أن log( 4 ) = 2 لأن ‎22 = 4، وبالتالي، لدينا أن 2x = 2، وعليه فـ x = 1؛ كما يمكن ملاحظة ذلك بسهولة من المعادلة الأصلية، حيث أن ناتج الرفع للأس 1 هو الأساس نفسه. تذكر أن ناتج الرفع للأس 0 هو 1، لذلك لدينا log( 1 ) = 0، بما أنّ ‎20= 1، وبالتالي، x = 0. لا يمكننا أخذ اللوغاريتم مباشرةً بسبب وجود المجموع، ولكن يمكن ملاحظة أنّ 2x+ 2x هي ‎2 * (2x) نفسها، حيث ضربنا هنا بالعدد 2 أي لهما الأساس نفسه، وبالتالي، ينتج 2x + 1، والآن كل ما علينا فعله هو حل المعادلة 2x + 1= 32، حيث نجد أنّ log( 32 ) = 5، وهكذا x + 1 = 5، وبالتالي، x = 4. نضرب هنا قوتين للعدد 2 معًا، ولذلك يمكننا ضمهما من خلال ملاحظة أن (2x) * (2x) هي 22x نفسها، وبالتالي كل ما علينا فعله هو حل المعادلة 22x= 64 التي حللناها بالفعل أعلاه، حيث x = 3. التعقيد العودي Recursive complexity لنلقِ نظرةً على دالة عودية recursive function، فالدالة العودية هي دالة تستدعي نفسها. هل يمكننا تحليل تعقيدها؟ توجِد الدالة الآتية والمكتوبة بلغة بايثون، حيث تُقيِّم مضروب factorial عددٍ معين، إذ يمكن إيجاد مضروب عدد صحيح موجب بضربه بجميع الأعداد الصحيحة السابقة معًا، فمثلًا، مضروب العدد 5 هو 5 * 4 * 3 * 2 * 1؛ كما نعبِّر عن ذلك بالصورة "!5" ونقرؤها "مضروب العدد خمسة five factorial"، ويفضِّل بعض الناس نُطقها بصوت عالٍ مثل "خمسة !!!". def factorial( n ): if n == 1: return 1 return n * factorial( n - 1 ) لنحلّل تعقيد هذه الدالة، فعلى الرغم من عدم احتواء هذه الدالة على أية حلقات، إلا أنّ تعقيدها ليس ثابتًا constant، حيث يجب علينا متابعة عد التعليمات مرةً أخرى لمعرفة تعقيدها، فإذا مرّرنا المتغير n إلى هذه الدالة، فستنفّذ n مرة؛ وإذا لم تكن متأكدًا من ذلك، فشغّل هذه الدالة "يدويًا" الآن من أجل n = 5 للتحقق منها. ستنفَّذ هذه الدالة مثلًا 5 مرات من أجل n = 5، بحيث ستستمر في إنقاص قيمة n بمقدار 1 في كل استدعاء، وبالتالي، يكون تعقيد هذه الدالة هو ( Θ( n. إذا لم تكن متأكدًا من هذه الحقيقة، فتذكر أنه يمكنك دائمًا العثور على التعقيد الدقيق عن طريق حساب عدد التعليمات، وإذا رغبت في ذلك، فيمكنك محاولة حساب عدد التعليمات الفعلية التي تطبّقها هذه الدالة لإيجاد الدالة f( n )، والوصول إلى نتيجة أنها خطية بالفعل، مع العلم أنّ خطية تعني Θ( n ). يحتوي الشكل التالي على رسم بياني لمساعدتك على فهم مفهوم العودية المُطبَّقة عند استدعاء الدالة factorial( 5 )، ويجب على هذا الشكل توضيح لماذا تعقيد هذه الدالة هو تعقيد خطي: العودية (معاوة الاستدعاء) التي تطبّقها الدالة factorial التعقيد اللوغاريتمي Logarithmic complexity إحدى المشكلات الشهيرة في علوم الحاسوب هي البحث عن قيمة داخل مصفوفة، ولقد حلّلنا هذه المشكلة سابقًا من خلال الحالة العامة، كما تصبح هذه المشكلة ممتعةً إذا كان لدينا مصفوفة مرتَّبة ونريد إيجاد قيمة معينة بداخلها، حيث تُسمَّى إحدى طرق القيام بذلك البحث الثنائي binary search. ننظر إلى العنصر الأوسط في المصفوفة، وإذا وجدنا العنصر هناك، فقد انتهينا؛ وإلّا فإذا كانت القيمة التي وجدناها أكبر من القيمة التي نبحث عنها، فسنعلم أن العنصر سيكون في الجزء الأيسر من المصفوفة؛ وإلّا فإننا نعلم أنه سيكون في الجزء الأيمن من المصفوفة، كما يمكننا الاستمرار في تقسيم هذه المصفوفات الصغيرة إلى نصفين حتى يتبقّى عنصر واحد فقط، وتوضّح الشيفرة الوهمية التالية هذه الفكرة: def binarySearch( A, n, value ): if n = 1: if A[ 0 ] = value: return true else: return false if value < A[ n / 2 ]: return binarySearch( A[ 0...( n / 2 - 1 ) ], n / 2 - 1, value ) else if value > A[ n / 2 ]: return binarySearch( A[ ( n / 2 + 1 )...n ], n / 2 - 1, value ) else: return true تُعَدّ هذه الشيفرة الوهمية تبسيطًا للتطبيق الفعلي، كما يُعَدّ وصفها أسهل من تطبيقها عمليًا، حيث يحتاج المبرمج إلى الاهتمام ببعض مشاكل التطبيق. يجب تطبيق الدالة floor()‎ أو ceil()‎ بسبب وجود أخطاء بفارق الواحد off-by-one، وقد لا ينتج عن القسمة على العدد 2 قيمةً صحيحةً، فالجزء الصحيح أو المتمم الصحيح الأسفل floor لعدد حقيقي ما x، هو أكبر عدد صحيح ليس أكبر من x، فصحيح العدد 2.6 هو 2، أي أنّ أكبر عدد صحيح ليس أكبر من 2.6. بينما السقف أو المتمم الصحيح الأعلى ceil لعدد حقيقي x، فهو أصغر عدد صحيح ولكنه ليس أصغر من x، لأن سقف العدد 2.15 هو 3، أي أنّ أصغر عدد صحيح ليس أصغر من 2.15. لكن يمكننا افتراض أن هذه الطريقة ستنجح دائمًا، وسنفترض أنّ تطبيقنا الفعلي يهتم بأخطاء الفراق الواحد off-by-one، وذلك لأننا نريد تحليل تعقيد هذه الطريقة فقط. إذا لم تطبّق البحث الثنائي مطلقًا، فقد ترغب في فعل ذلك باستخدام لغة البرمجة المفضلة لديك. يوضّح الشكل الآتي لصاحبه لوك فرانكل Luke Francl طريقة عمل البحث الثنائي باستخدام العودية، حيث يُميَّز الوسيط A لكل استدعاء باللون الأسود، وتستمر العودية حتى تصبح المصفوفة مكوّنةً من عنصر واحد فقط. إذا لم تكن متأكدًا من عمل هذه الطريقة، فشغّلها يدويًا باستخدام مثال بسيط واقنع نفسك بأنها تعمل بالفعل. لنحاول تحليل هذه الخوارزمية العودية، حيث سنفترض -من أجل التبسيط- أن المصفوفة تُقسَم دائمًا إلى نصفين تمامًا، متجاهلين الجزأين 1+ و 1- من الاستدعاء العودي. كما يجب اقتناعك بعدم تأثير إجراء تغيير بسيط على نتائج التعقيد مثل تجاهل الجزأين 1+ و1-، وهذه حقيقة يجب عادةً إثباتها إذا أردنا أن نكون حريصين من وجهة نظر رياضية، لكنها بديهية عمليًا. سنفترض للتبسيط أن حجم المصفوفة هو بالضبط قوة للعدد 2. بحيث لا يغير هذا الافتراض النتائج النهائية لتعقيدنا الذي سنصل إليه، وسيحدث السيناريو الأسوأ لهذه المشكلة عند عدم ظهور القيمة التي نبحث عنها في مصفوفتنا على الإطلاق، كما سنبدأ في هذه الحالة بمصفوفة ذات حجم n في الاستدعاء الأول للعودية، ثم سنحصل على مصفوفة بحجم n / 2 في الاستدعاء التالي. وبعدها سنحصل على مصفوفة بحجم n / 4 في الاستدعاء العودي التالي، ثم مصفوفة بحجم n / 8، وهكذا؛ حيث تقسَم المصفوفة إلى نصفين في كل استدعاء، حتى نصل إلى عنصر واحد فقط، لذلك لنكتب عدد العناصر في المصفوفة الخاصة بنا لكل استدعاء كما يلي: 0th iteration: n 1st iteration: n / 2 2nd iteration: n / 4 3rd iteration: n / 8 … ith iteration: n / 2i last iteration: 1 لاحظ احتواء المصفوفة على n / 2i عنصر في التكرار i بسبب تقسيم المصفوفة في كل تكرار إلى نصفين، مما يعني أننا نقسم عدد عناصرها على 2، أي نضرب المقام بـ 2؛ وإذا فعلنا ذلك i مرة، فسنحصل على n / 2i، إذ يستمر هذا الإجراء ونحصل على عدد أصغر من العناصر مع كل قيمة أكبر للمتغير i، حتى نصل إلى التكرار الأخير الذي يتبقى فيه عنصر واحد فقط، وإذا رغبنا في معرفة التكرار i الذي يتبقى فيه عنصرٌ واحد فقط، فعلينا حل المعادلة التالية: 1 = n / 2i سيكون هذا صحيحًا فقط عندما نصل إلى الاستدعاء النهائي للدالة ()binarySearch، وليس في الحالة العامة، لذلك فإيجاد قيمة i هنا سيساعدنا في العثور على التكرار الذي ستنتهي فيه العودية. وإذا ضربنا كلا الطرفين بـ 2i فسنحصل على: 2i= n يجب أن تبدو هذه المعادلة مألوفة إذا قرأت قسم اللوغاريتمات أعلاه، وبالتالي ينتج: i = log( n ) يخبرنا هذا أن عدد التكرارات المطلوبة لإجراء بحث ثنائي هو log( n )، حيث n هي عدد عناصر المصفوفة الأصلية، ويُعَدّ ذلك أمرًا منطقيًا. بافتراض أنّ n = 32 فسيكون لدينا مصفوفة مؤلفة من 32 عنصرًا، فكم مرةً يجب تقسيم هذه المصفوفة إلى نصفين للحصول على عنصر واحد فقط؟ سنحتاج إلى تقسيمها خمس مرات للحصول إلى عنصر واحد، أي بالترتيب التالي: 32 ← 16 ← 8 ← 4 ← 2 ← 1، والعدد 5 هو لوغاريتم 32، لذلك يكون تعقيد البحث الثنائي هو Θ( log( n ) ). تسمح لنا هذه النتيجة الأخيرة بمقارنة البحث الثنائي والبحث الخطي، وبما أن ( log( n أصغر بكثير من n، فيمكن استنتاج أن البحث الثنائي أسرع بكثير من البحث الخطي للبحث داخل مصفوفة، لذلك يُستحسَن إبقاء المصفوفات مرتبةً عند العمل على عدة عمليات بحث فيها. الفرز الأمثل Optimal sorting تهانينا! لقد بتّ الآن تعرف كلًا من تحليل تعقيد الخوارزميات، وسلوك الدوال المقارب، وصيغة big-O؛ بالإضافة إلى كيفية إيجاد تعقيد الخوارزمية ليكون O( 1 )، وO( log( n ) )، وO( n )، وO( n2 ) وما إلى ذلك بديهيًا، كما أصبحت تعرف الرموز o، وO، وω، وΩ، وΘ، وماذا يعني تحليل الحالة الأسوأ أيضًا. يُعَدّ هذا القسم الأخير من المقال أعقد قليلًا، لذا لا تتردد في أخذ راحة إذا تعبت، حيث سيتطلب منك التركيز وقضاء بعض الوقت في حل التمارين، لكنه سيوفر لك طريقةً مفيدةً للغاية في تحليل تعقيد الخوارزمية وهذا أمرٌ مهم، لذلك فهو بالتأكيد يستحق الفهم. يُدعى الفرز الذي طبقناه سابقًا بالفرز الانتقائي، حيث ذكرنا أنه ليس الفرز الأمثل؛ والخوارزمية المثلى هي الخوارزمية التي تحل المشكلة بأفضل طريقة ممكنة، مما يعني عدم وجود خوارزميات أفضل منها، وهذا يعني أن لدى جميع الخوارزميات الأخرى الموجهة لحل المشكلة تعقيدًا أسوأً أو مساويًا لتلك الخوارزمية المثلى، كما قد يكون هناك العديد من الخوارزميات المثلى لمشكلةٍ ما بحيث تشترك جميعها في التعقيد نفسه، ويمكن حل مشكلة الفرز على النحو الأمثل بطرق مختلفة، كما يمكن استخدام فكرة البحث الثنائي نفسها من أجل الفرز بسرعة، وتسمى طريقة الفرز المثلى هذه الفرز بالدمج mergesort. سنحتاج أولًا في إجراء فرز الدمج، إلى إنشاء دالة مساعدة والتي سنستخدمها بعد ذلك لإجراء الفرز الفعلي، حيث تأخذ دالة الدمج merge مصفوفتين مرتّبتَين سابقًا، ثم تدمجهما معًا في مصفوفة كبيرة مرتبة، ويمكن القيام بذلك بسهولة كما يلي: def merge( A, B ): if empty( A ): return B if empty( B ): return A if A[ 0 ] < B[ 0 ]: return concat( A[ 0 ], merge( A[ 1...A_n ], B ) ) else: return concat( B[ 0 ], merge( A, B[ 1...B_n ] ) ) تأخذ الدالة concat عنصرًا يُسمى "الرأس head" ومصفوفة تُسمى "الذيل tail"، ثم تبني وتعيد مصفوفةً جديدةً تحتوي على عنصر "الرأس" الذي يمثِّل العنصر الأول في المصفوفة الجديدة، وعلى عنصر "الذيل" الذي يمثِّل بقية العناصر الموجودة في المصفوفة، حيث تعيد الدالة concat( 3, [ 4, 5, 6 ] ) مثلًا، ما يلي: [ 3, 4, 5, 6 ]. ونستخدم المتغيرين An وBn للإشارة إلى أحجام المصفوفتين A وB على التوالي. تمرين 8 تحقق من إجراء الدالة المذكورة أعلاه لعملية الدمج، ثم أعد كتابتها بلغة البرمجة المفضلة لديك بطريقة تكرارية -أي باستخدام حلقات for- بدلًا من استخدام العودية. يكشف تحليل هذه الخوارزمية أن وقت تشغيلها Θ( n )، حيث يمثِّل n طول المصفوفة الناتجة أي n = A_n + B_n. تمرين 9 تحقق من أن وقت تشغيل الدالة merge هو Θ( n ). يمكننا بناء خوارزمية فرز أفضل باستخدام هذه الدالة، حيث نقسم المصفوفة إلى قسمين، ونرتِّب كل جزء من الجزأين عوديًا، ثم ندمج المصفوفتين المرتبتين في مصفوفة واحدة كبيرة، وذلك كما يلي: def mergeSort( A, n ): if n = 1: return A # it is already sorted middle = floor( n / 2 ) leftHalf = A[ 1...middle ] rightHalf = A[ ( middle + 1 )...n ] return merge( mergeSort( leftHalf, middle ), mergeSort( rightHalf, n - middle ) ) يُعَدّ فهم هذه الدالة أصعب مما مررنا به سابقًا، لذلك قد يأخذ منك التمرين التالي بضع دقائق. تمرين 10 تحقق من صحة الدالة mergeSort، وذلك من خلال التحقق من تمكّن الدالة mergeSort من فرز المصفوفة المعطاة بصورة صحيحة، وإذا واجهتك مشكلة في فهم سبب نجاحها في ذلك، فجرّبها باستخدام مصفوفة صغيرة على أساس مثال ثم شغّلها "يدويًا"، وتأكد عند تشغيل هذه الدالة يدويًا من حصولك على النصف الأيسر leftHalf والنصف الأيمن rightHalf. وإذا قسّمت المصفوفة في المنتصف تقريبًا، فليس من الضروري قسم المصفوفة في المنتصف تمامًا إذا احتوت على عدد فردي من العناصر وهذا الهدف من استخدام الدالة floor أعلاه. لنحلل الآن تعقيد الدالة mergeSort، حيث سنقسم المصفوفة إلى نصفين متساويين في الحجم على غرار دالة البحث الثنائي binarySearch في كل خطوة من خطوات الدالة mergeSort، ولكننا سنحافظ في هذه الحالة على كلا النصفين طوال فترة التنفيذ، ثم نطبّق الخوارزمية عوديًا في كل نصف، كما نطبّق عملية الدمج merge على النتيجة التي تستغرق وقتًا مقداره Θ( n ) بعد أن تعيد الخوارزمية العودية. لبهذا نكون قد قسمنا المصفوفة الأصلية إلى مصفوفتين بحجم n / 2 لكل منهما، ثم دمجنا هذه المصفوفات، وهي عملية لدمج n عنصرًا وبالتالي تستغرق وقتًا (Θ (n، كما يوضح الشكل التالي هذه العملية العودية: شجرة العودية لطريقة الفرز بالدمج merge sort تمثِّل كل دائرة استدعاءً للدالة mergeSort كما يشير الرقم المكتوب في الدائرة إلى حجم المصفوفة التي يجري فرزها، إذ تكون الدائرة الزرقاء العلوية الاستدعاء الأصلي للدالة mergeSort، بحيث نحصل على فرز مصفوفة بالحجم n، كما تشير الأسهم إلى الاستدعاءات المتكررة التي تجريها الدوال فيما بينها. يعمل الاستدعاء الأصلي للدالة mergeSort على استدعائها مرتين في مصفوفتين وحجم كل منهما n / 2، حيث يشار إلى ذلك بواسطة السهمين الموجودين في الأعلى، ثم يجري كل من هذين الاستدعائَين بدورهما استدعائين خاصين بهما لدمج مصفوفتين بحجم n / 4 لكل منهما، وهكذا دواليك حتى نصل إلى مصفوفات ذات حجم 1؛ ويسمَّى هذا الرسم البياني بالشجرة العودية recursion tree، لأنه يوضح كيفية حدوث العودية ويظهر مثل شجرة، لكن الجذر root في الأعلى والأوراق في الأسفل، لذلك يظهر مثل شجرة مقلوبة. لاحظ أن العدد الإجمالي للعناصر هو n في كل مستوى من الرسم البياني أعلاه، حيث يحتوي المستوى الأول على استدعاء واحد فقط للدالة mergeSort مع مصفوفة بحجم n أي العدد الإجمالي للعناصر هو n، كما يحتوي المستوى الثاني على استدعائين للدالة mergeSort وكل منهما بحجم n / 2. لكن n / 2 + n / 2 = n وهكذا يكون العدد الإجمالي للعناصر هو n في هذا المستوى، كما توجد 4 استدعاءات في المستوى الثالث، بحيث يُطبَّق كل استدعاء على مصفوفة بحجم n / 4، أي سيساوي عدد العناصر الإجمالي n / 4 + n / 4 + n / 4 + n / 4 = 4n / 4 = n، وبالتالي نحصل على n عنصر. يجب على المستدعي في كل مستوى من هذا الرسم البياني إجراء عملية دمج merge على العناصر التي يعيدها المستدعَى، إذ يجب على الدائرة المشار إليها باللون الأحمر مثلًا، ترتيب عدد n / 2 من العناصر، وذلك بتقسيم المصفوفة ذات الحجم n / 2 إلى مصفوفتين بحجم n / 4، ثم تُستدعَى الدالة mergeSort عوديًا لفرز تلك المصفوفة، ثم تُدمَجان معًا، ويُشار إلى هذه الاستدعاءات بالدوائر ذات اللون الأخضر. تحتاج عملية الدمج إلى دمج n / 2 عنصر في كل مستوى من الشجرة، ويكون العدد الإجمالي للعناصر المدموجة هو n. حيث تدمج الدالة في ذلك المستوى n / 2 عنصر، ويجب على الدالة الموجودة على يمينها -ذات اللون الأزرق- دمج n / 2 عنصرأيضًا، وبالتالي ينتج عدد العناصر الإجمالي التي يجب دمجها في هذا المستوى . تعقيد كل مستوى هو Θ( n )، كما يكون عدد المستويات في هذا الرسم البياني، والذي يُطلق عليه أيضًا عمق depth شجرة العودية مساويًا لـ log( n )، وسبب ذلك هو السبب ذاته تمامًا الذي استخدمناه عند تحليل تعقيد البحث الثنائي. لدينا log( n ) مستوى وتعقيد كل مستوى هو Θ( n )، وبالتالي، يكون تعقيد الدالة mergeSort هو Θ(n * log( n ))، وهذا أفضل بكثير من Θ( n2 ) الذي هو تعقيد خوارزمية الفرز الانتقائي -تذكر أنّ log( n ) أصغر بكثير من n، وبالتالي يكون n * log (n) أصغر بكثير من n * n = n2-، وإذا وجدت ذلك معقدًا، فلا تقلق لأن الأمر ليس سهلًا في المرة الأولى. يسمح لنا تحليل التعقيد بمقارنة الخوارزميات لمعرفة أيها أفضل كما رأيت في هذا المثال الأخير، ويمكننا الآن أن نكون على يقينٍ تام من تفوّق خوارزمية الفرز بالدمج على خوارزمية الفرز الانتقائي للمصفوفات الكبيرة، كما سيكون استخلاص هذا الاستنتاج صعبًا إذا لم تملك الخلفية النظرية لتحليل الخوارزمية. تُستخدَم خوارزميات الفرز التي لها وقت تشغيل Θ( n * log( n ) )عمليًا، إذ تستخدم نواة نظام لينكس مثلًا، خوارزمية فرز تسمى heapsort، والتي لها وقت تشغيل مماثل لخوارزمية الفرز بالدمج mergesort الذي أوجدناه للتو، والذي هو Θ( n log( n ) )، لذلك فهو الأمثل. لاحظ أننا لم نثبت أن خوارزميات الفرز هذه هي الأمثل، لأن ذلك يتطلب معرفةً رياضيةً أكبر، لكن كن مطمئنًا أنه لا يمكن لهذه الخوارزميات المثلى التحسن أكثر من ذلك من وجهة نظر التعقيد. يجب الآن بعد قراءة هذا المقال أن يكون حدسك الذي طورته لتحليل تعقيد الخوارزمية قادرًا على مساعدتك في تصميم برامج أسرع، ويجب عليك تركيز جهودك المثلى على الأشياء المهمة حقًا بدلًا من الأشياء الصغيرة التي لا تهمك، مما يتيح لك العمل بصورةٍ أكثر إنتاجية. كما يجب أن تكون اللغة الرياضية والتمثيل الذي طُوِّر في هذا المقال مثل صيغة Big-O مفيدَين أيضًا في التواصل مع مهندسي البرمجيات الآخرين عندما تنقاشهم بموضوع وقت تشغيل الخوارزميات. ترجمة -وبتصرف- للمقال A Gentle Introduction to Algorithm Complexity Analysis لصاحبه Dionysis "dionyziz" Zindros. اقرأ أيضًا المرجع الشامل إلى تعلم الخوارزميات للمبتدئين تعقيد الخوارزميات Algorithms Complexity ترميز Big-O في الخوارزميات خوارزمية ديكسترا Dijkstra’s Algorithm

تتكلف البرامج بموارد أكثر كلما زاد حجمها، وذلك ليس بسبب الوقت الذي تستغرقه من أجل بنائها، بل لأنّ الحجم الكبير يتبعه تعقيد أكثر، ويحيّر ذلك التعقيد المبرمجين العاملين عليه، حيث تجعلهم تلك الحيرة يرتكبون أخطاءً في صورة زلات برمجية Bugs، وعليه يكون البرنامج الكبير فرصةً كبيرةً لهذه الزلات بالاختفاء وسط الشيفرات، مما يصعِّب الوصول إليها. لنَعُدْ إلى المثالين الأخيرَين المذكورَين في مقدمة هذه السلسلة، حيث يحتوي المثال الأول منهما على ستة أسطر، وهو مستقل بذاته، انظر كما يلي: let total = 0, count = 1; while (count <= 10) { total += count; count += 1; } console.log(total); أما الثاني فيعتمد على دالتين خارجيتين، ويتكوّن من سطر واحد فقط، كما يلي: console.log(sum(range(1, 10))); برأيك، أيهما أكثر عرضةً لتكون فيه زلة برمجية؟ إذا حسبنا حجم تعريفي sum وrange، فسيكون البرنامج الثاني أكبر من الأول، لكن لا زلنا نراه أكثر صِحة، حيث عبَّر عن الحل بألفاظ تتوافق مع المشكلة المحلولة، فلا يتعلق استدعاء مجال من الأعداد بالحلقات التكرارية والعدادات بقدر ما يتعلق بالمجالات والمجموع الإجمالي؛ وتحتوي تعاريف هذه الألفاظ (دالتي sum، وrange) على حلقات تكرارية، وعدادات، وتفاصيل أخرى، وبما أنها تعبر عن مفاهيم أبسط من البرنامج ككل، فهي أدنى ألا تحتوي على أخطاء. التجريد تسمى هذه الأنواع من الألفاظ في السياقات البرمجية بالتجريدات Abstractions، وهي تخفي التفاصيل الدقيقة وتعطينا القدرة على الحديث عن المشاكل على مستوى أعلى أو أكثر تجريدًا. انظر هاتين الوصفتين أدناه لتقريب الأمر: الوصفة الأولى: الوصفة الثانية: لا شك أن الوصفة الثانية أقصر وأيسر في التفسير والفهم، لكن ستحتاج إلى فهم المصطلحات الخاصة بالطهي، مثل: النقع، والطهي، والتقطيع، والتجفيف (هذه المصطلحات للتقريب مثالًا، وشاهدها أن تكون على دراية بمصطلحات مجال المشكلة التي تريد حلها، وإلا فهي معروفة لكل أحد). يقع الكثير من المبرمجين في خطأ الوصفة الأولى عند سردهم للخطوات الدقيقة والصغيرة التي على الحاسوب تنفيذها خطوةً بخطوة، وذلك بسبب عدم ملاحظتهم للمفاهيم العليا في المشكلة التي بين أيديهم، ويُعَدّ الانتباه عند حلك لمشكلة بهذا الأسلوب مهارةً مفيدةً جدًا. تجريد التكرار تُعَدّ الدوال البسيطة طريقة ممتازة لبناء تجريدات، غير أنها تعجز عن ذلك أحيانًا، فمن الشائع أن يفعل البرنامج شيئًا ما بعدد معيّن من المرات باستخدام حلقة for، فمثلًا: for (let i = 0; i < 10; i++) { console.log(i); } فهل نستطيع تجريد مفهوم "فعل شيء ما عددًا من المرات قدره N" في صورة دالة؟ بدايةً، من السهل كتابة دالة تستدعي console.log عددًا من المرات قدره N: function repeatLog(n) { for (let i = 0; i < n; i++) { console.log(i); } } لكن ماذا لو أردنا فعل شيء آخر غير تسجيل الأعداد؟ بما أنّه يمكن تمثيل "فعل شيء ما" على أساس دالة، والدوال ما هي إلا قيم، فسنستطيع تمرير إجراءنا على أساس قيمة دالة، وذلك كما يلي: function repeat(n, action) { for (let i = 0; i < n; i++) { action(i); } } repeat(3, console.log); // → 0 // → 1 // → 2 لسنا في حاجة إلى تمرير دالة معرَّفة مسبقًا إلى repeat، فغالبًا من السهل إنشاء قيمة دالة عند الحاجة. let labels = []; repeat(5, i => { labels.push(`Unit ${i + 1}`); }); console.log(labels); // → ["Unit 1", "Unit 2", "Unit 3", "Unit 4", "Unit 5"] وكما ترى، فهذا مهيكل في صورة محاكية لحلقة for، إذ يصف نوع الحلقة التكرارية أولًا، ثم يوفر متنًا لها، غير أنّ المتن الآن مكتوب على أساس قيمة دالة مغلّفة بأقواس الاستدعاء إلى repeat، وهذا هو السبب الذي يجعل من الواجب إغلاقها بقوس إغلاق معقوص ‎}‎ وقوس إغلاق عادي ‎)‎ بأقواس إغلاق، وفي حالة هذا المثال عندما يكون المتن تعبيرًا واحدًا وصغيرًا، فيمكنك إهمال الأقواس المعقوصة وكتابة الحلقة في سطر واحد. الدوال العليا تسمى الدوال التي تعمل على دوال أخرى سواءً بأخذها على أساس وسائط أو بإعادتها لها، باسم الدوال العليا higher-order functions، وبما أنّ الدوال ما هي إلا قيم منتظمة، فلا شيء جديد في وجود هذا النوع منها، والمصطلح قادم من الرياضيات حين يؤخذ الفرق بين الدوال والقيم الأخرى على محمل الجد. وتسمح لنا الدوال العليا بعملية التجريد على القيم والإجراءات أيضًا، وتأتي في عدة أشكال وصور، فقد تنشِئ الدوال دوالًا أخرى جديدةً، كما يلي: function greaterThan(n) { return m => m > n; } let greaterThan10 = greaterThan(10); console.log(greaterThan10(11)); // → true وقد تغيّر الدوال دوالًا أخرى، كما في المثال التالي: function noisy(f) { return (...args) => { console.log("calling with", args); let result = f(...args); console.log("called with", args, ", returned", result); return result; }; } noisy(Math.min)(3, 2, 1); // → calling with [3, 2, 1] // → called with [3, 2, 1] , returned 1 كما توفر الدوال أنواعًا جديدةً من تدفق التحكم control flow: function unless(test, then) { if (!test) then(); } repeat(3, n => { unless(n % 2 == 1, () => { console.log(n, "is even"); }); }); // → 0 is even // → 2 is even يوفر تابع مصفوفة مدمج forEach شيئًا مثل حلقة for/of التكرارية على أساس دالة عليا، وذلك كما يلي: ["A", "B"].forEach(l => console.log(l)); // → A // → B مجموعات البيانات النصية تُعَدّ معالجة البيانات إحدى الجوانب التي تبرز فيها أهمية الدوال العليا، ولضرْب مثال على ذلك سنحتاج إلى بعض البيانات الفعلية، كما سنستخدم في هذا المقال مجموعة بيانات عن نصوص وأنظمة كتابة، مثل: اللاتينية، والعربية، والسيريلية (حروف اللغات الأوراسية، مثل: الروسية، والبلغارية). ترتبط أغلب محارف اللغات المكتوبة بنص معين، ولعلك تذكر حديثنا عن الترميز الموحد Unicode الذي يسند عددًا لكل محرف من محارف هذه اللغات، حيث يحتوي هذا المعيار على 140 نصًا مختلفًا، من بينها 81 لا تزال مستخدمةً، في حين صارت 59 منها مهملةً أو تاريخيةً، أي لم تَعُدْ مستخدمة؛ فعلى سبيل المثال، انظر هذه الكتابة من اللغة التاميلية: تحتوي مجموعة البيانات على بعض أجزاء البيانات من النصوص المئة والأربعين المعرَّفة في اليونيكود، وهي متاحة في صندوق اختبار هذا المقال على صورة رابطة SCRIPTS. { name: "Coptic", ranges: [[994, 1008], [11392, 11508], [11513, 11520]], direction: "ltr", year: -200, living: false, link: "https://en.wikipedia.org/wiki/Coptic_alphabet" } يخبرنا الكائن السابق بكل من: اسم النص، ومجالات اليونيكود المسنَدة إليه، واتجاه الكتابة، والزمن التقريبي لنشأة هذه اللغة، وما إذا كانت مستخدمةً أم لا، ورابط إلى مزيد من التفاصيل والبيانات عنها؛ وقد يكون اتجاه الكتابة من اليسار إلى اليمين "ltr"، أو من اليمين إلى اليسار "rtl"، كما في حالة اللغتين العربية والعبرية، أو من الأعلى إلى الأسفل "ttb" كما في حالة اللغة المنغولية. تحتوي خاصية ranges على مصفوفة من مجالات المحارف، حيث يكون كل منها مصفوفةً من عنصرين، هما الحدين الأدنى والأعلى، ويُسنَد أيّ رمز للمحارف بين هذه المجالات إلى النص، كما يُضمَّن الحد الأدنى فيها؛ أما الحد الأعلى فلا، أي يُعَدّ رمز 994 محرفًا قبطيًا Coptic في المثال السابق؛ أما الرمز 1008 فلا. ترشيح المصفوفات نستخدم دالة filter لإيجاد النصوص واللغات التي مازالت مستخدَمةً في مجموعات البيانات، إذ تُرشِّح عناصر المصفوفة التي لا تجتاز اختبارًا تجريه عليها: function filter(array, test) { let passed = []; for (let element of array) { if (test(element)) { passed.push(element); } } return passed; } console.log(filter(SCRIPTS, script => script.living)); // → [{name: "Adlam", …}, …] تستخدم الدالة وسيطًا اسمه test، وهو قيمة دالةٍ لملء الفراغ "gap" أثناء عملية اختيار العناصر. إذ تلاحظ كيف تبني دالة filter مصفوفةً جديدةً من العناصر التي تجتاز اختبارها بدلًا من حذف العناصر من المصفوفة القديمة، وهذا يشير إلى أنّ هذه الدالة دالةً نقيةً pure function، إذ لا تُعدِّل المصفوفة المُمرَرة إليها. تشبه هذه الدالة التابع forEach في كونها تابع مصفوفة قياسي، وقد عرَّف المثال السابق الدالة لتوضيح كيفية عملها من الداخل ليس إلا؛ أما من الآن فصاعدًا فسنستخدمها فقط كما يلي: console.log(SCRIPTS.filter(s => s.direction == "ttb")); // → [{name: "Mongolian", …}, …] التحويل مع map ليكن لدينا مصفوفة كائنات تمثِّل عدة نصوص، حيث أُنتجت بترشيح مصفوفة SCRIPTS، لكننا نريد مصفوفةً من الأسماء لأنها أسهل في البحث والتدقيق. هنا يأتي دور التابع map الذي يحوّل مصفوفةً بتطبيق دالة على جميع عناصرها، ثم يبني مصفوفةً جديدةً من القيم المعادة، وتكون المصفوفة الجديدة بطول المصفوفة المدخلة، مع إعادة توجيه محتوياتها في شكل form جديد بواسطة الدالة. function map(array, transform) { let mapped = []; for (let element of array) { mapped.push(transform(element)); } return mapped; } let rtlScripts = SCRIPTS.filter(s => s.direction == "rtl"); console.log(map(rtlScripts, s => s.name)); // → ["Adlam", "Arabic", "Imperial Aramaic", …] وبالمثل، يُعَدّ التابع map تابع مصفوفة قياسي، أي يحاكي كلًا من: filter، وforEach. التلخيص باستخدام reduce يُعَدّ إجراء حسابات على قيمة واحدة من المصفوفات من العمليات الشائعة على هذه المصفوفات، ومثالنا التعاودي الذي يستدعي تجميعةً من الأعداد هو مثال على هذا، وكذلك إيجاد النص الحاوي على أكبر عدد من المحارف. تُدعى العملية العليا الممثِلة لهذا النمط بـ reduce، وتُدعى fold أحيانًا، إذ تُنتِج قيمةً بتكرار أخذ عنصر ما من المصفوفة، ومن ثم جمعه مع القيمة الحالية، فتبدأ عند إيجاد مجموع الأعداد من الصفر، وتضيف كل عنصر إلى المجموع الإجمالي. تأخذ reduce جزءًا من المصفوفة، ودالة جامعة combining function، وقيمة بدء start value، على أساس معامِلات، وتختلف هذه الدالة عن دالتي filter، وmap المتّسمتين بالوضوح والمباشرة أكثر، كما في الدالة التالية: function reduce(array, combine, start) { let current = start; for (let element of array) { current = combine(current, element); } return current; } console.log(reduce([1, 2, 3, 4], (a, b) => a + b, 0)); // → 10 يملك تابع المصفوفة القياسي reduce الموافق لهذه الدالة خاصيةً مميزة، إذ يسمح لك بإهمال وسيط start إن كان في مصفوفتك عنصرًا واحدًا على الأقل، حيث سيأخذ العنصر الأول من المصفوفة على أساس قيمة بدء له، ويبدأ التقليل من العنصر الثاني، كما في المثال التالي: console.log([1, 2, 3, 4].reduce((a, b) => a + b)); // → 10 يمكننا استخدام reduce مرتين لحساب عدد محارف أو كلمات نص ما، كما في المثال التالي: function characterCount(script) { return script.ranges.reduce((count, [from, to]) => { return count + (to - from); }, 0); } console.log(SCRIPTS.reduce((a, b) => { return characterCount(a) < characterCount(b) ? b : a; })); // → {name: "Han", …} تقلل دالة charactercount المجالات المسندَة إلى نص ما بجمع أحجامها، حيث تلاحظ استخدام التفكيك في قائمة المعامِلات للدالة المقلِّلة، ثم يُستَدعى التابع reduce مرةً ثانية لإيجاد أكبر نص من خلال موازنة نصين في كل مرة وإعادة الأكبر بينهما. تحتوي لغات الهان -نظام الكتابة الصيني، والياباني، والكوري- على أكثر من 89 ألف محرف مسنَد إليها في معيار يونيكود، مما يجعلها أكبر نظام كتابة في مجموعة البيانات. وقد قرر مجمع الترميز الموحد Unicode Consortium معاملة تلك اللغات على أنها نظام كتابة واحد لتوفير رموز المحارف، رغم مضايقة هذا لبعض العامة، وسُمي ذلك القرار بتوحيد الهان Han Unification. قابلية التركيب لن يبدو مثال إيجاد أكبر نص سيئًا إذا كتبناه دون استخدام الدوال العليا فيه، كما في المثال التالي: let biggest = null; for (let script of SCRIPTS) { if (biggest == null || characterCount(biggest) < characterCount(script)) { biggest = script; } } console.log(biggest); // → {name: "Han", …} لا يزال البرنامج سهل القراءة على الرغم من استخدام أربع رابطات جديدة، وزيادة أربعة أسطر أخرى، حيث تبرز الدوال العليا عند الحاجة لإجراء عمليات تركيب، فمثلًا، دعنا نكتب شيفرة للبحث عن السنة المتوسطة لإنشاء لغة ما سواءً كانت حيةً أو ميتةً في مجموعة البيانات: function average(array) { return array.reduce((a, b) => a + b) / array.length; } console.log(Math.round(average( SCRIPTS.filter(s => s.living).map(s => s.year)))); // → 1165 console.log(Math.round(average( SCRIPTS.filter(s => !s.living).map(s => s.year)))); // → 204 نتبين مما سبق أنّ متوسط اللغات الميتة في اليونيكود أقدم من الحية، وهذا متوقع لا شك، كما أنّ الشيفرة السابقة ليست صعبة القراءة، إذ يمكن النظر إليها على أنها أنبوب، حيث نبدأ فيها بجميع اللغات، ثم نرشّح الحية منها أو الميتة، وبعدها نأخذ أعوام هؤلاء ونحسب المتوسط، ثم نقرب النتيجة لأقرب رقم صحيح. كما نستطيع كتابة هذه العملية الحسابية على صورة حلقة تكرارية واحدة كبيرة، كما يلي: let total = 0, count = 0; for (let script of SCRIPTS) { if (script.living) { total += script.year; count += 1; } } console.log(Math.round(total / count)); // → 1165 لكن من الصعب قراءة هذا الأسلوب لمعرفة ما الذي يُحسب فيه، وبما أنّ النتائج البينية غير ممثلة على أساس قيم مترابطة، فستدور حول نفسك لاستخراج شيء مثل average إلى دالة منفصلة. يختلف هذان المنظوران من حيث ما يفعله الحاسوب، إذ يبني الأول مصفوفات جديدة عند تشغيل filter، وmap؛ بينما يحسب الثاني بعض الأعداد فقط وينجز عملًا أقل، ولا شك في تفضيلك للشيفرة المقروءة، لكن إن كنت تعالج مصفوفات ضخمة بتواتر، فيكون الأسلوب الأقل تجريدًا هنا أفضل بسبب السرعة الزائدة. السلاسل النصية ورموز المحارف تُعَدّ معرفة اللغة التي يستخدمها نص ما، إحدى استخدامات مجموعات البيانات، حيث يمَكّننا رمز المحرف المعطى من كتابة دالة لإيجاد اللغة الموافقة لهذا المحرف إن وجِدت، وذلك بسبب ارتباط كل لغة بمصفوفة من مجالات رموز المحارف، أي كما في المثال التالي: function characterScript(code) { for (let script of SCRIPTS) { if (script.ranges.some(([from, to]) => { return code >= from && code < to; })) { return script; } } return null; } console.log(characterScript(121)); // → {name: "Latin", …} يُعَدّ تابع some أعلاه دالةً عليا، إذ تأخذ دالة اختبار لتخبرك إن كانت الدالة تعيد true لأيّ عنصر في المصفوفة، ولكن كيف سنحصل على رموز المحارف في سلسلة نصية؟ ذكرنا في المقال الأول أنّ سلاسل جافاسكربت النصية مرمّزة على أساس تسلسلات من أعداد 16-بت، وتسمى هذه الأعداد بالأعداد البِتّية لمحارف السلسلة code units، حيث صُممِّت رموز المحارف character code في اليونيكود لتتوافق مع وحدة unit -مثل التي تعطيك 65 ألف محرف-؛ ولكن عارض بعض العامة زيادة الذاكرة المخصصة لكل محرف بعدما تبين عدم كفاية هذا، فقد ابتُكِرت لمعالجة هذه المشكلة صيغة UTF-16 التي استخدمتها جافاسكربت، حيث تصف أكثر المحارف شيوعًا باستخدام عدد بِتّي لمحرف 16-بت واحد، لكنها تستخدم زوجًا من تلك الأعداد البِتّية لغيرها. تُعَدّ UTF-16 فكرةً سيئةً حاليًا، إذ يبدو أنّها اختُرعت لخلق أخطاء! فمن السهل كتابة برامج تدّعي أنّ الأعداد البِتّية للمحارف والمحارف هما الشيء نفسه، وإن لم تكن لغتك تستخدم محارف من وحدتين فلا بأس؛ لكن سينهار البرنامج عند محاولة أحدهم استخدامه مع المحارف الصينية الأقل شيوعًا، ولحسن الحظ، فقد بدأ الجميع مع اختراع الإيموجي (الرموز التعبيرية) باستخدام المحارف ذات الوحدتين. لكن العمليات الواضحة في سلاسل جافاسكربت النصية، مثل: الحصول على طولها باستخدام خاصية length، والوصول إلى محتواها باستخدام الأقواس المربعة، لا تتعامل إلا مع الأعداد البِتية للمحارف، أنظر إلى ما يلي: // محرفي إيموجي، حصان وحذاء let horseShoe = "??"; console.log(horseShoe.length); // → 4 console.log(horseShoe[0]); // → (Invalid half-character) console.log(horseShoe.charCodeAt(0)); // → 55357 (رمز لنصف محرف) console.log(horseShoe.codePointAt(0)); // → 128052 (الرمز الحقيقي لرمز الحصان) يعطينا تابع charCodeAt عداد بِتي للمحرف فقط وليس الرمز الكامل للمحرف؛ أما تابع codePointAt الذي أضيف لاحقًا فيعطي محرف يونيكود كامل، لذا نستطيع استخدامه للحصول على المحارف من سلسلة نصية، لكن لا يزال الوسيط الممرر إلى codePointAt فهرسًا داخل تسلسل من الأعداد البِتّية لمحارف السلسلة، لذا فلا زلنا في حاجة إلى النظر هل يأخذ المحرف وحدتين رمزيتين أم وحدةً واحدةً للمرور على جميع المحارف في سلسلة نصية ما. ذكرنا في المقال السابق أنه يمكن استخدام حلقة for/of التكرارية على السلاسل النصية، وقد أُدخل هذا النوع من الحلقات -شأنه في هذا شأن codePointAt- في الوقت الذي كانت العامة فيه على علم بمشكلة UTF-16، لذا سيعطيك محارف حقيقية حين استخدامه للتكرار على سلسلة نصية، بدلًا من أعداد بِتية لمحارف السلسلة. let roseDragon = "??"; for (let char of roseDragon) { console.log(char); } // → ? // → ? وإن كان لديك محرف -وما هو إلا سلسلة نصية من وحدة رمزية أو اثنتين-، فستستطيع استخدام codePointAt(0)‎ للحصول على رمزه. التعرف على النصوص لدينا دالة characterScript، وطريقةً للتكرار الصحيح على المحارف، فالخطوة التالية إذًا هي عدّ المحارف المنتمية لكل لغة، كما في التجريد أدناه للعد: function countBy(items, groupName) { let counts = []; for (let item of items) { let name = groupName(item); let known = counts.findIndex(c => c.name == name); if (known == -1) { counts.push({name, count: 1}); } else { counts[known].count++; } } return counts; } console.log(countBy([1, 2, 3, 4, 5], n => n > 2)); // → [{name: false, count: 2}, {name: true, count: 3}] تتوقع دالة countBy تجميعةً collection -من أي شيء نستطيع التكرار عليه باستخدام for/of-، ودالةً لحساب اسم المجموعة group للعنصر المعطى، حيث تعيد مصفوفةً من الكائنات وكل منها هو اسم لمجموعة، وتخبرك بعدد العناصر الموجودة في تلك المجموعة. تستخدِم هذه الدالة تابع مصفوفة اسمه findIndex، حيث يحاكي indexof نوعًا ما، لكنه يبحث في القيمة الأولى التي تعيد true في الدالة المعطاة بدلًا من البحث عن قيمة معينة، كما يتشابه معه في إعادة ‎-1 عند عدم وجود مثل هذا العنصر، ونستطيع باستخدام countBy كتابة الدالة التي تخبرنا أيّ اللغات مستخدمة في نص ما. function textScripts(text) { let scripts = countBy(text, char => { let script = characterScript(char.codePointAt(0)); return script ? script.name : "none"; }).filter(({name}) => name != "none"); let total = scripts.reduce((n, {count}) => n + count, 0); if (total == 0) return "No scripts found"; return scripts.map(({name, count}) => { return `${Math.round(count * 100 / total)}% ${name}`; }).join(", "); } console.log(textScripts('英国的狗说"woof", 俄罗斯的狗说"тяв"')); // → 61% Han, 22% Latin, 17% Cyrillic تَعُدّ الدالة أولًا المحارف من خلال الاسم باستخدام characterScript لتعيينها اسمًا وتعود إلى السلسلة "none" من أجل المحارف التي ليست جزءًا من أي لغة، ثم يحذف استدعاء filter الإدخال الخاص بـ "none" من المصفوفة الناتجة بما أننا لا نهتم بتلك المحارف. سنحتاج إلى العدد الإجمالي للمحارف المنتمية إلى لغة ما لنستطيع حساب النسب، ويمكن معرفة ذلك من خلال reduce، وإن لم نجد هذه المحارف، فستعيد الدالة سلسلةً نصيةً محدّدةً، وإلا فستحوِّل مدخلات العد إلى سلاسل نصية مقروءة باستخدام map، ومن ثم تدمجها باستخدام join. خاتمة تبين لنا مما سبق أنّ تمرير قيم دالة ما إلى دوال أخرى مفيد جدًا، إذ يسمح لنا بكتابة دوال تُنمذِج الحسابات التي بها فراغات، إذ تستطيع الشيفرة التي تستدعي هذه الدوال ملء تلك الفراغات بتوفير قيم الدوال؛ أما المصفوفات فتعطينا عددًا من التوابع العليا، ويمكننا استخدام forEach للتكرار على عناصر داخل مصفوفة ما؛ ويعيد تابع filter مصفوفةً جديدةً تحتوي العناصر التي تمرِّر دالة التوقّع predicate function؛ كما نستطيع تحويل مصفوفة ما من خلال وضع كل عنصر في دالة باستخدام map؛ وكذلك نستطيع استخدام reduce لجمع عناصر مصفوفة ما داخل قيمة واحدة؛ أما تابع some فينظر هل ثَمّ عنصر مطابق لدالة توقع معطاة أم لا؛ ويبحث findIndex عن موضع أول عنصر مطابق لتوقّع ما. تدريبات التبسيط استخدم تابع method، وconcat لتبسيط مصفوفة بها مصفوفات أخرى، إلى مصفوفة واحدة بها جميع العناصر الموجودة في تلك المصفوفات كلها. تستطيع تعديل شيفرة التدريب لكتابة الحل وتشغيلها في طرفية المتصفح إن كنت تقرأ من متصفح، أو بنسخها إلى codepen. let arrays = [[1, 2, 3], [4, 5], [6]]; // ضع شيفرتك هنا. // → [1, 2, 3, 4, 5, 6] الحلقة التكرارية الخاصة بك اكتب دالة loop العليا التي تعطي شيئًَا مثل تعليمة حلقة for التكرارية، إذ تأخذ قيمةً، ودالة اختبار، ودالة تحديث، ومتن دالة. تستخدِم في كل تكرار دالة الاختبار أولًا على قيمة التكرار الحالية، وتتوقف إن لم تتحقق -أي أعادت false-، ثم تستدعي متن الدالة لتعطيه القيمة الحالية، وأخيرًا تستدعي دالة التحديث لإنشاء قيمة جديدة والبدء من جديد. تستطيع عند تعريف الدالة استخدام حلقة تكرارية عادية لتنفيذ التكرار الفعلي. تستطيع تعديل شيفرة التدريب لكتابة الحل وتشغيلها في طرفية المتصفح إن كنت تقرأ من متصفح، أو بنسخها إلى codepen. // شيفرتك هنا. loop(3, n => n > 0, n => n - 1, console.log); // → 3 // → 2 // → 1 كل شيء تحتوي المصفوفات على تابع every بالتماثل مع تابع some، ويتحقق every إذا تحققت الدالة المعطاة لكل عنصر في المصفوفة، ويمكن النظر إلى some في سلوكه على المصفوفات على أنه عامِل ||، في حين يكون every عامِل &&. استخدم every على أساس دالة تأخذ مصفوفة ودالة توقّع على أساس معامِلات، واكتب نسختين، إحداهما باستخدام حلقة تكرارية، والأخرى باستخدام تابع some. تستطيع تعديل شيفرة التدريب لكتابة الحل وتشغيلها في طرفية المتصفح إن كنت تقرأ من متصفح، أو بنسخها إلى codepen. function every(array, test) { // ضع شيفرتك هنا. } console.log(every([1, 3, 5], n => n < 10)); // → true console.log(every([2, 4, 16], n => n < 10)); // → false console.log(every([], n => n < 10)); // → true إرشادات للحل يستطيع التابع every إيقاف تقييم المزيد من العناصر بمجرد إيجاد عنصر واحد غير مطابق، تمامًا كما في حالة عامل &&، لذا تستطيع النسخة المبنية على الحلقة التكرارية القفز خارجها -باستخدام break، أو return- عند إيجاد العنصر الذي تعيد له دالة التوقّع false، فإذا انتهت الحلقة التكرارية دون مقابلة عنصر كهذا، فسنعرف بتطابق جميع العناصر ويجب لإعادة true. نستخدم قوانين دي مورجَن De Morgan لبناء every فوق some، والذي ينص على أنّ a && b تساوي ‎!(!a || !b)‎، ويمكن أن يُعمَّم هذا للمصفوفات، حيث تكون كل العناصر في المصفوفة مطابقةً إذا لم يكن في المصفوفة عنصرًا غير مطابق. اتجاه الكتابة السائد اكتب دالة تحسب اتجاه الكتابة السائد في نص ما، وتذكّر أنّه لدى كل كائن من كائنات اللغات خاصية direction، والتي من الممكن أن تكون: ltr، أو rtl، أو ttb، كما ذكرنا في سابق شرحنا هنا. الاتجاه السائد هو اتجاه أغلب المحارف المرتبطة بلغة ما، وستستفيد من دالتي: characterScript، وcountBy المعرَّفتَين في هذا المقال. تستطيع تعديل شيفرة التدريب لكتابة الحل وتشغيلها في طرفية المتصفح إن كنت تقرأ من متصفح، أو بنسخها إلى codepen. function dominantDirection(text) { // ضع شيفرتك هنا. } console.log(dominantDirection("Hello!")); // → ltr console.log(dominantDirection("Hey, مساء الخير")); // → rtl إرشادات للحل قد يبدو حلك مثل النصف الأول من مثال textScripts، فعليك عدّ المحارف بمقياس مبني على characterScript، ثم ترشيح الجزء الذي يشير إلى المحارف غير المهمة (غير النصية). يمكن إيجاد الاتجاه الذي يحمل أعلى عدد من المحارف بواسطة reduce، فإذا لم يكن ذلك واضحًا، فارجع إلى المثال السابق في هذا المقال حيث استُخدِم reduce لإيجاد النص الذي فيه أكثر المحارف. ترجمة -بتصرف- للفصل الخامس من كتاب Elequent Javascript لصاحبه Marijn Haverbeke. اقرأ أيضًا الدوال في جافاسكريبت. التخاطب بين النوافذ في جافاسكريبت. القيم والأنواع والعوامل في جافاسكريبت

يحتار المطورون في اختيار أفضل إطار لمشاريعهم وسيكون هذا تحديًا حقيقيًا للمبتدئين في الأطر الحديثة. بعد العمل على الأطر الثلاثة (Django، Laravel و Rails – والذي يُعرف باسم Ruby On -rails)، سأقارن بين هذه الأطر الرائعة على أساس شعارها، سهولة تعلمها، أدائها، قوة وضعف مكتباتها وقوالبها، دعمها، آفاقها المستقبلية، فرص العمل، التكلفة والصيانة. ملاحظة: ينتقد بعض المعجبين عند التحدث عن نقاط ضعف أطرهم، ولا أستطيع فعل أي شيء لأنه لا يمكن إخفاء الحقيقة، كل إطار لديه بعض المزايا مع بعض العيوب. المقدمة لغة البرمجة أهم فرق بين هذه الأطر هي أن Django بلغة بايثون، Laravel بلغة PHP وRails بلغة الروبي، لذا إذا كنت تنوي استخدام أي من هذه الأطر فيجب عليك تعلم لغتها أولاً، وبسبب هذا، العديد من المطورين يختارون الإطار الذي يتطابق مع اللغة التي يعرفونها. إن التحول من لغة إلى أخرى ليس صعبًا بل يحتاج إلى بعض الوقت، وإذا احترت في اختيار لغة البرمجة، فهذه مقارنة بين لغات بايثون و PHP وروبي. الشعار جميع هذه الأطر من نوع MVC وشعارها ‘لا تكرر نفسك’ أي تدعم إعادة الاستخدام وقابلية النقل، وجميعها مشاريع مجانية ومفتوحة المصدر. المواقع بعض المواقع المعروفة تستخدم Django مثل Pinterest، Instagram، Mozilla، The Washington Times، Disqus، the Public Broadcasting Service و Bitbucket. في حين أن Laravel هو إطار جديد، حيث صدر في يونيو عام 2011، لكنه أصبح مشهورا جدا، ومن بين المواقع التي تستخدمه هي Deltanet Travel، Sublimity، Neighborhood Lender، Sendity و MyRank. يعتبر Rails من الأطر الرائعة فمن المواقع التي تستخدمه Twitter، Shopify، SoundCloud، Heroku، Github، Bloomberg و Hulu. سهولة التعلم على الرغم من أن الأطر الثلاثة لديها مجتمعات كبيرة وتوثيق رسمي، إلا أن تعلم Django وLaravel أسهل بكثير من تعلم Rails، فالتوثيق الحالي ل Django يجعلها الأسهل، وإذا كنت تملك خلفية PHP فيمكنك تعلم Laravel في غضون أسبوعين أو ثلاثة أسابيع، وهذه هي الوثائق الرسمية: وثائق Django ووثائق Laravel وثائق Rails. الأداء الأمن جميع هذه الأطر آمنة جدا إذا لم يرتكب المبرمج أخطاء، فيمتلك Django برمجيات وسيطة ويمتلك Rails Active Records وأما Laravel فيمتلك برمجيات HTTP وسيطة، وتوفر كل هذه الأطر رموز csrf للنماذج. لا يوجد فرق أمني كبير بين هذه الأطر، وكل هذا يعتمد على خبرة المبرمج. تحديث:أشار بعض القراء أن المبرمجين هم بشر وسيخطئون، لذا سأقول في هذه الحالة أن Django هو الأكثر أمانا وLaravel هو الأقل أمانًا، اطلع على هذا التوثيق عن أمن Django وهذا دليل أمن Rails و هذا دليل أمن Laravel، وسأقول أيضا أنه لا يوجد إطار آمن بشكل كامل لأن المطورين هم أيضا بشر، ويمكنك زيادة الأمن لكنك لا تستطيع جعله آمن بنسبة 100%، لكن إذا كتبت التعليمات البرمجية بعناية وحذر فإن جميع الأطر متساوية من ناحية الأمن. السرعة جميع الأطر مكتوبة بشكل صحيح، لذلك سرعتها تعتمد على اللغة البرمجة المستخدمة، فDjango هو الأسرع بسبب البايثون و Laravel هي الأبطأ بسبب PHP. الوقت المطلوب لإنشاء تطبيق إذا كنت تفهم الإطار بشكل كامل فإن إنشاء تطبيق Rails هو الأسرع لأنه يوفر لك الكثير من الاختصارات وبهذا ستكتب أقل عدد من الأسطر البرمجية. ومن جهة أخرى، Laravel هو الأبطأ ولا يوفر مكتبة قوية. إذا كان المشروع معقد فإن الفرق الزمني بين تطبيقات Django وRails سيكون صغيرًا بسبب صياغة بايثون المريحة للمتابعة وأقل أرباك، أما بالنسبة لـ Laravel فيجب عليك كتابة الكثير من الأسطر البرمجية وهذا قد يسبب لك بعض الإرباك وسترتفع نسبة الأخطاء. قوة وضعف المكتبة الأشياء المشتركة في جميع الأطر: جميعها MVC (يسمى Django MTV أيضا لكن على الرغم من أن الاسم مختلف إلا أن المفهوم هو نفسه). تركز جميع الأطر على قابلية القراءة وبساطة الشيفرة البرمجية وتوزيع الملفات. جميعها تستعلم تلقائيًا من قاعدة البيانات، فلا يجب عليك كتابة استعلامات قاعدة البيانات بشكل مباشر. تبنى الجداول تلقائيا في قاعدة البيانات من النماذج (models). جميع الأطر تملك نظام توجيه سهل وآمن، وتعرض صفحات الويب بشكل حيوي. تملك جميعها أنظمة قوالب خاصة بها وكل نظام قوالب غني بالمرشحات والدوال المعرّفة مسبقًا، الفرق الوحيد في الصياغة. جميعها مرنة ومحمولة مع تقنيات حديثة أخرى. Django يمتلك Django مكتبة قوية مع المميزات التالية: يعتبر قسم الإدارة المدمجة، المزخرف (decorator)، وأصناف المناظر نقاط قوة ل Django. الاستمارات المولدة تلقائيا للنماذج مع عملية التحقيق تجعلها سهلة للغاية. يدعم الإطار خاصية التخزين المؤقت وستتمكن من استخدام أي من أساليب التخزين المؤقت المتاحة. يدعم الأصناف البرمجيات الوسطيّة والتي يمكن أن تتدخّل في مراحل مختلفة من معالجة الطلب وتُنفّذ دوال مخصصة. يسمح لك نظام مرسل (dispatcher) داخلي لمكونات التطبيق اتصال الأحداث مع بعضها البعض عبر إشارات محددة مسبقا. يملك نظام تدويل يتضمن ترجمات لمكونات Django إلى لغات مختلفة. يملك نظام تسلسل الذي يمكنك من إنتاج وقراءة تمثيل XML و/أو JSON لمثيلات نموذج Django. واجهة بايثون مدمجة في إطار اختبار الوحدة. نظام مصادقة (authentication) موسّع. واجهة إدارة حيوية. أدوات لتوليد RSS وتغذيات (feed) خلاصات Atom. إطار مواقع تسمح ل Django واحد بتشغيل مواقع متعددة، ولكل منها المحتوى والتطبيقات الخاصة به. يملك أدوات لتوليد Google Sitemap. يملك تقنيات مدمجة للتخفيف من التزوير عبر الموقع، ثغرات XSS، ثغرات حقن SQL، تكسير كلمات المرور وهجمات الويب النموذجية، ومعظمها يعمل افتراضيا. إطار لإنشاء تطبيقات GIS. Laravel على الرغم من أن مكتبات Laravel ليست قوية مثل Django وRails إلا أنها كافية لإنشاء أي نوع من المواقع. يوفر Bundles و composer عدد من حزم نظام وحدات التحزيم والاعتماديات. التوجيه (Routing) – يوّفر طريقة سهلة وبسيطة لإدارة وتوجيه الروابط إلى متحكم أو دالة تُنفَّذ عند زيارة رابط محدَّد. دعم Eloquent ORM – خدمة أخرى مقدمة لتجريد وأتمتة جزء النموذج، حيث سنطبق التقنيات المتعارف عليها على الإعدادات. التهجيرات – طريقة لإصدار سكربتات قواعد البيانات بطريقة أنيقة للغاية، فلا حاجة للحفاظ على جميع التحققات على التهجيرات، يمكن لفريق عمل المشروع سحب الهجرة المقدمة وستعيّن جميعها وستكون جاهزة للعمل. إدارة قائمة الانتظار (Queue management) – لتجريد المهام غير الضرورية ووضعهم في قائمة الانتظار وجعل وقت استجابة المستخدم أسرع بكثير. دعم Redis، ويمكن توسيعها إلى memcached. حقن الإعتماديّة – اختبار سهل وأتمتة تحميل الإعتماديّة. Artisan – لإنشاء تطبيقات سطر الأوامر في لحظة. تعلم استخدام Laravel عن طريق هذه الدروس. Rails يتضمن Rails أدوات لجعل مهام التطوير الشائعة أسهل (خارج الصندوق)، مثل scaffolding الذي يستطيع إنشاء بعض النماذج تلقائيًا والمناظر اللازمة لموقع ويب الأساسي، بالإضافة إلى WEBrick وهو خادم ويب روبي بسيط الموزع مع روبي و Rake والذي هو نظام بناء موزع كـ gem. وتوفر هذه الأدوات جنبا إلى جنب مع Rails بيئة تطوير أساسية. Active record: يلعب دورا رئيسيا في تطبيقات Rails، وهو أفضل من Eloquent ORM في Laravel ومن النماذج في Django. اختصارات: يعبر الكثير من الناس الذين يأتون من لغات برمجة أو إطارات أخرى أن هذا الإطار سحري بسبب الاختصارات الكثيرة، فأغلب الأشياء معرّفة مسبقًا ويجب عليك كتابة بعض الأسطر البرمجية لإنشاء تطبيقات معقدة. التوجيه التلقائي: بعض الدوال الشائع في جدول قاعدة البيانات مثل الإنشاء ، التعديل والعرض مُعرّفة تلقائيًا، وهذا يعني أننا لا نحتاج إلى تضييع الوقت في المهام البسيطة ويمكننا قضاء وقت أطول على الأجزاء المعقدة من المشروع. سطر الأوامر: الكثير من الأشياء يمكن إنجازها عن طريق سطر الأوامر مثل استخدام rake وهي Ruby Make، أداة روبي مستقلة تستبدل أداة يونكس 'make' وتستخدم 'Rakefile' وملفات .rake لبناء قائمة مهام. في Rails، يُستخدم Rake لمهام الإدارة الشائعة، خاصة المعقدة منها التي تبني من بعضها البعض. تحتوي وحدة ActiveModelHelper على أساليب المساعدة لإنشاء النماذج من الكائنات بسرعة التي تتبع اتفاقيات Active Model، بداية من Active Record. خدمات الاستضافة يمكنك تشغيل أي تطبيق على VPS أو على خدمة استضافة مخصصة، وهذه مجموعة من الروابط لمواقع تسمح لك باستضافة مشروعك مجانا أو على خطط الاستضافة المشتركة. Django: بعض من المواقع التي تستضيف مشاريع Django هي: WebFaction، PythonAnywhere ، Heroku ، Digital Ocean ، Bulehost ، Dreamhost ، Arvixe و Google App Engine. Laravel: يمكنك الاستضافة على Heroku ، Bulehost ، Inmotion Hosting ، Site5 ، Dreamhost ، Digital Ocean و Arvixe. Rails: مواقع لتطبيقات Rails هي: Heroku ، Bulehost ، Dreamhost ، Arvixe ، Hosting24 و Digital Ocean. معايير أخرى كل هذه الأطر جيّدة في المستقبل، ففرص العمل، التكلفة والصيانة هي تقريبا نفسها ويمتاز Rails على Django وLaravel في شروط العمل، على الرغم من سرعة نمو Laravel. خاتمة يمكنك أن تختار أي واحدة من هذه الأطر حسب لغة البرمجة والخبرة، وإذا كنت هنا لتقرر أي واحدة يجب عليك تعلمها فأنا أفضل Rails، فعلى الرغم من صعوبة تعلمها إلا أنها مريحة أثناء إنشاء التطبيقات، إذا أردت أشياء سهلة مع الكثير من المميزات فاختر Django، فصياغة بايثون ونماذجه تجعله خيار جيدا، وعلى الرغم من أن تعلم Django قد يستغرق بعض الوقت إلا أنه ليس أصعب من Rails.إذا كانت لدي خبرة في PHP أو إذا أردت التعلم بسرعة فاختر Laravel. ترجمة -وبتصرّف- للمقال Django vs Laravel vs Rails لصاحبه Harish Kumar