Sortierung Sätze geordneter verkettete Listen

Question

Ich bin auf der Suche nach einer eleganten, High Performance Lösung für das folgende Problem.

Es gibt 256 verkettete Listen.

• Jede Liste enthält die gleichen Arten von Objekt, das unter anderem eine ganze Zahl enthält, die verwendet wird, eine Sortierreihenfolge zu definieren.
• Alle Zahlen in allen Listen sind einzigartig
• Jede einzelne Liste wird durch diese Zahlen in aufsteigender Reihenfolge sortiert

Wie würden Sie ein einziges aufsteigend create geordnete Liste aller Objekte aus den 256 ursprünglichen verkettete Listen? Ich würde es vorziehen, nicht Brute zu zwingen, und ein paar andere Ideen haben, aber dies scheint wie eine jener Probleme, dass es einen Standard, optimale Lösung für.

Answer 1

Sie können eine Prioritätswarteschlange verwenden, die die „oberste“ Element eines jeden der 256 verkettete Listen hält. Dieses „oberste“ item ist derjenige, der in die resultierende Liste eingefügt werden soll. Auf diese Weise können Sie einfach nehmen das kleinste Element aus der Prioritätswarteschlange, legen Sie sie in Ihre resultierende Warteschlange, und legen Sie seine nächste Element in der Prioritätswarteschlange:

# 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

, wenn die einzelnen Listen bereits sortiert sind, dann ist es eine direkte Anwendung des Algorithmus zu fusionieren . kurz: Vergleichen Sie die Köpfe und die kleinste Pick, nehmen Sie es aus der Liste aus und drücken Sie in Ihrer Ausgabeliste. wiederholen, bis alle Quelllisten leer sind.

edit: Konrads Verwendung einer Prioritätswarteschlange (a Haufen ) ist ein viel eleganter und skalierbare Lösung, aber vielleicht 256 Eingabelisten sind so wenige, dass ein einfacher schneller vergleichen könnte.

Answer 3

fusioniert einfach jede Liste mit der Liste 128 darüber. (Was zu 128 Listen)
Dann verschmilzt jede Liste mit der Liste 64 darüber. (Was in 64 Listen)
Dann verschmilzt jede Liste mit der Liste 32 darüber. (Was in 32 Listen)
Dann verschmilzt jede Liste mit der Liste 16 darüber. (Was in 16 Listen)
Dann verschmilzt jede Liste mit der Liste 8 darüber. (Was in 8 Listen)
Dann verschmilzt jede Liste mit der Liste 4 darüber. (Was in 4 Listen)
Dann verschmilzt jede Liste mit der Liste 2 darüber. (Was in 2 Listen)
Dann verschmilzt jede Liste mit der Liste 1 darüber. (Was in 1 Liste)
(Sie können eine Schleife für die oben verwenden).

Answer 4

Sie sagen nicht, wie lange diese Listen sind, aber ich nehme sie alle im RAM zur gleichen Zeit passen. Das erste, was ich versuchen würde, ist anhängt sie alle zusammen, und meine Umgebung des builtin Art Routine aufrufen, und ich würde sehen, ob das eine akzeptable Leistung gab. Es ist einfach zu implementieren und testen würde nicht lange dauern. Wenn das nicht eine akzeptable Leistung gegeben hat, würde ich mit der Prioritätswarteschlange merge gehen von Konrad Rudolph gegeben.