فرز مجموعات من القوائم المرتبطة المرتبة

Question

أنا أبحث عن حل أنيق وعالي الأداء للمشكلة التالية.

هناك 256 قائمة مرتبطة.

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

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

Answer 1

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

# Preprocessing:
result = list.new()
queue = priority_queue.new()

foreach (list in lists):
    queue.push(list.first())

# Main loop:
while (not queue.empty()):
    node = queue.pop()
    result.insert(node)
    if (node.next() != null):
        queue.push(node.next())

Answer 2

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

يحرر:استخدام كونراد لقائمة الانتظار ذات الأولوية (أ كومة) هو حل أكثر أناقة وقابلية للتطوير، ولكن ربما تكون 256 قائمة إدخال قليلة جدًا بحيث يمكن أن تكون المقارنة البسيطة أسرع.

Answer 3

ما عليك سوى دمج كل قائمة مع القائمة 128 الموجودة فوقها.(ينتج عنه 128 قائمة)
ثم قم بدمج كل قائمة مع القائمة 64 التي تعلوها.(ينتج عنه 64 قائمة)
ثم قم بدمج كل قائمة مع القائمة 32 التي تعلوها.(ينتج عنه 32 قائمة)
ثم قم بدمج كل قائمة مع القائمة رقم 16 التي تعلوها.(ينتج عنه 16 قائمة)
ثم قم بدمج كل قائمة مع القائمة رقم 8 التي فوقها.(ينتج عنه 8 قوائم)
ثم قم بدمج كل قائمة مع القائمة رقم 4 التي فوقها.(ينتج عنه 4 قوائم)
ثم قم بدمج كل قائمة مع القائمة رقم 2 التي فوقها.(مما أدى إلى قائمتين)
ثم قم بدمج كل قائمة مع القائمة رقم 1 التي تعلوها.(ينتج عنه قائمة واحدة)
(يمكنك استخدام حلقة لما سبق).

Answer 4

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