Revisión de código Java: combina listas ordenadas en una sola lista ordenada

Question

Quiero fusionar listas ordenadas en una sola lista. ¿Cómo es esta solución? Creo que funciona en O (n) tiempo. ¿Alguna falla flagrante, ineficacia o problemas de estilo?

Realmente no me gusta el modismo de establecer una bandera para "esta es la primera iteración" y usarla para asegurar que "más bajo" tenga un valor predeterminado. ¿Hay una mejor manera de evitar eso?

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) { 
    List<T> result = new ArrayList<T>(); 

    int totalSize = 0; // every element in the set 
    for (List<T> l : lists) { 
     totalSize += l.size(); 
    } 

    boolean first; //awkward 
    List<T> lowest = lists.iterator().next(); // the list with the lowest item to add 

    while (result.size() < totalSize) { // while we still have something to add 
     first = true; 

     for (List<T> l : lists) { 
      if (! l.isEmpty()) { 
       if (first) { 
        lowest = l; 
        first = false; 
       } 
       else if (l.get(0).compareTo(lowest.get(0)) <= 0) { 
        lowest = l; 
       } 
      } 
     } 
     result.add(lowest.get(0)); 
     lowest.remove(0); 
    } 
    return result; 
} 

Nota: esto no es tarea, pero tampoco es para código de producción.

Answer 1

Su solución es probablemente la más rápida. SortedLists tiene un costo de inserción de log (n), por lo que terminará con M log (M) (donde M es el tamaño total de las listas).

Al agregarlos a una lista y ordenar, aunque es más fácil de leer, sigue siendo M log (M).

Su solución es simplemente M.

Usted puede limpiar su código un poco dimensionando la lista de resultados, y mediante el uso de una referencia a la lista más bajo en lugar de un valor lógico.

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) { 
    int totalSize = 0; // every element in the set 
    for (List<T> l : lists) { 
     totalSize += l.size(); 
    } 

    List<T> result = new ArrayList<T>(totalSize); 

    List<T> lowest; 

    while (result.size() < totalSize) { // while we still have something to add 
     lowest = null; 

     for (List<T> l : lists) { 
      if (! l.isEmpty()) { 
       if (lowest == null) { 
        lowest = l; 
       } else if (l.get(0).compareTo(lowest.get(0)) <= 0) { 
        lowest = l; 
       } 
      } 
     } 

     result.add(lowest.get(0)); 
     lowest.remove(0); 
    } 

    return result; 
} 

Si usted está realmente en particular, utilice un objeto de lista como entrada, y la más baja se puede inicializar a ser lists.get (0) y se puede omitir la comprobación nula.

Answer 2

Para ampliar el comentario de Anton:

Al colocar el último resultado de cada lista, junto con un indicador de la apartada lista es, en un montón, entonces continuamente tomar la parte superior de la pila, y poner una nueva elemento en el montón de la lista que pertenece al artículo que acaba de quitar.

PriorityQueue de Java puede proporcionar la implementación del montón.

Answer 3

La eficiencia se absorberá si lists contiene una ArrayList, ya que lowest.remove(0) tomará tiempo lineal en la longitud de la lista, haciendo que su algoritmo O (n^2).

que lo haría:

List<T> result = new ArrayList<T>(); 
for (List<T> list : lists) { 
    result.addAll(list); 
} 
Collections.sort(result); 

que está en O (n log n), y deja de código mucho menos tedioso para probar, depurar y mantener.

Answer 4

Dado que Balus y Meriton juntos han dado una excelente respuesta a su pregunta sobre el algoritmo, hablaré con usted sobre la "primera" expresión idiomática.

Definitivamente hay otros enfoques (como establecer el valor más bajo a 'mágico'), pero sucede que siento que "primero" (a lo que probablemente daré un nombre más largo, pero eso es ser pedante) es el mejor porque es muy claro. La presencia de un booleano como "primero" es una señal clara de que su bucle hará algo especial la primera vez. Ayuda al lector.

Por supuesto que no lo necesita si se toma el enfoque Balus/Meriton, pero es una situación que surge.

Answer 5

Esta es una pregunta muy antigua, pero no me gusta ninguna de las respuestas enviadas, así que esto es lo que terminé haciendo.

La solución de simplemente agregarlos a todos en una lista y clasificación es mala debido a la complejidad lineal del registro.SI eso no es importante para ti, definitivamente es la respuesta más simple y directa. Su solución inicial no está mal, pero es un poco desordenada, y @Dathan señaló que la complejidad es O (m n) para m listas y n elementos totales. Puede reducir esto a O (n log (m)) usando un montón para reducir el número de comparaciones para cada elemento. Utilizo una clase de ayuda que me permite comparar los iterables. De esta forma, no destruyo las listas iniciales, y debería funcionar con una complejidad razonable sin importar qué tipo de listas se ingresen. El único defecto que veo con la implementación a continuación es que no admite listas con elementos null, sin embargo, esto podría solucionarse si así lo desea.

public static <E extends Comparable<? super E>> List<E> merge(Collection<? extends List<? extends E>> lists) { 
    PriorityQueue<CompIterator<E>> queue = new PriorityQueue<CompIterator<E>>(); 
    for (List<? extends E> list : lists) 
     if (!list.isEmpty()) 
      queue.add(new CompIterator<E>(list.iterator())); 

    List<E> merged = new ArrayList<E>(); 
    while (!queue.isEmpty()) { 
     CompIterator<E> next = queue.remove(); 
     merged.add(next.next()); 
     if (next.hasNext()) 
      queue.add(next); 
    } 
    return merged; 
} 

private static class CompIterator<E extends Comparable<? super E>> implements Iterator<E>, Comparable<CompIterator<E>> { 
    E peekElem; 
    Iterator<? extends E> it; 

    public CompIterator(Iterator<? extends E> it) { 
     this.it = it; 
     if (it.hasNext()) peekElem = it.next(); 
     else peekElem = null; 
    } 

    @Override 
    public boolean hasNext() { 
     return peekElem != null; 
    } 

    @Override 
    public E next() { 
     E ret = peekElem; 
     if (it.hasNext()) peekElem = it.next(); 
     else peekElem = null; 
     return ret; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException(); 
    } 

    @Override 
    public int compareTo(CompIterator<E> o) { 
     if (peekElem == null) return 1; 
     else return peekElem.compareTo(o.peekElem); 
    } 

} 

Cada elemento de la lista devuelta implica dos operaciones de lixiviación en O (log (m)), también hay una iteración inicial sobre la totalidad de las listas. Por lo tanto, la complejidad general es O (n log (m) + m) para n elementos totales y m listas. haciendo esto siempre más rápido que concatenar y clasificar.