تحليل زمن تشغيل القوائم المنفذة باستخدام قائمة ازدواجية الترابط

سنراجع في هذه المقالة نتائج تمرين مقالة تحليل زمن تشغيل القوائم المُنفَّذة باستخدام قائمة مترابطة، ثم سنُقدِّم تنفيذًا آخرَ للواجهة List، وهو القائمة ازدواجية الترابط doubly-linked list.

نتائج تشخيص الأداء

اِستخدَمنا الصنف Profiler.java -في التمرين المشار إليه- لكي نُطبِّق عمليات الصنفين ArrayList وLinkedList على أحجام مختلفة من المشكلة، ثم عرضنا زمن التشغيل مقابل حجم المشكلة بمقياس لوغاريتمي-لوغاريتمي log-log، وقدّرنا ميل المنحني الناتج. يُوضِّح ذلك الميل العلاقة بين زمن التشغيل وحجم المشكلة.

فعلى سبيل المثال، عندما استخدمنا التابع add لإضافة عناصر إلى نهاية قائمة من النوع ArrayList، وجدنا أن الزمن الكلّي لتنفيذ عدد n من الإضافات يتناسب مع n، أي أن الميل المُقدَّر كان قريبًا من 1، وبناءً على ذلك استنتجنا أن تنفيذ عدد n من الإضافات ينتمي إلى المجموعة O(n)‎، وأن تنفيذَ إضافةٍ واحدةٍ يتطلَّب زمنًا ثابتًا في المتوسط، أي أنه ينتمي إلى المجموعة O(1)‎، وهو نفس ما توصلنا إليه باستخدام تحليل الخوارزميات.

كان المطلوب من ذلك التمرين هو إكمال متن التابع profileArrayListAddBeginning الذي يُشخِّص عملية إضافة عناصر جديدة إلى بداية قائمة من النوع ArrayList. وبناءً على تحليلنا للخوارزمية

Y، فقد توقّعنا أن يتطلَّب تنفيذ إضافة واحدة زمنًا خطيًا بسبب تحريك العناصر الأخرى إلى اليمين، وعليه توقَّعنا أن يتطلَّب تنفيذ عدد n من الإضافات زمنًا تربيعيًا.

انظر إلى حل التمرين الذي ستجده في مجلد الحل داخل مستودع الكتاب:

    public static void profileArrayListAddBeginning() {
        Timeable timeable = new Timeable() {
            List<String> list;

            public void setup(int n) {
                list = new ArrayList<String>();
            }

            public void timeMe(int n) {
                for (int i=0; i<n; i++) {
                    list.add(0, "a string");
                }
            }
        };
        int startN = 4000;
        int endMillis = 10000;
        runProfiler("ArrayList add beginning", timeable, startN, endMillis);
    }

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

انظر إلى النتائج (حجم المشكلة على اليسار وزمن التشغيل بوحدة الميلي ثانية على اليمين):

4000, 14
8000, 35
16000, 150
32000, 604
64000, 2518
128000, 11555

تَعرِض الصورة التالية رسمًا بيانيًا لزمن التشغيل مقابل حجم المشكلة.

لا يَعنِي ظهور خط مستقيم في هذا الرسم البياني أن الخوارزمية خطّيّة، وإنما يعني أنه إذا كان زمن التشغيل متناسبًا مع n^k‎ لأي أس k، فإنه من المتوقَّع أن نرى خطًّا مستقيمًا ميله يساوي k. نتوقَّع في هذا المثال أن يكون الزمنُ الكلّيّ لعدد n من الإضافات متناسبًا مع n²‎، وأن نحصل على خطٍّ مستقيمٍ بميلٍ يساوي 2، وفي الحقيقة يساوي الميل المُقدَّر 1.992 تقريبًا، وهو في الحقيقة دقيق جدًا لدرجةٍ تجعلنا لا نرغب في تزوير بيانات بهذه الجودة.

تشخيص توابع الصنف LinkedList

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

انظر شيفرة الحل:

    public static void profileLinkedListAddBeginning() {
        Timeable timeable = new Timeable() {
            List<String> list;

            public void setup(int n) {
                list = new LinkedList<String>();
            }

            public void timeMe(int n) {
                for (int i=0; i<n; i++) {
                    list.add(0, "a string");
                }
            }
        };
        int startN = 128000;
        int endMillis = 2000;
        runProfiler("LinkedList add beginning", timeable, startN, endMillis);
    }

اضطرّرنا إلى إجراء القليل من التعديلات، فعدّلنا الصنف ArrayList إلى الصنف LinkedList، كما ضبطنا قيمة المعاملين startN وendMillis لكي نحصل على قياسات مناسبة، فقد لاحظنا أن القياسات ليست بدقة القياسات السابقة. انظر إلى النتائج:

128000, 16
256000, 19
512000, 28
1024000, 77
2048000, 330
4096000, 892
8192000, 1047
16384000, 4755

لم نحصل على خط مستقيم تمامًا، وميل الخيط لا يساوي 1 بالضبط، وقد قدَّرت المربعات الدنيا least squares fit الميل بحوالي 1.23، ومع ذلك تشير تلك النتائج إلى أن الزمن الكلي لعدد n من الإضافات ينتمي إلى المجموعة O(n)‎ على الأقل، وبالتالي يتطلَّب تنفيذُ إضافةٍ واحدةٍ زمنًا ثابتًا.

الإضافة إلى نهاية قائمة من الصنف LinkedList

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

في الواقع هذا ليس صحيحًا، ويمكنك الاطلاع إلى الشيفرة التالية:

    public static void profileLinkedListAddEnd() {
        Timeable timeable = new Timeable() {
            List<String> list;

            public void setup(int n) {
                list = new LinkedList<String>();
            }

            public void timeMe(int n) {
                for (int i=0; i<n; i++) {
                    list.add("a string");
                }
            }
        };
        int startN = 64000;
        int endMillis = 1000;
        runProfiler("LinkedList add end", timeable, startN, endMillis);
    }

ها هي النتائج التي حصلنا عليها:

64000, 9
128000, 9
256000, 21
512000, 24
1024000, 78
2048000, 235
4096000, 851
8192000, 950
16384000, 6160

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

القوائم ازدواجية الترابط Doubly-linked list

الفكرة هي أن الصنف MyLinkedList الذي نفَّذناه يَستخدِم قائمة مترابطة أحادية، أي أن كل عنصرٍ يحتوي على رابطٍ واحدٍ إلى العنصر التالي، في حين يحتوي الكائن MyArrayList نفسه على رابط إلى العقدة الأولى.

في المقابل، إذا اطلعت على توثيق الصنف LinkedList باللغة الإنجليزية الذي تُوفِّره جافا، فإننا نجد ما يلي:

تنفيذ قائمة ازدواجية الترابط للواجهتين List وDeque. تَعمَل جميع العمليات بالشكل المُتوقَّع من قائمةٍ ازدواجية الترابط، أي تؤدي عمليات استرجاع فهرس معين إلى اجتياز عناصر القائمة من البداية أو من النهاية بناءً على أيهما أقرب لذلك الفهرس.

فيما يلي نذكر الفكرة العامّة عن القوائم ازدواجية الترابط، إذ فيها:

تحتوي كل عقدةٍ على رابطٍ إلى العقدة التالية ورابطٍ إلى العقدة السابقة.
تحتوي كائنات الصنف LinkedList على روابط إلى العنصر الأول والعنصر الأخير في القائمة.

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

يُلخِّص الجدول التالي الأداء المُتوقَّع من الصنف ArrayList والصنف المُخصَّص MyLinkedList الذي تحتوي عقده على رابط واحد والصنف LinkedList الذي تحتوي عقده على رابطين:

	MyArrayList	MyLinkedList	LinkedList
add (بالنهاية)	1	n	1
add (بالبداية)	n	1	1
add (في العموم)	n	n	n
get / set	1	n	n
indexOf / lastIndexOf	n	n	n
isEmpty / size	1	1	1
remove (من النهاية)	1	n	1
remove (من البداية)	n	1	1
remove (في العموم)	n	n	n

اختيار هيكل البيانات الأنسب

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

إذا كان زمن تشغيل التطبيق الخاص بك يعتمد على الزمن الذي تتطلَّبه عمليتا get وset، فقد يكون التنفيذ ArrayList هو الخيار الأفضل؛ أما إذا كان يَعتمِد على عملية إضافة العناصر وحذفها إلى بداية القائمة ونهايتها، فلربما التنفيذ LinkedList هو الخيار الأفضل.

ولكن تذكّر أن هذه التوصياتِ مبنيّةٌ على ترتيب النمو order of growth للأحجام الكبيرة من المشكلات. هنالك عوامل أخرى ينبغي أن تأخذها في الحسبان أيضًا:

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

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

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

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

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

ترجمة -بتصرّف- للفصل Chapter 5: Doubly-linked list من كتاب Think Data Structures: Algorithms and Information Retrieval in Java.