Ordinamento di set di elenchi collegati ordinati

Question

Sto cercando una soluzione elegante e ad alte prestazioni al seguente problema.

Ci sono 256 liste collegate.

• Ogni elenco contiene gli stessi tipi di oggetto che tra le altre cose contiene un numero intero che viene utilizzato per definire un ordinamento.
• Tutti i numeri in tutti gli elenchi sono unici
• Ogni singolo elenco è ordinato in ordine crescente in base a questi numeri

Come creeresti un singolo elenco ordinato crescente da tutti gli oggetti dalle 256 liste collegate originali? Preferirei non forzarlo brutalmente e avere qualche altra idea, ma questo sembra uno di quei problemi per i quali esiste una soluzione standard ottimale.

Answer 1

È possibile utilizzare una coda di priorità che contiene l'elemento "più in alto" di ciascuno dei 256 elenchi collegati. Questo elemento "più in alto" è quello che è programmato per essere inserito nell'elenco risultante. In questo modo, puoi semplicemente prendere l'elemento più piccolo dalla coda di priorità, inserirlo nella coda risultante e inserire il suo elemento successivo nella coda di priorità:

# 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

se i singoli elenchi sono già ordinati, si tratta di un'applicazione diretta dell'algoritmo di fusione merge . in breve: confronta tutte le teste e scegli la più piccola, estraila dalla sua lista e spingi nella tua lista di output. ripetere fino a quando tutti gli elenchi di sorgenti sono vuoti.

modifica: l'uso di Konrad di una coda prioritaria (un heap ) è un soluzione molto più elegante e scalabile, ma forse 256 elenchi di input sono così pochi che un semplice confronto potrebbe essere più veloce.

Answer 3

Unisci ogni elenco con l'elenco 128 sopra di esso. (risultante in 128 elenchi)
Quindi unire ogni elenco con l'elenco 64 sopra di esso. (risultante in 64 elenchi)
Quindi unire ogni elenco con l'elenco 32 sopra di esso. (risultante in 32 elenchi)
Quindi unire ogni elenco con l'elenco 16 sopra di esso. (risultante in 16 elenchi)
Quindi unire ogni elenco con l'elenco 8 sopra di esso. (risultante in 8 elenchi)
Quindi unire ogni elenco con l'elenco 4 sopra di esso. (risultante in 4 elenchi)
Quindi unire ogni elenco con l'elenco 2 sopra di esso. (risultante in 2 elenchi)
Quindi unire ogni elenco con l'elenco 1 sopra di esso. (risultante in 1 elenco)
(È possibile utilizzare un ciclo per quanto sopra).

Answer 4

Non dici quanto sono lunghi questi elenchi, ma suppongo che si adattino tutti alla RAM contemporaneamente. La prima cosa che vorrei provare è aggiungerle tutte insieme e chiamare la routine di ordinamento integrata del mio ambiente e vedrei se ciò ha dato prestazioni accettabili. È facile da implementare e non ci vorrebbe molto tempo per testarlo. Se ciò non offrisse prestazioni accettabili, sceglierei la fusione delle code prioritarie fornita da Konrad Rudolph.