التجميع المتجاور groupby: حدود المجموعة وحفظ أعضائها قبل التقدم

حدد هل السؤال عن مقطع أم فئة

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

توثق Python أن groupby تنتج مفاتيح ومجموعات متتابعة، وتبدأ مجموعة عند تغير المفتاح. المجموعة نفسها مكرر يشارك الإدخال؛ لذلك تتأثر إمكانية قراءتها بالتقدم في المكرر الخارجي. إذا أردنا جمع كل العناصر المتساوية في مفتاح واحد بهذه الأداة، نرتبها بحيث تتجاور وفق المفتاح المقصود. هذه حقائق الواجهة التي سنختبر آثارها في بياناتنا المؤلفة.[1]

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

ثمانية سجلات تحمل الهوية والمفتاح والقيمة

نعطي السجلات معرفات من p0 إلى p7 بحسب ترتيبها الأول. مفاتيحها X وX وY وX وY وY وY وX، وقيمها العددية على الترتيب 4 و7 و3 و2 و6 و1 و5 و8. القيمة وحدة تعليمية واحدة اخترناها، وليست مدة أو مبلغًا أو قياسًا حقيقيًا. المفتاح هو حقل الفئة فقط؛ لا نستعمل القيمة العددية لتحديد حد المقطع.

تظل هوية السجل مفيدة حتى لو تشابه مفتاحه وقيمته مع سجل آخر. p0 وp1 ينتميان إلى X لكنهما ملاحظتان مستقلتان في ترتيبنا. وp3 وp7 يعودان إلى X في موضعين لاحقين. لا نستبدل الهويات بالمفتاح إذا كان السؤال يطلب استرجاع تسلسل الإدخال، لأن أربعة سجلات تحمل X لن يكفي اسم X لتمييز أي منها جاء أولًا أو أين فصل Y بينها.

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

امش على التتابع وارسم حد كل مقطع

نبدأ عند p0 ومفتاحه X، ونضم p1 لأن مفتاحه X أيضًا. عند p2 نجد Y فنغلق المقطع الأول قبل هذا الموضع، ثم نفتح مقطع Y. يلي ذلك p3 ومفتاحه X، فيكون مقطع Y الأول مفردًا. تأتي p4 بفئة Y فتغلق مقطع X الثاني الذي احتوى p3 وحده، وتبدأ سلسلة Y جديدة تضم p4 ثم p5 ثم p6.

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

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

حدود مشمولة وأخرى غير مشمولة

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

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

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

من خمسة مقاطع إلى فئتين بعد الفرز

نفرز نسخة من السجلات بحسب حقل الفئة، فتظهر X قبل Y في ترتيب نصوص المثال. داخل X تبقى المعرفات p0 ثم p1 ثم p3 ثم p7، وداخل Y تكون p2 ثم p4 ثم p5 ثم p6. تصبح القائمتان متجاورتين، ويعطي تقسيم الترتيب الجديد مقطعين، لكل منهما أربعة أعضاء.

تذكر وثائق sorted أنها تنتج قائمة مرتبة جديدة، وأن الفرز مستقر: العناصر المتساوية في مفتاح المقارنة تحتفظ بترتيبها النسبي. لا يعني ذلك أن مواقع جميع السجلات بقيت كما كانت؛ معناه هنا أن ترتيب أعضاء X فيما بينهم لم يتبدل، وكذلك أعضاء Y. أما العلاقات بين الفئتين فتغيرت بالفرز.[2]

بعد التحويل صار p3 مجاورًا لـp1، رغم أن p2 فصل بينهما في الأصل. وصار p7 في مجموعة X قبل جميع Y، بعدما كان آخر السجل. إذا كان السؤال عن عدد العناصر لكل فئة فهذا التقسيم نافع في مثالنا. أما سؤال أين عاد X بعد Y فلا يجيبه حد المقطع الجديد من صفر إلى أربعة، لأنه وصف لترتيب مشتق لا للتتابع الأصلي.

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

المفتاح عقد تختاره قبل التقسيم

في السجلات الثمانية عرفنا المفتاح بأنه حقل الفئة النصي وحده. لذلك p4 وp5 وp6 مقطع واحد رغم أن قيمها 6 و1 و5 مختلفة. لو جعلنا المفتاح زوج الفئة والقيمة لكان هذا تقسيمًا آخر؛ كل عنصر من تلك الثلاثة يختلف عن جاره في الزوج، فينتج ثلاثة مقاطع بدل المقطع الواحد.

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

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

احفظ الأعضاء قبل طلب المجموعة التالية

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

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

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

كود أصلي يحفظ الهوية والحدود معًا

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

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

على بياناتنا، الوصف الأول يحفظ p0 وp1 مع المفتاح X والحدين صفر واثنين. الوصف الرابع يحفظ p4 وp5 وp6 مع المفتاح Y والحدين أربعة وسبعة. نراجع الأعضاء والحدود معًا؛ فمطابقة طول ثلاثة وحده لا تثبت أننا حفظنا السجلات الثلاثة الصحيحة، كما أن حفظ أسماء المفاتيح وحده لا يثبت ترتيب المواضع.

from itertools import groupby


def retained_runs(rows, key):
    output = []
    offset = 0
    for label, members in groupby(rows, key):
        saved = tuple(members)
        end = offset + len(saved)
        output.append({
            "key": label,
            "start": offset,
            "stop": end,
            "members": saved,
        })
        offset = end
    return output

حفظ الحاوية لا يعني نسخ السجل بعمق

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

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

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

تلخيص المقطع يجيب سؤالًا أضيق

قيم أول مقطع هي 4 و7، فيكون عدده اثنين ومجموعه 11. المقطع الثاني قيمته 3، والثالث 2، والرابع يجمع 6 و1 و5 إلى 12، والأخير 8. بجمع المجاميع الخمسة نحصل على 36. هذه عملية مستقلة عن قرار حدود المجموعات؛ لو حفظنا أعضاءها دون حساب المجموع لبقي التقسيم نفسه.

إذا جمعنا جميع X تصبح القيم 4 و7 و2 و8، ومجموعها 21 مع عدد أربعة. وجميع Y قيمها 3 و6 و1 و5، ومجموعها 15 مع عدد أربعة أيضًا. جمع 21 و15 يعيد 36، لكن الرقمين لا يخبراننا أن ترتيب الأصل كان خمس مقاطع، أو أن أطول مقطع Y احتوى ثلاث سجلات محددة.

ولبيان فقدان التفاصيل، يمكن لمقطع X من قيمتين 5 و6 أن يعطي العدد اثنين والمجموع 11 مثل مقطعنا الأول من 4 و7. لذلك لا نعيد قيم الأعضاء من هذين الملخصين وحدهما. يناقش مقال البيانات التفصيلية والبيانات المجمعة هذا الفرق في مستوى المعلومات، بينما نحدد هنا أيضًا موضع الملخص داخل التتابع.

التصفية قبل التقسيم قد توصل ما كان منفصلًا

نحذف من نسخة السجل جميع عناصر Y قبل تقسيم المقاطع. يبقى p0 ثم p1 ثم p3 ثم p7، وكلها X، فتكون مقطعًا واحدًا طوله أربعة. التصفية لم تغير ترتيب X فيما بينها، لكنها أزالت العناصر التي كانت تشكل الفواصل. لا يصح أن نسمي هذا الناتج عدد مقاطع X في السجل الأصلي دون ذكر أن الفواصل حذفت أولًا.

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

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

قطع الإدخال إلى أجزاء يحتاج قاعدة للوصل

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

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

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

عدد المقاطع يساوي البداية والانتقالات

لأي قائمة غير فارغة في نطاق مثالنا، يبدأ مقطع أول عند العنصر الأول. وبعده نفتح مقطعًا فقط عندما يختلف مفتاح العنصر عن مفتاح جاره السابق. لذلك عدد المقاطع يساوي واحدًا زائد عدد الانتقالات بين مفتاحين متجاورين مختلفين. في تسلسلنا وقعت انتقالات قبل p2 وp3 وp4 وp7، فتكون النتيجة واحدًا زائد أربعة، أي خمسة.

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

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

الذاكرة تتبع ما قررت الاحتفاظ به

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

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

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

فحوص تعيد بناء الأصل من النتائج

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

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

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

بطاقة نتيجة تجعل حدود العمل واضحة

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

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

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