排序有序链表的集合

I'm looking for an elegant, high performance solution to the following problem.

我正在寻找一个优雅,高性能的解决方案来解决以下问题。

There are 256 linked lists.

有256个链接列表。

• Each list contains the same types of object that among other things holds a whole number that is used to define a sort order.

每个列表包含相同类型的对象,其中包含用于定义排序顺序的整数。

• All numbers across all lists are unique

所有列表中的所有数字都是唯一的

• Each individual list is sorted in ascending order by these numbers

每个单独的列表按这些数字按升序排序

How would you create a single ascending ordered list from all the objects from the 256 original linked lists? I'd prefer not to brute force it, and have a few other ideas, but this seems like one of those problems that there's a standard, optimal solution for.

如何从256个原始链表中的所有对象创建单个升序有序列表?我不想暴力破解它,并且还有一些其他的想法,但这似乎是那些有标准的,最佳的解决方案的问题之一。

4 个解决方案

#1

You could use a priority queue that holds the “topmost” item of each of the 256 linked lists. This “topmost” item is the one that is scheduled to be inserted into the resulting list. This way, you can just take the smallest element from the priority queue, insert it into your resulting queue, and insert its next element into the priority queue:

您可以使用一个优先级队列来保存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())

#2

if the individual lists are already sorted, then it's a direct application of the merge algorithm. in short: compare all the heads and pick the smallest, take it out of its list and push into your output list. repeat until all source lists are empty.

如果各个列表已经排序,则它是合并算法的直接应用。简而言之:比较所有的头并挑选最小的头,将其从列表中取出并推入输出列表。重复,直到所有源列表都为空。

edit: Konrad's use of a priority queue (a heap) is a far more elegant and scalable solution, but maybe 256 input lists are so few that a simple compare could be faster.

编辑:Konrad使用优先级队列(堆)是一个更优雅和可扩展的解决方案,但可能256个输入列表很少,简单的比较可能更快。

#3

Just merge each list with the list 128 above it. (resulting in 128 lists)
Then merge each list with the list 64 above it. (resulting in 64 lists)
Then merge each list with the list 32 above it. (resulting in 32 lists)
Then merge each list with the list 16 above it. (resulting in 16 lists)
Then merge each list with the list 8 above it. (resulting in 8 lists)
Then merge each list with the list 4 above it. (resulting in 4 lists)
Then merge each list with the list 2 above it. (resulting in 2 lists)
Then merge each list with the list 1 above it. (resulting in 1 list)
(You might use a loop for the above).

只需将每个列表与其上方的列表128合并即可。 (产生128个列表)然后将每个列表与其上方的列表64合并。 (产生64个列表)然后将每个列表与其上方的列表32合并。 (产生32个列表)然后将每个列表与其上方的列表16合并。 (产生16个列表)然后将每个列表与其上方的列表8合并。 (产生8个列表)然后将每个列表与其上方的列表4合并。 (产生4个列表)然后将每个列表与其上方的列表2合并。 (产生2个列表)然后将每个列表与其上方的列表1合并。 (产生1个列表)(您可以使用上面的循环)。

#4

You don't say how long these lists are, but I assume they all fit in RAM at the same time. The first thing I would try is appending them all together, and calling my environment's builtin sort routine, and I'd see if that gave acceptable performance. It's easy to implement and wouldn't take long to test. If that didn't give acceptable performance, I'd go with the priority queue merge given by Konrad Rudolph.

你没有说这些列表有多长,但我认为它们同时适用于RAM。我要尝试的第一件事是将它们全部附加在一起,并调用我的环境的内置排序例程,我会看到它是否提供了可接受的性能。它易于实现,不需要很长时间来测试。如果这不能提供可接受的性能,我将使用Konrad Rudolph给出的优先级队列合并。