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

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

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

Редакция:

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

Answer 3

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

Answer 4

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