الطابور مزدوج الطرف في Python: ترتيب العناصر والسعة المحدودة وما يُحذف

بنية ذات طرفين وسياسة استعمال

تقدم وثائق Python الطابور المزدوج deque بوصفه حاوية تسمح بالإضافات والإزالات عند الجهتين. ويصف مرجع NIST الطابور في معناه المعتاد بترتيب خروج يحافظ على أسبقية الدخول. ليست كل طريقة استعمال للطرفين طابورًا بالمعنى نفسه؛ نحتاج أن نعلن جهة الإضافة وجهة السحب قبل تفسير المخرجات.

سنختار العناصر 12 و 24 و 36، ونرسمها من اليسار إلى اليمين بهذا الترتيب. الأرقام قيم مؤلفة، لا معرفات معاملات أو قياسات. سنجرب على نسخ منفصلة من الحالة كي لا تنسب نتيجة عملية لاحقة إلى القائمة الأولى التي تغيرت. حالة البداية والطرف المختار والقيمة المرجعة والباقي معلومات تحفظ المعنى معًا.

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

[1] [2]

أربع عمليات على الطرفين

نبدأ بطابور غير محدود يحتوي 12 و 24 و 36. إذا أضفنا 48 باستعمال append، صار الترتيب 12 و 24 و 36 و 48. وإذا أخذنا نسخة جديدة من البداية واستعملنا appendleft للقيمة 6، صار الترتيب 6 و 12 و 24 و 36. الإضافة من جهة لا تعني فرز القيم بحسب مقدارها؛ المواضع تتبع العملية التي طلبناها.

أما pop على نسخة من الحالة الأصلية فيعيد 36 ويترك 12 و 24، بينما popleft يعيد 12 ويترك 24 و 36. لا نجعل اختيار الجهة تفصيلًا شكليًا؛ المخرجان مختلفان رغم أن عدد العناصر نقص واحدًا في الحالتين. إذا كان أول الداخلين هو من ينبغي أن يخرج، فالإضافة يمينًا مع السحب يسارًا يحققان ذلك في النموذج المتسلسل.

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

القراءة لا تزيل عنصرًا

قراءة الموضع 0 في الحالة الأصلية تعطي 12 ولا تغير الطول 3. قراءة الموضع الأخير تعطي 36 أيضًا دون إزالة. أما popleft فينقص الطول ويعيد 12. إذا سجلت القيمة 12 فقط بعد الحالتين، فقد تفقد معلومة هل العنصر ما زال ينتظر في الحاوية أم أزيل منها. القيمة المرجعة لا تكفي وحدها لوصف أثر عملية.

وفي الفراغ، لا يوجد عنصر عند الموضع 0 ولا عند الموضع الأخير. وكذلك pop و popleft ترفعان IndexError عند عدم وجود عناصر، وفق الواجهة الموثقة. يمكن أن تختار دالتك عقدًا يعيد نتيجة مميزة أو يعالج الاستثناء، لكن لا نخلط نتيجة الفراغ بقيمة عنصر حقيقي. مثلًا None قد تكون حمولة واردة فعلًا إذا سمح عقد البيانات بها.

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

سعة 3: إضافة من اليمين تسقط من اليسار

ننشئ الحاوية 12 و 24 و 36 بسعة قصوى 3. وصلت إلى السعة بالفعل. عند append للقيمة 48 تصبح القيم المحتفظ بها 24 و 36 و 48، ويسقط 12 من الطرف المقابل. طولها يظل 3، لذلك لا يكشف عد العناصر وحده أن مجموعة المحتوى تغيرت أو أن قيمة قديمة خرجت دون أن نطلب popleft صراحةً.

الرسم الرئيسي يثبت الحالة قبل العملية وبعدها، ويكتب العنصر المسقط 12 بجانبها. لا يعني سقوطه أنه عولج بنجاح أو أن عملًا يمثل الرقم قد انتهى؛ معناه الوحيد في هذا النموذج أن سياسة الاحتفاظ لم تبقه. إذا أردت الاحتفاظ بسجل لكل ما وصل، فإن النافذة ذات الثلاثة عناصر ليست هذا السجل بمفردها.

وإذا كانت البداية 12 و 24 فقط بالسعة نفسها، فإن append للقيمة 36 يكملها إلى 3 دون إسقاط قديم. نراجع الامتلاء قبل الإضافة، لا مجرد وجود maxlen في التعريف. السعة تحدد حد الطول الممكن، لكن أثر عملية بعينها يعتمد على الحالة الحالية أيضًا. المثالان يميزان الوصول إلى السعة من الوصول بعد اكتمالها.

[1]

الإضافة اليسرى تغير جهة ما يسقط

نأخذ نسخة جديدة من 12 و 24 و 36 بسعة 3، ثم نضيف 6 يسارًا. تصبح القيم 6 و 12 و 24، ويسقط 36 من اليمين. لا نعيد نتيجة المثال السابق الذي حذف 12؛ الطرف الذي أضفنا إليه تغير، فانتقلت جهة الإسقاط إلى الطرف المقابل له. نحتاج الاسم appendleft إلى جانب القيم كي نعيد تفسير النتيجة.

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

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

تمديد جهة اليسار يعكس ترتيب المدخل

نختار حاوية غير محدودة 12 و 24، ومدخل تمديد 5 ثم 8. extendleft يضيف كل عنصر يسارًا بالتتابع: بعد 5 تصير 5 و 12 و 24، وبعد 8 تصير 8 و 5 و 12 و 24. إذن ترتيب المدخل 5 و 8 انعكس في الجزء المضاف. لا نكتب 5 و 8 و 12 و 24 بوصفها نتيجة هذه العملية نفسها؛ ذلك يعبر عن طريقة أخرى لوضع المجموعة.

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

وهذا لا يغير سلوك appendleft للعنصر الواحد؛ العملية المفردة لا تعكس قائمة داخلية من تلقاء نفسها. إذا أضفت كائن قائمة[5,8]كحمولة واحدة، فهو عنصر واحد يحمل قائمة، لا عنصران 5 و 8. فرق العنصر المفرد من المتتابعة التي تمدها جزء من عقد الكود، وسنراجعه في قوائم صغيرة حتى لا تدخل حمولة واحدة على أنها عنصران منفصلان.

[1]

تمديد متعدد في نافذة محدودة

نعود إلى 12 و 24 و 36 بسعة 3. إذا مددنا اليمين بالمدخل 48 و 60، نحصل بعد 48 على 24 و 36 و 48، ثم بعد 60 على 36 و 48 و 60. سقط عنصران قديمان،12 ثم 24. لا نسجل فقد عنصر واحد فقط لأن اسم extend ظهر مرة واحدة في البرنامج؛ الاستدعاء يمثل مرور عناصر متعددة في النموذج.

وإذا مددنا اليسار بالمدخل 5 ثم 8 في نسخة جديدة، تكون المرحلة الأولى 5 و 12 و 24، وتسقط 36. ثم تصبح 8 و 5 و 12، وتسقط 24. تغير كل من ترتيب الجزء الجديد وجهة ما خرج. الرسم الداخلي سيعرض هذا التعاقب، كي نميز النتيجة النهائية من سجل الإسقاطات التي لا نراها بمجرد تحويل الطابور إلى قائمة في النهاية.

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

عرض الرسم بالحجم الكامل

السعة المحدودة لا تضمن سياسة واحدة لكل إدراج

نختار الحاوية الأصلية الممتلئة 12 و 24 و 36 بسعة 3، ثم نحاول insert في موضع داخلها لقيمة 18. توثق الواجهة IndexError إذا كان الإدراج سيجعل الطول يتجاوز maxlen. لا تسلك هذه العملية سياسة append نفسها التي تسمح بوصول جديد وتحذف من الطرف المقابل. الاسم العام إضافة لا يكفي لخلط عقدي الطريقتين.

ننفذ المثال في حالة منفصلة ونحفظ ما رجع من استثناء وما بقي. أما إذا بدأنا 12 و 24 بسعة 3، فإن insert للقيمة 18 عند 1 يمكن أن يعطي 12 و 18 و 24. امتلاء الحاوية واسم العملية يؤثران معًا. لا ننقل نتيجة الإخفاق من حالة ممتلئة إلى كل إدراج في حاوية لها حد ثابت.

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

سعة 0: قبول الاستدعاء لا يعني الاحتفاظ

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

سنعد في غلاف التسجيل البسيط أن العنصر الجديد نفسه هو ما لم يحتفظ به عندما تكون السعة 0. لا نسميه عنصرًا قديمًا خرج؛ لم توجد خانة قديمة أخذنا منها القيمة. هذا الاختلاف مهم في معنى التقرير، خصوصًا إذا كنت تستعمل كلمة إسقاط لكل ما لم يعد ظاهرًا في النافذة.

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

غلاف أصلي يسجل ما لم يحتفظ به

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

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

ونستخدم قائمة في الناتج لتمييز سقوط حمولة None من عدم سقوط شيء. فإذا كانت السعة 1 والقيمة القديمة None ووصل 48، يرجع[None]ويصبح المحتوى[48]. القائمة الفارغة تعني أثرًا مختلفًا ولا ينبغي دمجها بالقائمة ذات العنصر None. سننفذ هذه الحالات محليًا مع مرجع مستقل يستعمل قائمة عادية حتى يكون معنى التقرير قابلًا للمراجعة.

def append_right_reported(buffer, item):
    discarded = []
    if buffer.maxlen == 0:
        discarded.append(item)
    elif buffer.maxlen is not None and len(buffer) == buffer.maxlen:
        discarded.append(buffer[0])
    buffer.append(item)
    return discarded

الدوران ليس قلب الترتيب

في الحاوية 12 و 24 و 36 و 48، rotate(1)يعطي 48 و 12 و 24 و 36. انتقل عنصر اليمين إلى البداية، وبقي ترتيب الثلاثة الآخرين كما كان. أما rotate(-1)على نسخة من الأصل فيعطي 24 و 36 و 48 و 12. يوضح التوثيق اتجاه الإشارة؛ لا نفترض أن الموجب يتحرك إلى اليسار لأن اتجاه قراءة نص عربي يختلف من ترتيب القيم في الكود.

القلب الكامل يعطي 48 و 36 و 24 و 12، وهو غير نتيجة دوران خطوة واحدة. يمكن فحص المثال بتتبع قيمة 24: بعد الدوران الأيمن تبقى تالية 12، وبعد القلب تصبح تالية 36. لذلك لا نضع اسمي rotate و reverse موضع بعضهما عند تحليل سجل عمليات، ولو كان الطول واحدًا أو كانت قائمة قصيرة قد جعلت النتيجتين تتفقان مصادفةً.

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

الحد والعدد ومحتويات الحالة

maxlen تصف الحد، بينما len تصف عدد العناصر الموجودة الآن. حاوية حدها 3 وطولها 2 تختلف من أخرى حدها 3 وطولها 3 في أثر الإضافة التالية. كما يمكن لحاوية غير محدودة أن يكون طولها 3 الآن؛ اتفاق الطول مع نموذجنا المحدود لا يعني أنها ستسقط القديم عند وصول رابع. نحتفظ بالقيمتين عندما تكون سياسة الاحتفاظ جزءًا من المعنى.

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

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

الفهرسة لا تغير اتفاق الطرفين

الموضع 0 في ترتيبنا من اليسار يشير إلى أول عنصر، والموضع الأخير يقرأ من الطرف المقابل. بعد append على النافذة الممتلئة، صارت 24 أول عنصر بدل 12، لذلك لا يبقى الفهرس 0 معرفًا للعنصر السابق. إذا كانت الحمولة تحمل هوية، فنحفظها داخل البيانات ونراجعها عند انتقال المواقع، بدل استعمال موضع قديم بوصفه هوية ثابتة.

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

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

سجل مرور لا يساوي سجل إنجاز

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

وفي بيانات مؤلفة من وصول 12 و 24 و 36 و 48 و 60، تعرض نافذة الإضافة اليمينية بسعة 3 الأخير 36 و 48 و 60. لا تنفي هذه اللقطة وصول 12 و 24، ولا تثبت أن عناصرها الثلاثة الحالية هي الوحيدة التي ينبغي تفسيرها في سؤال عن كل المرور. علينا تحديد هل نسأل عن كل عناصر دخلت أو عن نافذة حالية فقط.

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

فحوص محلية ومرجع قائمة عادية

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

نضيف تكرارات وقيمة None ونوافذ غير ممتلئة وفراغًا، ثم نراجع extendleft عنصرًا عنصرًا. كما نختبر insert عند الامتلاء في حالة منفصلة، والدوران يمينًا ويسارًا مقارنةً بتبديل مواقع قائمة معلنة. هذه حالات تكشف الخلط بين الجهات والسعة والعنصر الواحد والمتتابعة، لكنها ليست حصرًا لكل نوع حمولة أو سلوك مقارنات مخصصة.

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

قائمة مراجعة قبل استعمال نافذة محدودة

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

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

وأخيرًا، اكتب ما الذي تمثله اللقطة: محتويات حالية أم سجل وصول أم مهام انتظار. أمثلتنا قيم أصلية نفذت محليًا، لا ضمان حفظ لكل أحداث نظام حقيقي. يمكن إعادة المقارنة بين append للقيمة 48 و appendleft للقيمة 6 على الحالة الأصلية، ثم التمديد 5 و 8 يسارًا. عندما تكون الجهة والسعة والنتيجة معلنة، يظل أثر العملية مفهومًا قبل ربطه بمعنى خارج الكود.

وللفهرس بوصفه موقعًا داخل نطاق معلن، اقرأ الفهرس داخل الصف والمحور المحدد.