Revisione codice Java: Unisci elenchi ordinati in un unico elenco ordinato

Question

Voglio unire elenchi ordinati in un unico elenco. Come è questa soluzione? Credo che funzioni nel tempo O (n). Eventuali difetti evidenti, inefficienze o problemi stilistici?

Non mi piace l'idioma di impostare un flag per "questa è la prima iterazione" e usarlo per assicurarsi che "più basso" abbia un valore predefinito. C'è un modo migliore per aggirare questo?

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: non si tratta di compiti a casa, ma nemmeno del codice di produzione.

Answer 1

La soluzione è probabilmente la più veloce. Le liste ordinate hanno un costo di inserzione di log (n), quindi finirai con M log (M) (dove M è la dimensione totale degli elenchi).

Aggiungendoli a una lista e ordinando, mentre è più facile da leggere, è ancora M log (M).

La soluzione è solo M.

Si può ripulire il codice un po 'dal dimensionamento della lista dei risultati, e utilizzando un riferimento alla lista più basso al posto di un valore booleano.

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

Se siete veramente particolare, utilizzare un oggetto List come input, e più basso può essere inizializzato da lists.get (0) e si può ignorare il controllo nullo.

Answer 2

Per espandere il commento di Anton:

Inserendo l'ultimo risultato da ogni lista, insieme a un indicatore di whch lista che è, in un mucchio, poi continuamente prendere la parte superiore al mucchio, e mettere una nuova elemento sull'heap dalla lista che appartiene all'oggetto appena decollato.

PriorityQueue di Java può fornire l'implementazione dell'heap.

Answer 3

L'efficienza fa schifo se lists contiene un oggetto Array, poiché lowest.remove(0) impiegherà tempo lineare nella lunghezza dell'elenco, rendendo l'algoritmo O (n^2).

farei:

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

che è in O (n log n), e lascia il codice molto meno noioso per testare, eseguire il debug e mantenere.

Answer 4

Poiché Balus e Meriton hanno dato una risposta eccellente alla tua domanda sull'algoritmo, parlerò del tuo "primo" idioma.

Ci sono sicuramente altri approcci (come l'impostazione più bassa ad un valore "magico"), ma mi capita di sentire che "primo" (a cui probabilmente darei un nome più lungo, ma che è pedante) è il migliore perché è molto chiaro La presenza di un booleano come "primo" è un chiaro segnale che il tuo loop farà qualcosa di speciale la prima volta. Aiuta il lettore.

Naturalmente non ne hai bisogno se prendi l'approccio Balus/meriton, ma è una situazione che si presenta.

Answer 5

Questa è una domanda molto vecchia, ma non mi piace nessuna delle risposte inviate, quindi questo è quello che ho finito per fare.

La soluzione di aggiungerli tutti in un unico elenco e l'ordinamento non è buona a causa della complessità lineare del registro.Se questo non è importante per te, allora è sicuramente la risposta più semplice e diretta. La tua soluzione iniziale non è male, ma è un po 'caotica, e @Dathan ha sottolineato che la complessità è O (m n) per m liste e n elementi totali. È possibile ridurre questo valore a O (n log (m)) utilizzando un heap, quindi ridurre il numero di confronti per ciascun elemento. Uso una classe di supporto che mi consente di confrontare i valori iterabili. In questo modo non distruggo gli elenchi iniziali e dovrebbe operare con una ragionevole complessità, indipendentemente dal tipo di elenchi inseriti. L'unico difetto che vedo con l'implementazione di seguito è che non supporta elenchi con elementi null, tuttavia questo potrebbe essere risolto se lo si desidera.

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

} 

Ogni elemento della lista restituita coinvolge due operazioni heap O (log (m)), v'è anche un'iterazione iniziale su tutte le liste. Pertanto la complessità complessiva è O (n log (m) + m) per n elementi totali e m liste. rendendolo sempre più veloce della concatenazione e dell'ordinamento.