Сортировка наборов упорядоченных связанных списков

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

, если отдельные списки уже отсортированы, то это прямое применение алгоритма слияния . короче говоря: сравните все головы и выберите самую маленькую, выньте ее из своего списка и нажмите в свой выходной список. повторять до тех пор, пока все списки источников не станут пустыми.

edit: использование Konrad очереди приоритетов ( heap ) является гораздо более элегантным и масштабируемым решением, но, возможно, 256 входных списков настолько малы, что простое сравнение может быть быстрее.

Answer 3

Вы не говорите, как долго эти списки, но я предполагаю, что они все помещаются в ОЗУ одновременно. Первое, что я бы попробовал, это сложить их все вместе и вызвать встроенную процедуру сортировки в моей среде, и я посмотрю, даст ли это приемлемую производительность. Это легко реализовать и не займет много времени для тестирования. Если бы это не дало приемлемой производительности, я бы согласился на слияние очереди приоритетов, данное Конрадом Рудольфом.

Answer 4

Просто объедините каждый список со списком 128 над ним. (в результате получается 128 списков)
Затем объедините каждый список со списком 64 над ним. (в результате получается 64 списка)
Затем объедините каждый список со списком 32 над ним. (в результате получается 32 списка)
Затем объедините каждый список со списком 16 над ним. (в результате получается 16 списков)
Затем объедините каждый список со списком 8 над ним. (в результате получается 8 списков)
Затем объедините каждый список со списком 4 над ним. (в результате 4 списка)
Затем объедините каждый список со списком 2 над ним. (в результате получается 2 списка)
Затем объедините каждый список со списком 1 над ним. (в результате 1 список)
(Вы можете использовать цикл для вышеперечисленного).