sort - ordenar un array java

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

Como 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 lo 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 toma el enfoque de Balus / meriton, pero es una situación que surge.

Answer 2

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

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 un código mucho menos tedioso para probar, depurar y mantener.

Answer 3

Para ampliar el comentario de Anton:

Al colocar el resultado más reciente de cada Lista, junto con un indicador de la lista, se convierte en un montón, luego saca continuamente la parte superior del montón y coloca un nuevo elemento en el montón de la lista que pertenece al artículo que acabas de tomar apagado.

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

Answer 4

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 sola 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 es mala, pero es un poco desordenada, y @Dathan señaló que la complejidad es O (mn) para m listas yn 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 pila O (log (m)), también hay una iteración inicial sobre todas 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.

Answer 5

Tu 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).

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

Tu solución es solo M.

Puede limpiar su código un poco al dimensionar la lista de resultados, y al usar una referencia a la lista más baja en lugar de una booleana.

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 es realmente particular, use un objeto List como entrada, y lo más bajo se puede inicializar para ser lists.get (0) y puede omitir la verificación nula.