Classificando conjuntos de listas ligadas ordenados
-
03-07-2019 - |
Pergunta
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.
Solução
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())
Outras dicas
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.
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).
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.