Ordenar conjuntos de listas enlazadas ordenadas

Question

Estoy buscando una solución elegante y de alto rendimiento para el siguiente problema.

Hay 256 listas enlazadas.

• Cada lista contiene los mismos tipos de objeto que, entre otras cosas, contiene un número entero que se utiliza para definir un orden de clasificación.
• Todos los números en todas las listas son únicos
• Cada lista individual está ordenada en orden ascendente por estos números

¿Cómo crearía una sola lista ordenada ascendente de todos los objetos de las 256 listas vinculadas originales? Preferiría no atacarlo con fuerza bruta y tener algunas otras ideas, pero este parece ser uno de esos problemas para los que existe una solución estándar y óptima.

Answer 1

Podría usar una cola de prioridad que contenga el elemento "más alto" de cada una de las 256 listas vinculadas. Este elemento "superior" es el que está programado para insertarse en la lista resultante. De esta manera, puede tomar el elemento más pequeño de la cola de prioridad, insertarlo en la cola resultante e insertar su siguiente elemento en la cola de prioridad:

# 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

si las listas individuales ya están ordenadas, entonces es una aplicación directa del algoritmo de combinación . en resumen: compare todas las cabezas y elija las más pequeñas, sáquelas de la lista y empújelas en su lista de resultados. repita hasta que todas las listas de fuentes estén vacías.

editar: el uso de Konrad de una cola de prioridad (un heap ) es una Una solución mucho más elegante y escalable, pero tal vez 256 listas de entrada son tan pocas que una simple comparación podría ser más rápida.

Answer 3

Simplemente fusione cada lista con la lista 128 arriba. (resultando en 128 listas)
Luego fusiona cada lista con la lista 64 arriba. (resultando en 64 listas)
Luego fusiona cada lista con la lista 32 arriba. (resultando en 32 listas)
Luego fusiona cada lista con la lista 16 arriba. (resultando en 16 listas)
Luego fusiona cada lista con la lista 8 arriba. (resultando en 8 listas)
Luego fusiona cada lista con la lista 4 arriba. (resultando en 4 listas)
Luego fusiona cada lista con la lista 2 arriba. (resultando en 2 listas)
Luego fusiona cada lista con la lista 1 arriba. (resultando en 1 lista)
(Podría usar un bucle para lo anterior).

Answer 4

No dice cuánto duran estas listas, pero supongo que todas caben en la RAM al mismo tiempo. Lo primero que intentaría es agregarlos a todos, y llamar a la rutina de ordenación integrada de mi entorno, y vería si eso daba un rendimiento aceptable. Es fácil de implementar y no tardaría mucho en probarse. Si eso no proporcionara un rendimiento aceptable, iría con la fusión de cola prioritaria dada por Konrad Rudolph.