Java Code Review: Sortieren Sie sortierte Listen in eine einzige sortierte Liste

Question

Ich möchte sortierte Listen in eine einzige Liste zusammenführen. Wie ist diese Lösung? Ich glaube, es läuft in O (n) Zeit. Irgendwelche eklatanten Mängel, Ineffizienzen oder stilistische Probleme?

Ich mag nicht das Idiom der Einstellung eines Flags für "das ist die erste Iteration" und verwenden, um sicherzustellen, dass "niedrigste" einen Standardwert hat. Gibt es einen besseren Weg?

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; 
} 

Hinweis: Dies ist keine Hausaufgabe, aber es ist auch nicht für den Produktionscode.

Answer 1

Ihre Lösung ist wahrscheinlich die schnellste. SortedLists haben Einfügekosten von log (n), so dass Sie mit M log (M) enden (wobei M die Gesamtgröße der Listen ist).

Hinzufügen sie zu einer Liste und Sortierung, während einfacher zu lesen, ist immer noch M log (M).

Ihre Lösung ist nur M.

Sie können den Code ein bisschen durch Dimensionierung der Ergebnisliste aufzuräumen, und durch einen Verweis auf die niedrigste Liste anstelle eines boolean verwenden.

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; 
} 

Wenn Sie wirklich besonders sind, ein List-Objekt als Eingabe verwenden, und die niedrigste initialisiert werden kann, um lists.get (0), und Sie können die Nullprüfung überspringen.

Answer 2

auf Antons Kommentar zu erweitern:

von aus jeder Liste das letzte Ergebnis platzieren, zusammen mit einem Indikatoren für whch Liste ist es, in einen Haufen, dann die oberen ständig nimmt einen neuen die Haufen, und beiseite legen Element auf dem Heap aus der Liste, die zu dem gerade entfernten Objekt gehört.

Die PriorityQueue von Java kann die Heap-Implementierung bereitstellen.

Answer 3

Effizienz wird saugen, wenn lists enthält eine ArrayList, da lowest.remove(0) lineare Zeit in der Länge der Liste nehmen wird, wodurch Ihr Algorithmus O (n^2).

ich tun würde:

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

die (n log n) in O ist, und lässt Debug weit weniger langweilig Code zu testen und zu warten.

Answer 4

Da Balus und Meriton zusammen eine ausgezeichnete Antwort auf Ihre Frage nach dem Algorithmus gegeben haben, werde ich zu Ihrer Seite über das "erste" Idiom sprechen.

Es gibt definitiv andere Ansätze (wie Einstellung am niedrigsten zu einem "magischen" Wert), aber ich fühle, dass "zuerst" (zu dem ich wahrscheinlich einen längeren Namen geben würde, aber das ist pedantisch) ist das Beste weil es sehr klar ist. Das Vorhandensein eines booleschen Wertes wie "first" ist ein klares Signal, dass Ihre Schleife beim ersten Mal etwas Spezielles tut. Es hilft dem Leser.

Natürlich brauchen Sie es nicht, wenn Sie den Balus/Meriton-Ansatz nehmen, aber es ist eine Situation, die auftaucht.

Answer 5

Dies ist eine wirklich alte Frage, aber ich mag keine der eingereichten Antworten, also ist es das, was ich getan habe.

Die Lösung, sie alle nur in eine Liste aufzunehmen und zu sortieren, ist wegen der linearen Komplexität des Protokolls schlecht.WENN das für dich nicht wichtig ist, dann ist es definitiv die einfachste und direkteste Antwort. Ihre anfängliche Lösung ist nicht schlecht, aber es ist ein wenig unordentlich und @Dathan wies darauf hin, dass die Komplexität O (m n) für m Listen und n Gesamtelemente ist. Sie können dies auf O (n log (m)) reduzieren, indem Sie einen Heap verwenden, um die Anzahl der Vergleiche für jedes Element zu reduzieren. Ich benutze eine Hilfsklasse, die es mir erlaubt, Iterables zu vergleichen. Auf diese Weise zerstöre ich die anfänglichen Listen nicht und sie sollte mit angemessener Komplexität arbeiten, egal welche Art von Listen eingegeben werden. Der einzige Fehler, den ich bei der Implementierung unten sehe, ist, dass es keine Listen mit null Elementen unterstützt, dies könnte jedoch auf Wunsch korrigiert werden.

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); 
    } 

} 

Jedes Element der zurückgegebenen Liste beinhaltet zwei O (log (m)) Heap-Operationen, da über alle Listen auch eine erste Iteration ist. Daher ist die Gesamtkomplexität O (n log (m) + m) für n Gesamtelemente und m Listen. Dies ist immer schneller als Verketten und Sortieren.