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

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

Есть 256 связанных списков.

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

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


sorting language-agnostic linked-list
person Nerdfest    schedule 02.10.2008    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Вы можете использовать приоритетную очередь, которая содержит «самый верхний» элемент каждого из 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())
person Konrad Rudolph    schedule 02.10.2008

arrow_upward
1
arrow_downward

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

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

person Javier    schedule 02.10.2008
comment
+1, но слияние было бы быстрее, если бы оно работало только с одним списком за раз. - person ; 02.10.2008

arrow_upward
0
arrow_downward

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

person paperhorse    schedule 26.10.2008

arrow_upward
0
arrow_downward

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

person Andru Luvisi    schedule 26.10.2008