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

سنتناول في التمارين التالية تنفيذاتٍ مختلفةً للواجهة Map، حيث يعتمدُ أحدها على الجدول hash table، والذي يُعدّ واحدًا من أفضل هياكل البيانات الموجودة، في حين يتشابه تنفيذٌ آخرُ مع الصنف TreeMap، ويُمكِّننا من المرور عبر العناصر بحسب ترتيبها، غير أنّه لا يتمتع بكفاءة الجداول.

ستكون لديك الفرصة لتنفيذ هياكل البيانات تلك وتحليل أدائها، وسنبدأ أولًا بتنفيذ بسيط للواجهة Map باستخدام قائمة من النوع List تتكوّن من أزواج مفاتيح/قيم key-value، ثم سننتقل إلى شرح الجداول.

تنفيذ الصنف MyLinearMap

سنُوفِّر كالمعتاد شيفرةً مبدئيةً، ومهمتك إكمال التوابع غير المكتملة. انظر إلى بداية تعريف الصنف MyLinearMap:

public class MyLinearMap<K, V> implements Map<K, V> {

    private List<Entry> entries = new ArrayList<Entry>();

يَستخدِم هذا الصنف معاملي نوع type parameters، حيث يشير المعامل الأول K إلى نوع المفاتيح، بينما يشير المعامل الثاني V إلى نوع القيم. ونظرًا لأن الصنف MyLinearMap يُنفِّذ الواجهة Map، فإن عليه أن يُوفِّر التوابع الموجودة في تلك الواجهة.

تحتوي كائنات النوع MyLinearMap على متغير نسخةٍ instance variable وحيدٍ entries، وهو عبارة عن قائمة من النوع ArrayList مكوّنة من كائنات تنتمي إلى النوع Entry، حيث يحتوي كل كائن من النوع Entry على زوج مفتاح-قيمة. انظر فيما يلي إلى تعريف الصنف:

    public class Entry implements Map.Entry<K, V> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public K getKey() {
            return key;
        }
        @Override
        public V getValue() {
            return value;
        }
    }

لا تتعدى كائنات الصنف Entry كونها أكثر من مجرد حاوٍ لزوج مفتاح/قيمة، ويقع تعريف ذلك الصنف ضمن الصنف MyLinearList، ويَستخدِم نفس معاملات النوع K وV.

هذا هو كل ما ينبغي أن تعرفه لحل التمرين، ولذا سننتقل إليه الآن.

تمرين 7

ستجد ملفات شيفرة التمرين في المستودع:

MyLinearMap.java: يحتوي هذا الصنف على الشيفرة المبدئية للجزء الأول من التمرين.
MyLinearMapTest.java: يحتوي على اختبارات الواحدة unit tests للصنف MyLinearMap.

ستجد أيضًا ملف البناء build.xml في المستودع.

نفِّذ الأمر ant build لكي تُصرِّف ملفات الشيفرة، ثم نفِّذ الأمر ant MyLinearMapTest. ستجد أن بعض الاختبارات لم تنجح؛ والسبب هو أنه ما يزال عليك القيام ببعض العمل.

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

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

ينبغي أن ينجح الاختبار containsKey بعدما تنتهي من كتابة التابع put.

اقرأ توثيق التابع Map.get ثم نفِّذه، وشغِّل الاختبارات مرةً أخرى. بعد ذلك اقرأ توثيق التابع Map.remove، ثم نفِّذه.

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

تحليل الصنف MyLinearMap

سنُقدِّم حلًا للتمرين الوارد في الأعلى، ثم سنُحلِّل أداء التوابع الأساسية. انظر إلى تعريف التابعين findEntry وequals:

private Entry findEntry(Object target) {
    for (Entry entry: entries) {
        if (equals(target, entry.getKey())) {
            return entry;
        }
    }
    return null;
}

private boolean equals(Object target, Object obj) {
    if (target == null) {
        return obj == null;
    }
    return target.equals(obj);
}

قد يعتمد زمن تشغيل التابع equals على حجم target والمفاتيح، ولكنه لا يعتمد في العموم على عدد المُدْخَلات n، وعليه، يَستغرِق التابع equals زمنًا ثابتًا.

بالنسبة للتابع findEntry، ربما يحالفنا الحظ ونجد المفتاح الذي نبحث عنه في البداية، ولكن هذا ليس مضمونًا، ففي العموم، يتناسب عدد المُدْخَلات التي سنبحث فيها مع n، وعليه، يَستغرِق التابع findEntry زمنًا خطيًا.

تعتمد معظم التوابع الأساسية المُعرَّفة في الصنف MyLinearMap على التابع findEntry، بما في ذلك التوابع put وget وremove. انظر تعريف تلك التوابع:

public V put(K key, V value) {
    Entry entry = findEntry(key);
    if (entry == null) {
        entries.add(new Entry(key, value));
        return null;
    } else {
        V oldValue = entry.getValue();
        entry.setValue(value);
        return oldValue;
    }
}
public V get(Object key) {
    Entry entry = findEntry(key);
    if (entry == null) {
        return null;
    }
    return entry.getValue();
}
public V remove(Object key) {
    Entry entry = findEntry(key);
    if (entry == null) {
        return null;
    } else {
        V value = entry.getValue();
        entries.remove(entry);
        return value;
    }
}

بعدما يَستدعِي التابعُ put التابعَ findEntry، فإن كل شيءٍ آخرَ ضمنَه يستغرق زمنًا ثابتًا. لاحِظ أن entries هي عبارةٌ عن قائمةٍ من النوع ArrayList، وأن إضافة عنصر إلى نهاية قائمةٍ من ذلك النوع تستغرق زمنًا ثابتًا في المتوسط؛ فإذا كان المفتاح موجودًا بالفعل في الخريطة، فإننا لن نضطّر إلى إضافة مُدْخَلٍ جديدٍ، ولكننا في المقابل سنضطّر لاستدعاء التابعين entry.getValue وentry.setValue، وكلاهما يستغرق زمنًا ثابتًا. بناءً على ما سبق، يُعدّ التابع put خطيًا، ويَستغرِق التابع get زمنًا خطيًا لنفس السبب.

يُعدّ التابع remove أعقد نوعًا ما؛ فقد يضطّر التابع entries.remove إلى حذف العنصر من بداية أو وسط قائمةٍ من النوع ArrayList، وهو ما يستغرِق زمنًا خطيًا. والواقع أنّه ليس هناك مشكلة في ذلك، فما تزال محصلة عمليتين خطيتين عمليةً خطيّةً أيضًا.

نستخلص مما سبق أن جميع التوابع الأساسية ضمن ذلك الصنف خطية، ولهذا السبب أطلقنا عليه اسم MyLinearMap.

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

سنشرح كيف لذلك أن يكون ممكنًا في خطوتين:

بدلًا من أن نُخزِّن المُدْخَلات في قائمةٍ واحدةٍ كبيرةٍ من النوع List، سنقسِّمها على عدة قوائمَ قصيرةٍ، وسنَستخدِم شيفرة تعمية hash code - وسنشرح معناها في المقال التالي- لكل مفتاح؛ وذلك لتحديد القائمة التي سنَستخدِمها.
يُعَد استخدام عدة قوائمَ قصيرةٍ أسرعَ من اِستخدَام قائمةٍ واحدةٍ كبيرةٍ، ولكنه مع ذلك لا يُغيِّر ترتيب النمو order of growth -كما سنناقش لاحقًا-، فما تزال العمليات الأساسية خطيّةً، ولكن هنالك خدعة ستُمكِّننا من تجاوز ذلك، فإذا زِدنا عدد القوائم بحيث نُقيّد عدد المُدْخَلات الموجودة في كل قائمة، فسنحصل على خريطةٍ ذات زمنٍ ثابتٍ. سنناقش تفاصيل ذلك في تمرين المقال التالي، ولكن قبل أن نفعل ذلك سنشرح ما تعنيه التعمية hashing.

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

ترجمة -بتصرّف- للفصل Chapter 9: The Map interface من كتاب Think Data Structures: Algorithms and Information Retrieval in Java.