مدخل إلى تحليل الخوارزميات

كما رأينا في مقالة طريقة عمل الواجهات بلغة جافا، تُوفِّر جافا تنفيذين implementations للواجهة List، هما ArrayList وLinkedList، حيث يكون النوع LinkedList أسرع بالنسبة لبعض التطبيقات، بينما يكون النوع ArrayList أسرع بالنسبة لتطبيقاتٍ أخرى.

وإذا أردنا أن نُحدِّد أيهما أفضل للاستخدام في تطبيق معين، فيمكننا تجربة كلٍّ منهما على حدةٍ لنرى الزمن الذي سيَستغرِقه. يُطلَق على هذا الأسلوب اسم التشخيص profiling، ولكنّ له بعض الإشكاليّات:

أننا سنضطّر إلى تنفيذ الخوارزميتين كلتيهما لكي نتمكَّن من الموازنة بينهما.
قد تعتمد النتائج على نوع الحاسوب المُستخدَم، فقد تعمل خوارزمية معينة بكفاءةٍ عالية على حاسوب معين، في حين قد تَعمَل خوارزميةٌ أخرى بكفاءةٍ عاليةٍ على حاسوب مختلف.
قد تعتمد النتائج على حجم المشكلة أو البيانات المُدْخَلة.

يُمكِننا معالجة بعض هذه النقاط المُشكلةِ بالاستعانة بما يُعرَف باسم تحليل الخوارزميات، الذي يُمكِّننا من الموازنة بين عدة خوارزمياتٍ دون الحاجة إلى تنفيذها فعليًا، ولكننا سنضطّر عندئذٍ لوضع بعض الافتراضات:

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

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

يُمكِن تصنيف غالبية الخوارزميات البسيطة إلى إحدى التصنيفات التالية:

ذات زمن ثابت: تكون الخوارزمية ثابتة الزمن إذا لم يعتمد زمن تشغيلها على حجم المدخلات. على سبيل المثال، إذا كان لدينا مصفوفةٌ مكوَّنةٌ من عدد n من العناصر، واستخدمنا العامل [] لقراءة أيٍّ من عناصرها، فإن ذلك يتطلَّب نفس عدد العمليات بغضّ النظر عن حجم المصفوفة.
ذات زمن خطّي: تكون الخوارزمية خطيّةً إذا تناسب زمن تشغيلها مع حجم المدخلات. فإذا كنا نحسب حاصل مجموع العناصر الموجودة ضمن مصفوفة مثلًا، فعلينا أن نسترجع قيمة عدد n من العناصر، وأن نُنفِّذ عدد n-1 من عمليات الجمع، وبالتالي يكون العدد الكليّ للعمليات (الاسترجاع والجمع) هو 2‎*‎n-1، وهو عددٌ يتناسب مع n.
ذات زمن تربيعي: تكون الخوارزمية خطيةً إذا تناسب زمن تشغيلها مع n²‎. على سبيل المثال، إذا كنا نريد أن نفحص ما إذا كان هنالك أيُّ عنصرٍ ضمن قائمةٍ معينةٍ مُكرَّرًا، فإن بإمكان خوارزميةٍ بسيطةٍ أن توازن كل عنصرٍ ضمن القائمة بجميع العناصر الأخرى، وذلك نظرًا لوجود عدد n من العناصر، والتي لا بُدّ من موازنة كُلٍّ منها مع عدد n-1 من العناصر الأخرى، يكون العدد الكليّ لعمليات الموازنة هو n²-n، وهو عددٌ يتناسب مع n²‎.

الترتيب الانتقائي Selection sort

تُنفِّذ الشيفرة المثال التالية خوارزميةً بسيطةً تُعرَف باسم الترتيب الانتقائي:

public class SelectionSort {

    /**
     * بدل العنصرين الموجودين بالفهرس‫ i والفهرس j
     */
    public static void swapElements(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * ‫اعثر على فهرس أصغر عنصر بدءًا من الفهرس المُمرَّر 
     * عبر المعامل‫ index وحتى نهاية المصفوفة
     */
    public static int indexLowest(int[] array, int start) {
        int lowIndex = start;
        for (int i = start; i < array.length; i++) {
            if (array[i] < array[lowIndex]) {
                lowIndex = i;
            }
        }
        return lowIndex;
    }

    /**
     * رتب المصفوفة باستخدام خوارزمية الترتيب الانتقائي
     */
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int j = indexLowest(array, i);
            swapElements(array, i, j);
        }
    }
}

يُبدِّل التابع الأول swapElements عنصرين ضمن المصفوفة، وتَستغرِق عمليتا قراءة العناصر وكتابتها زمنًا ثابتًا؛ لأننا لو عَرَفنا حجم العناصر وموضع العنصر الأول ضمن المصفوفة، فسيكون بإمكاننا حساب موضع أي عنصرٍ آخرَ باستخدام عمليتي ضربٍ وجمعٍ فقط، وكلتاهما من العمليات التي تَستغرِق زمنًا ثابتًا. ولمّا كانت جميع العمليات ضمن التابع swapElements تَستغرِق زمنًا ثابتًا، فإن التابع بالكامل يَستغرِق بدوره زمنًا ثابتًا.

يبحثُ التابع الثاني indexLowest عن فهرسِ index أصغرِ عنصرٍ في المصفوفة بدءًا من فهرسٍ معينٍ يُخصِّصه المعامل start، ويقرأ كل تكرارٍ ضمن الحلقة التكراريّة عنصرين من المصفوفة ويُوازن بينهما، ونظرًا لأن كل تلك العمليات تستغرِق زمنًا ثابتًا، فلا يَهُمّ أيُها نَعُدّ. ونحن هنا بهدف التبسيط سنحسب عدد عمليات الموازنة:

إذا كان start يُساوِي الصفر، فسيَمُرّ التابع indexLowest عبر المصفوفة بالكامل، وبالتالي يكون عدد عمليات الموازنة المُجراة مُساويًا لعدد عناصر المصفوفة، وليكن n.
إذا كان start يُساوِي 1، فإن عدد عمليات الموازنة يُساوِي n-1.
في العموم، يكون عدد عمليات الموازنة مساويًا لقيمة n-start، وبالتالي، يَستغرِق التابع indexLowest زمنًا خطّيًا.

يُرتِّب التابع الثالث selectionSort المصفوفة. ويُنفِّذ التابع حلقة تكرار من 0 إلى n-1، أي يُنفذِّ الحلقة عدد n من المرات. وفي كل مرة يَستدعِي خلالها التابع indexLowest، ثم يُنفِّذ العملية swapElements التي تَستغرِق زمنًا ثابتًا.

عند استدعاء التابع indexLowest لأوّلِ مرة، فإنه يُنفِّذ عددًا من عمليات الموازنة مقداره n، وعند استدعائه للمرة الثانية، فإنه يُنفِّذ عددًا من عمليات الموازنة مقداره n-1، وهكذا. وبالتالي سيكون العدد الإجمالي لعمليات الموازنة هو:

n + n-1 + n-2 + ... + 1 + 0

يبلُغ مجموع تلك السلسلة مقدارًا يُساوِي n(n+1)/2، وهو مقدارٌ يتناسب مع n²‎، مما يَعنِي أن التابع selectionSort يقع تحت التصنيف التربيعي.

يُمكِننا الوصول إلى نفس النتيجة بطريقة أخرى، وهي أن ننظر للتابع indexLowest كما لو كان حلقة تكرارٍ متداخلةً nested، ففي كل مرة نَستدعِي خلالها التابع indexLowest، فإنه يُنفِّذ مجموعةً من العمليات يكون عددها متناسبًا مع n، ونظرًا لأننا نَستدعيه عددًا من المرات مقداره n، فإن العدد الكليّ للعمليات يكون متناسبًا مع n²‎.

ترميز Big O

تنتمي جميع الخوارزميات التي تَستغرِق زمنًا ثابتًا إلى مجموعةٍ يُطلَق عليها اسم O(1)‎، فإذا قلنا إن خوارزميةً معينةً تنتمي إلى المجموعة O(1)‎، فهذا يعني ضمنيًّا أنها تستغرِق زمنًا ثابتًا. وعلى نفس المنوال، تنتمي جميع الخوارزميات الخطيّة -التي تستغرِق زمنًا خطيًا- إلى المجموعة O(n)‎، بينما تنتمي جميع الخوارزميات التربيعية إلى المجموعة O(n²‎)‎. تطلَق على تصنيف الخوارزميات بهذا الأسلوب تسمية ترميز Big O.

اقتباس

ملحوظة. لقد عرَّفنا هنا ترميز big O تعريفًا عارضًا، ولكن لو أردت التعمّق في الجزء الرياضيّ منه فبإمكانك الاطلاع على ما هو ترميز Big O .

يُوفِّر هذا الترميز أسلوبًا سهلًا لكتابة القواعد العامة التي تسلُكها الخوارزميات في العموم. فلو نفَّذنا خوارزميةً خطيةً وتبعناها بخوارزميةٍ ثابتة الزمن على سبيل المثال، ، فإن زمن التشغيل الإجمالي يكون خطيًا. وننبّه هنا إلى أنّ ‎∈‎ تَعنِي "ينتمي إلى":

If f ∈ O(n) and g ∈ O(1), f+g ∈ O(n)

إذا أجرينا عمليتين خطيتين، فسيكون المجموع الإجمالي خطيًا:

If f ∈ O(n) and g ∈ O(n), f+g ∈ O(n)

في الحقيقة، إذا أجرينا عمليةً خطيّةً أي عددٍ من المرات، وليكن k، فإن المجموع الإجمالي سيبقى خطيًا طالما أن k قيمة ثابتة لا تعتمد على n:

If f ∈ O(n) and k is constant, kf ∈ O(n)

في المقابل، إذا أجرينا عمليةً خطيةً عدد n من المرات، فستكون النتيجة تربيعيةً:

If f ∈ O(n), nf ∈ O(n^2)

وفي العموم، ما يهمنا هو أكبر أسٍّ للأساس n، فإذا كان العدد الكليّ للعمليات يُساوِي 2n+1، فإنه إجمالًا ينتمي إلى O(n)‎، ولا أهمية للثابت 2 ولا للقيمة المضافة 1 في هذا النوع من تحليل الخوارزميات. وبالمثل، ينتمي n²+100n+1000 إلى O( n²)‎. ولا أهمّية للأرقام الكبيرة التي تراها.

يُعدّ ترتيب النمو Order of growth طريقةً أخرى للتعبير عن نفس الفكرة، ويشير ترتيبُ نموٍّ معين إلى مجموعة الخوارزميات التي ينتمي زمن تشغيلها إلى نفس تصنيف ترميز big O، حيث تنتمي جميع الخوارزميات الخطية مثلًا إلى نفس ترتيب النمو؛ وذلك لأن زمن تشغيلها ينتمي إلى المجموعة O(n)‎.

ويُقصَد بكلمة "ترتيب" ضمن هذا السياق "مجموعة"، مثل اِستخدَامنا لتلك الكلمة في عبارةٍ مثل "ترتيب فرسان المائدة المستديرة". ويُقصَد بهذا أنهم مجموعة من الفرسان، وليس طريقة صفّهم أو ترتيبهم، أي يُمكِنك أن تنظر إلى ترتيب الخوارزميات الخطية وكأنها مجموعة من الخوارزميات التي تتمتّع بكفاءةٍ عالية.

تمرين 2

يشتمل التمرين التالي على تنفيذ الواجهة List باستخدام مصفوفةٍ لتخزين عناصر القائمة.

ستجد الملفات التالية في مستودع الشيفرة الخاص بالكتاب -انظر القسم 0.1-:

MyArrayList.java : يحتوي على تنفيذ جزئي للواجهة List، فهناك أربعةُ توابعَ غير مكتملة عليك أن تكمل كتابة شيفرتها.
MyArrayListTest.java: يحتوي على مجموعة من اختبارات JUnit، والتي يُمكِنك أن تَستخدِمها للتحقق من صحة عملك.

كما ستجد الملف build.xml. يُمكِنك أن تُنفِّذ الأمر ant MyArrayList؛ لكي تتمكَّن من تشغيل الصنف MyArrayList.java وأنت ما تزال في المجلد code الذي يحتوي على عدة اختباراتٍ بسيطة. ويُمكِنك بدلًا من ذلك أن تُنفِّذ الأمر ant MyArrayListTest لكي تُشغِّل اختباراتِ JUnit.

عندما تُشغِّل تلك الاختبارات فسيفشل بعضها، والسبب هو وجود توابع ينبغي عليك إكمالها. إذا نظرت إلى الشيفرة، فستجد 4 تعليقات TODO تشير إلى هذه موضع كل من هذه التوابع.

ولكن قبل أن تبدأ في إكمال تلك التوابع، دعنا نلق نظرةً سريعةً على بعض أجزاء الشيفرة. تحتوي الشيفرة التالية على تعريف الصنف ومتغيراتِ النُّسَخ instance variables وباني الصنف constructor:

public class MyArrayList<E> implements List<E> {
    int size;                    // احتفظ بعدد العناصر
    private E[] array;           // خزِّن العناصر

    public MyArrayList() {
        array = (E[]) new Object[10];
        size = 0;
    }
}

يحتفظ المتغير size -كما يُوضِّح التعليق- بعدد العناصر التي يَحمِلها كائنٌ من النوع MyArrayList، بينما يُمثِل المتغير array المصفوفة التي تحتوي على تلك العناصر ذاتها.

يُنشِئ الباني مصفوفةً مكوَّنةً من عشرة عناصر تَحمِل مبدئيًّا القيمة الفارغة null، كما يَضبُط قيمة المتغير size إلى 0. غالبًا ما يكون طول المصفوفة أكبر من قيمة المتغير size، مما يَعنِي وجود أماكنَ غير مُستخدَمةٍ في المصفوفة.

اقتباس

ملحوظة متعلقة بقواعد لغة جافا: لا يُمكِنك إنشاء مصفوفة باستخدام معامل نوع type parameter، وهكذا فالتعليمة التالية مثلًا لن تَعمَل:

        array = new E[10];

لكي تتمكَّن من تخطِي تلك العقبة، عليك أن تُنشِئ مصفوفةً من النوع Object، ثم تُحوِّل نوعها typecast. يُمكِنك قراءة المزيد عن ذلك في ما المقصود بالأنواع المعمّمة (باللغة الإنجليزية).

ولنُلقِ نظرةً الآن على التابع المسؤول عن إضافة العناصر إلى القائمة:

    public boolean add(E element) {
        if (size >= array.length) {
            // أنشئ مصفوفة أكبر وانسخ إليها العناصر
            E[] bigger = (E[]) new Object[array.length * 2];
            System.arraycopy(array, 0, bigger, 0, array.length);
            array = bigger;
        } 
        array[size] = element;
        size++;
        return true;
    }

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

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

في الأخير، لنُلقِ نظرةً على التابع get، وبعدها يُمكِنك البدء في حل التمرين:

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return array[index];
    }

كما نرى، فالتابع get بسيطٌ للغاية ويعمل كما يلي: إذا كان الفهرس المطلوب خارج نطاق المصفوفة، فسيُبلِّغ التابع عن اعتراض exception؛ أما إذا ضمن نطاق المصفوفة، فإن التابع يسترجع عنصر المصفوفة ويعيده. لاحِظ أن التابع يَفحَص ما إذا كانت قيمة الفهرس أقل من قيمة size لا قيمة array.length، وبالتالي لا يعيد التابع قيم عناصر المصفوفة غير المُستخدَمة.

ستجد التابع set في الملف MyArrayList.java على النحو التالي:

    public T set(int index, T element) {
        // TODO: fill in this method.
        return null;
    }

اقرأ توثيق set باللغة الإنجليزية، ثم أكمل متن التابع. لا بُدّ أن ينجح الاختبار testSet عندما تُشغِّل MyArrayListTest مرةً أخرى.

اقتباس

ملحوظة: تجنَّب تكرار الشيفرة المسؤولة عن فحص الفهرس.

الخطوة التالية هي إكمال التابع indexOf. وقد وفَّرنا لك أيضًا التابع المساعد equals للموازنة بين قيمة عنصر ضمن المصفوفة وبين قيمة معينة أخرى. يعيد ذلك التابع القيمة true إذا كانت القيمتان متساويتين كما يُعالِج القيمة الفارغة null بشكل سليم. لاحِظ أن هذا التابع مُعرَّف باستخدام المُعدِّل private؛ لأنه ليس جزءًا من الواجهة List، ويُستخدَم فقط داخل الصنف.

شغِّل الاختبار MyArrayListTest مرة أخرى عندما تنتهي، والآن ينبغي أن ينجح الاختبار testIndexOf وكذلك الاختبارات الأخرى التي تعتمد عليه.

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

مثلما سبق، اقرأ التوثيق باللغة الإنجليزية أولًا ثم نفِّذ التابع، بعدها شغِّل الاختبارات لكي تتأكّد من أنك تنفيذك سليم.

اقتباس

ملحوظة: تجنَّب تكرار الشيفرة المسؤولة عن زيادة/إعادة ضبط حجم المصفوفة.

لننتقل الآن إلى التابع الأخير. أكمل متن التابع remove وعندما تنتهي من إكمال هذا التابع، فالمتوقع أن تنجح جميع الاختبارات. وبعد أن تُنهِي جميع التوابع وتتأكَّد من أنها تَعمَل بكفاءة، يُمكِنك الاطلاع على الشيفرة.

ترجمة -بتصرّف- للفصل Chapter 2: Analysis of Algorithms من كتاب Think Data Structures: Algorithms and Information Retrieval in Java.