Python/deque

تعدّ deques صورة عامة للأكداس والطوابير stacks and queues (يقرأ الاسم هكذا "deck" وهو اختصار للعبارة "double-ended queue").

تدعم deques عمليات الإضافة والحذف من طرفي الطابور مع ضمان سلامة الخيوط thread-safe ودون استهلاك كبير للذاكرة وبأداء مقارب لأداء O(1)‎ في كلا الاتجاهين.

صحيح أن القوائم تدعم مثل هذه العمليات، إلا أنّها مصمّمة للعمليات السريعة ذات الطول الثابت وتكلّف الذاكرة بمقدار O(n)‎ للعمليتين pop(0)‎ و insert(0, v)‎ واللتان تغيران حجم وموقع البيانات الضمنية الممثلة.

البنية العامة

‎class collections.deque([iterable[, maxlen]])

تعيد الدالة البانية كائن deque جديدًا مهيّئًا من اليسار إلى اليمن (باستخدام التابع append()‎) مع البيانات القادمة من الكائن المكرِّر iterable المعطى. وف يحال عدم تحديد الكائن المكرِّر يكون كائن deque الجديد فارغًا.

يبين المثال التالي طريقة إنشاء كائن deque:

>>> from collections import deque
>>> d = deque('ghi')                 # إنشاء كائن جديد يمتلك ثلاثة عناصر
>>> for elem in d:                   # deque المرور على عناصر 
...     print(elem.upper())
G
H
I

في حال عدم تحديد قيمة maxlen أو أخذ هذا المعامل القيمة None، فيمكن لكائن deque أن يصل إلى طول غير محدّد. وفيما عدا ذلك، يكون كائن deque محدّدًا بالطول المعطى.

تؤدي إضافة عناصر جديدة إلى كائن deque الممتلئ إلى حذف نفس عدد العناصر المضافة من الطرف المقابل. تؤدي كائنات deque ذات الطول المحدد نفس وظيفة المرشح tail في أنظمة يونكس.

كائنات deque مفيدة أيضًا في تعقب الإجراءات ومجموعات (pools) البيانات الأخرى حيث يكون المطلوب التعامل مع الأنشطة الحديثة فقط.

توابع كائنات deque

تدعم كائنات deque التوابع التالية:

التابع append()‎

يضيف التابع العنصر المعطى إلى الجانب الأيمن من كائن deque.

التابع appendleft()‎

يضيف التابع العنصر المعطى إلى الجانب الأيسر من كائن deque.

التابع clear()‎

يحذف جميع العناصر من كائن deque.

التابع copy()‎

ينشئ التابع نسخة سطحية من كائن deque.

التابع count()‎

يحسب التابع عدد عناصر deque المساوية للقيمة المعطاة.

التابع extend()‎

يمدّد الجانب الأيمن من كائن deque بإضافة العناصر المعطاة.

التابع extendleft()‎

يمدّد الجانب الأيسر من كائن deque بإضافة العناصر المعطاة.

التابع index()‎

يعيد التابع موقع العنصر المعطى في كائن deque.

التابع insert()‎

يدرج التابع القيمة المعطاة في الكائن deque في الموقع المحدّد.

التابع pop()‎

يحذف التابع ويعيد عنصرًا واحدًا من الجانب الأيمن في الكائن deque.

التابع popleft()‎

يحذف التابع ويعيد عنصرًا واحدًا من الجانب الأيسر في الكائن deque.

التابع remove()‎

يحذف التابع أوّل عنصر يحمل القيمة المعطاة.

التابع reverse()‎

يعكس التابع ترتيب عناصر الكائن deque في نفس المكان.

التابع rotate()‎

يدوّر التابع كائن deque إلى جهة اليمين بعدد الخطوات المعطاة.

خصائص كائنات deque

تقدّم كائنات deque خاصية واحدة للقراءة فقط:

الخاصية maxlen

تحمل هذه الخاصية قيمة الحجم الأقصى لكائن deque إن كان الكائن ذا طول محدّد، أو القيمة None إن كان الكائن غير محدّد الطول.

ملاحظة: هذه الخاصية جديدة في الإصدار 3.1.

تدعم deques إضافة إلى ما سبق عمليات التكرار iteration، وpickling، ويمكن معرفة طول كائن deque (عدد العناصر فيه) باستخدام الدالة len(d)‎، وقلب ترتيب العناصر بواسطة reversed(d)‎، وإجراء عمليات النسخ السطحية والعميقة بواسطة copy.copy(d)‎ و copy.deepcopy(d)‎، والتأكد من وجود عنصر ما بواسطة العامل in، والإشارات الخلفية subscript references مثل d[-1]‎.

تكون عملية الوصول المفهرس إلى العناصر بسرعة O(1)‎ ولكنّها تصبح أبطأ لتصل إلى سرعة O(n)‎ في الوسط. يمكن استخدام القوائم بدلًا من كائنات deque للحصول على أداء أسرع في الوصول العشوائي.

بدءًا من الإصدار 3.5 من بايثون، أصبحت كائنات deque تدعم التوابع ‎__add__()‎ و ‎__mul__()‎ و ‎__imul__()‎.

تطبيقات للكائن deque

يعرض هذا القسم بعض طرق استخدام كائنات deque.

تؤدي كائنات deque ذات الطول المحدد وظيفة مشابهة للمرشح tail في أنظمة يونكس:

def tail(filename, n=10):
    'Return the last n lines of a file'
    with open(filename) as f:
        return deque(f, n)

يمكن استخدام كائنات deque للمحافظة على تسلسل العناصر المضافة حديثًا وذلك بإلحاق العناصر من جهة اليمين وحذفها من جهة اليسار:

def moving_average(iterable, n=3):
    # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
    # http://en.wikipedia.org/wiki/Moving_average
    it = iter(iterable)
    d = deque(itertools.islice(it, n-1))
    d.appendleft(0)
    s = sum(d)
    for elem in it:
        s += elem - d.popleft()
        d.append(elem)
        yield s / n

يمكن إنشاء برنامج لجدولة المباريات باستخدام مدخلات من المكرِّرات المخزّنة في كائن deque. وتنتج القيم من المكرِّر الفعال في الموقع صفر. وفي حال الوصول إلى نهاية ذلك المكرِّر يمكن حذفه باستخدام التابع popleft()‎ أو يمكن تدويره مجدّدًا إلى النهاية بواسطة التابع rotate()‎:

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    iterators = deque(map(iter, iterables))
    while iterators:
        try:
            while True:
                yield next(iterators[0])
                iterators.rotate(-1)
        except StopIteration:
            # حذف المكرِّر المستنفد.
            iterators.popleft()

يمكن استخدام التابع rotate()‎ كوسيلة لتضمين عمليتي الاقتطاع slicing والحذف deletion في كائنات deque. فعلى سبيل المثال، يعتمد المعامل del d[n]‎ في لغة بايثون الصرفة على التابع rotate()‎ لوضع العنصر المراد حذفه في الموضع الصحيح:

def delete_nth(d, n):
    d.rotate(-n)
    d.popleft()
    d.rotate(n)

وللاستفادة من عملية الاقتطاع في كائنات deque يمكن اتباع أسلوب مماثل حيث يطبّق التابع rotate()‎ لجلب العنصر المطلوب إلى الجهة اليسرى من كائن deque، ثم تُحذف العناصر القديمة باستخدام التابع popleft()‎، وتضاف العناصر الجديدة بواسطة التابع extend()‎ ثم تُعكس الدورة. وبإجراء بعض التعديلات على هذا الأسلوب، يصبح من السهل إضافة نمط Forth في معالجة الكدس بواسطة عمليات مثل dup، drop، swap، over، pick، rot و roll.

انظر أيضًا

• القوائم في بايثون.
• كائنات namedtuple: :دالة مولِّدة factory function لإنشاء أصناف فرعية من tuple تتضمن حقولًا مسمّاة
• كائنات ChainMap: :صنف شبيه بالقواميس يستخدم لإنشاء عرض منفرد لعمليات ربط mapping متعددة
• كائنات Counter: :صنف فرعي من الصنف dict الهدف منه عدّ الكائنات القابلة للتقطيع hashable
• كائنات OrderedDict: :صنف فرعي من الصنف dict يمكنه تذكّر ترتيب العناصر عند إضافتها
• كائنات defaultdict: :صنف فرعي من الصنف dict يستدعي دالة مولّدة تقدّم القيم المفقودة
• كائنات UserDict: :تغليف حول كائنات القواميس لتسهيل عملية تفريع أصناف القواميس
• كائنات UserList: :تغليف حول كائنات القوائم لتسهيل عملية تفريع أصناف القوائم
• كائنات UserString: :تغليف حول كائنات السلاسل النصية لتسهيل عملية تفريع أصناف السلاسل النصية

مصادر

• قسم deque Objects في صفحة Container Datatypes في توثيق بايثون الرسمي.