Python/heapq

تقدّم هذه الوحدة وسيلة لاستخدام خوارزمية طابور الكومة heap queue والتي تعرف كذلك بخوارزمية طابور الأولوية priority queue.

الكومات Heaps هي مشجّرات ثنائية binary trees تمتلك كل عقدة أبوية parent node فيها قيمة تكون أصغر من أو مساوية لأي قيمة أخرى في العقد البنوية children.

تستخدم الوحدة مصفوفات تكون فيها heap[k] <= heap[2*k+1]‎ و heap[k] <= heap[2*k+2]‎ لجميع قيم k، ويبدأ عدّ العناصر من الصفر. ولغرض المقارنة، تُعدّ العناصر غير الموجودة ما لا نهائية. أما أهمّ خصائص الكومة هي أنّ أصغر عنصر فيها هو الجذر دائمًا، ويعبر عنه heap[0]‎.

جدير بالذكر أنّ الواجهة البرمجية الخاصة بهذه الوحدة تختلف عن خوارزميات الكومة التي ترد في الكتب الدراسية من ناحيتين:

أ - تستخدم هذه الوحدة فهرسة تبدأ من الصفر، وهذا يجعل العلاقة بين الفهرس الخاص بعقدة وفهارس العقد المتفرّعة عنها أقل وضوحًا ولكنّها أكثل ملائمة؛ وذلك لأنّ لغة بايثون تعتمد عملية الفهرسة التي تبدأ من الصفر.

ب - تعيد الدالة pop()‎ في هذه الوحدة العنصر الأصغر وليس الأكبر (يسمى في الكتب الدراسية "min-heap"، والشائع هو استخدام "max heap" في الكتب الدراسية لأنّه أكثر ملائمة لعمليات الفرز الموقعية).

يتيح وجها الاختلاف هذان على النظر إلى الكومة على أنّها قائمة بايثون عادية دون أي مفاجئات: فالتعبير heap[0]‎ يمثّل أصغر عنصر، ويحافظ التعبير heap.sort()‎ على الكومة ثابتة.

يمكن إنشاء الكومة إمّا عن طريق استخدام قائمة تأخذ القيمة الأولية []، أو يمكن تحويل قائمة ذات عناصر إلى كومة باستخدام الدالة heapify()‎.

دوال الوحدة heapq

تقدّم وحدة heapq الدوال التالية:

الدالة heappush()‎

تدرج الدالة القيمة المعطاة في الكومة، مع الحفاظ على ثبات الكومة.

الدالة heappop()‎

تحذف الدالة وتعيد أصغر عنصر في الكومة، مع الحفاظ على ثبات الكومة.

الدالة heappushpop()‎

تضيف الدالة العنصر المعطى إلى الكومة، ثم تحذف وتعيد أصغر عنصر في الكومة.

الدالة heapify()‎

تحوّل الدالة القائمة المعطاة إلى كومة، في نفس المكان، وفي زمن خطي linear time.

الدالة heapreplace()‎

تحذف الدالة وتعيد أصغر عنصر في الكومة، وتضيف كذلك العنصر الجديد المعطى.

دوال ذات استخدامات عامة

تقدّم هذه الوحدة كذلك ثلاث دوال ذات استخدامات عامة:

الدالة heapmerge()‎

تدمج الدالة عدة مدخلات مفروزة في مخرج مفرد مفروز.

الدالة nlargest()‎

تعيد الدالة قائمة تضمّ n من أكبر العناصر في مجموعة البيانات dataset المعرّفة بواسطة المكرَّرات.

الدالة nsmallest()‎

تعيد الدالة قائمة تضمّ n من أصغر العناصر في مجموعة البيانات dataset المعرّفة بواسطة المكرَّرات.

أمثلة بسيطة

يمكن إنجاز عملية heapsort عن طريق دفع كل القيم إلى الكومة ثم حذف القيمة الصغرى في كل مرة:

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

هذه العملية مشابهة للتعبير sorted(iterable)‎ ولكنّها ليس مستقرّة مثلها. يمكن لعناصر الكومة أن تكون صفوفًا، ويفيد هذا في إسناد قيم المقارنة (مثل أولويات المهام) إلى جانب العنصر الرئيسي الذي يجري تعقبه:

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

ملاحظات على خوارزمية طابور ألأولوية

طابور الأولوية هو من الاستخدامات الشائعة للكومات، ولكن استخدام هذه الخوارزمية ينطوي على عدد من التحديات:

• استقرارية عملية الفرز: كيف يمكن الحصول على مهمّتين لهما نفس الأولوية وتعادان بنفس ترتيب إضافتها؟
• المقارنة الصفية Tuple comparison للأزواج (priority, task) غير صالحة إن كانت الألولويات متساوية، وكانت المهام لا تمتلك ترتيب مقارنة افتراضي.
• إن حدث تغيير في أولوية إحدى المهمّات، فكيف يمكن حينئذ نقل المهمّة إلى الموقع الجديد في الكومة؟
• أو إن كان يجب حذف إحدى المهمّات المعلّقة pending، فكيف يمكن العثور على تلك المهمّة وحذفها من الطابور؟

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

هناك حل آخر لمشكلة عدم القدرة على مقارنة المهمّام وتتلخّص في إنشاء صنف تغليف wrapper class يتجاهل المهمّة ويقارن الأولويات فقط:

‎from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

تتمحور بقية المشاكل حول العثور على المهامّ المعلقة وتغيير أولويتها أو حذفها من الكومة نهائيًا. يمكن العثور على مهمّة معينة بواسطة قاموس يشير إلى عنصر معين في الكومة. ولكن حذف العنصر أو تغيير أولويته لا يخلو من صعوبة؛ ذلك لأنّه قد يؤدي إلى إفساد بنية الكومة الثابتة. من الحلول المحتملة لهذه المشكلة هو تعليم العنصر على أنّه عنصر محذوف وإضافة عنصر جديد يمتلك الأولوية المعدّلة:

pq = []                         # قائمة بالعناصر المرتّبة في الكومة
entry_finder = {}               # ربط المهام بالعناصر
REMOVED = '<removed-task>'      # عنصر يحلّ محل المهمّة المحذوفة
counter = itertools.count()     # تعداد تسلسل فريد

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

النظرية

الكومات هي مصفوفات يكون فيها a[k] <= a[2*k+1]‎ و a[k] <= a[2*k+2]‎ لجميع قيم k ويبدأ عدّ العناصر من 0. 

ولغرض المقارنة، تُعدّ العناصر غير الموجودة ما لا نهائية. أما أهمّ خصائص الكومة هو أنّ أصغر عنصر فيها هو الجذر دائمًا، ويعبر عنه heap[0]‎.

الهدف من الثابت غير المعروف أعلاه هو إيجاد تمثيل لدوري رياضي لا يستهلك الكثير من الذاكرة. الأرقام أدناه هي قيم k وليست a[k]‎:

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

يلاحظ أنّ كل رقم k في المشجّر أعلاه يعلو رقمين هما 2‎*k+1‎ و ‎2*k+2.

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

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

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

ومن الواضح أنّ هذه العملية تتناسب تناسبًا لوغاريتميًا مع عدد العناصر الكلي في المخطط، وسنحصل على عملية فرز بسرعة O(n log n)‎ عن طريق المرور على جميع العناصر في المخطط.

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

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

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

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

ولكن هناك العديد من طريق التمثيل التي قد تكون أكثر فعالية بصورة عامة، ولكنّها قد تعاني من مشاكل كبيرة للغاية.

الكومات مفيدة كذلك في عمليات الفرز التي تجرى في الأقراص الكبيرة. تتضمّن عمليات الفرز هذه إنتاج جولات runs (وهي تسلسلات مفروزة مسبقًا، ويكون حجمها مرتبطًا عادةً بمقدار ذاكرة المعالج) تتبعها عمليات دمج لهذه الجولات.

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

إضافة إلى ما سبق، إن عرضنا العنصر رقم 0 على القرص وحصلنا على مدخلات قد لا تتلائم مع المنافسة الحالية (لأنّ القيمة "حاكمة" على آخر قيمة للمخرجات)، فلا يمكن لهذه القائمة أن تتلائم مع الكومة، وهكذا يتناقص حجم الكومة، ويمكن استخدام الذاكرة المتحررة مباشرة لبناء كومة ثانية تدريجيًا، وستنمو هذا الكومة بنفس سرعة تناقص الكومة الأولى. وعند انتهاء الكومة الأولى، يمكننا تبديل الكومة والبدء بجولة جديدة.

مصادر

• صفحة Heap queue algorithm في توثيق بايثون الرسمي.