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

Я ищу элегантное и высокопроизводительное решение следующей проблемы.

Имеется 256 связанных списков.

  • Каждый список содержит те же типы объектов, что между прочим содержит целое число, которое используется для определения порядка сортировки.
  • Все номера во всех списках уникальны.
  • Каждый отдельный список сортируется в порядке возрастания по этим номерам

Как бы вы создали один восходящий упорядоченный список из всех объектов из 256 исходных связанных списков? Я бы предпочел не использовать эту команду и предложить несколько других идей, но это похоже на одну из тех проблем, в которой есть стандартное, оптимальное решение для.

4 ответа

Вы можете использовать очередь приоритетов, которая содержит "самый верхний" элемент каждого из 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())


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

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


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


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

licensed under cc by-sa 3.0 with attribution.