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

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 над ним.(в результате получается 2 списка)
Затем объедините каждый список со списком 1 над ним.(в результате получается 1 список)
(Вы можете использовать цикл для вышеописанного).

Answer 4

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