Classificando conjuntos de listas ligadas ordenados

Question

Eu estou procurando uma solução desempenho elegante, alto para o seguinte problema.

Existem 256 listas ligadas.

• Cada lista contém os mesmos tipos de objeto que entre outras coisas tem um número inteiro que é usado para definir uma ordem de classificação.
• Todos os números em todas as listas são únicas
• Cada lista individual é classificada em ordem crescente por esses números

Como você criar um único ascendente lista ordenada de todos os objetos das listas ligadas 256 originais? Eu prefiro não força bruta-lo, e tem algumas outras idéias, mas este parece ser um daqueles problemas que não há um padrão, solução ideal para.

Answer 1

Você pode usar uma fila de prioridade que mantém o “superior” artigo de cada uma das 256 listas ligadas. Este “superior” item é o que está programado para ser inserido na lista resultante. Dessa forma, você pode simplesmente pegar o menor elemento da fila de prioridade, insira-o na fila resultante, e inserir seu elemento seguinte na fila de prioridade:

# 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 as listas individuais já estão classificadas, então é uma aplicação directa da merge algoritmo . em suma: comparar todas as cabeças e escolher o menor, tirá-lo da sua lista e impulso em sua lista de saída. repetir até que todas as listas de origem estão vazias.

edit: uso de uma fila de prioridade do Konrad (a pilha ) é uma solução escalável muito mais elegante e, mas talvez 256 listas de entrada são tão poucos que uma simples comparação poderia ser mais rápido.

Answer 3

Apenas mesclar cada lista com a lista de 128 acima dela. (Resultando em 128 listas)
Em seguida, mesclar cada lista com a lista de 64 acima dela. (Resultando em 64 listas)
Em seguida, mesclar cada lista com a lista de 32 acima dela. (Resultando em 32 listas)
Em seguida, mesclar cada lista com a lista de 16 acima dela. (Resultando em 16 listas)
Em seguida, mesclar cada lista com a lista 8 acima dela. (Resultando em 8 lista)
Em seguida, mesclar cada lista com a lista 4 acima dela. (Resultando em 4 lista)
Em seguida, mesclar cada lista com a lista 2 acima dela. (Resultando em 2 listas)
Em seguida, mesclar cada lista com a lista 1 acima dela. (Resultando em uma lista)
(Você pode usar um loop para o acima).

Answer 4

Você não diz quanto tempo essas listas são, mas presumo que todos eles se encaixam na RAM ao mesmo tempo. A primeira coisa que eu tentaria está anexando-los todos juntos, e chamando rotina embutida tipo de meu ambiente, e eu veria se que deu um desempenho aceitável. É fácil de implementar e não levaria muito tempo para testar. Se isso não deu um desempenho aceitável, eu iria com a fusão fila de prioridade dado por Konrad Rudolph.