Elenco di attuazione che mantenendo l'ordine

StackOverflow https://stackoverflow.com//questions/10675446

Domanda

C'è un esistente List implementazione in Java che mantiene l'ordine in base forniti Comparator?

Qualcosa che può essere utilizzato nel modo seguente:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

in modo che someT viene inserito in modo che l'ordine in lista è effettuata secondo cmp

(Su @andersoj suggerimento sto completando la mia domanda con la richiesta di un altro)

Anche io voglio essere in grado di scorrere l'elenco in modo ordinato senza rimuovere gli elementi, mi.e:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

deve passare.

Tutti i suggerimenti sono i benvenuti (tranne che mi dice di usare Collections.sort sul non ordinato l'elenco completo), però, io preferirei qualcosa in java.* o, infine, org.apache.* dal momento che sarebbe difficile introdurre nuove librerie in questo momento.

Nota:(UPDATE4) Ho capito che le implementazioni di questo tipo di lista avrebbe prestazioni inadeguate.Ci sono due approcci generali:

  1. Utilizzare la struttura Collegata sorta di B-tree o simili
  2. Utilizzare la matrice e l'inserimento (con la ricerca binaria)

N.1.si è verificato un problema con la cache della CPU manca N.2.si è verificato un problema con il passaggio di elementi nella matrice.

UPDATE2: TreeSet non funziona perché utilizza la condizione di confronto (MyComparator) per verificare l'uguaglianza e basato su di esso presuppone che gli elementi sono uguali e li escludono.Ho bisogno che comparatore solo per l'ordine, non "unicità" del filtro (dato che gli elementi dalla loro naturale ordine non sono uguali)

Su update3: PriorityQueue non funziona come List (come ho bisogno), perché non c'è modo di attraversare in ordine è "ordinato", per ottenere gli elementi in modo ordinato si possono rimuovere dalla raccolta.

AGGIORNAMENTO:

Domanda simile:
Un buon Elenco Ordinato per Java
Array ordinato lista in Java

È stato utile?

Soluzione

Risposta al nuovo requisito.Vedo due potenzialità:

  • Fare ciò che JavaDoc PriorityQueue dice:

    Questa classe e la sua iteratore di implementare tutti i metodi alternativi di Raccolta e Iteratore interfacce.L'Iteratore fornito nel metodo iterator() non è garantito per attraversare gli elementi della coda di priorità in alcun ordine particolare.Se hai bisogno di ordinare l'attraversamento, considerare l'utilizzo di Arrays.sort(pq.toArray()).

    Ho il sospetto che questo consente di ottenere le migliori prestazioni, dato le vostre esigenze.Se questo non è accettabile, è necessario spiegare meglio che cosa stai cercando di realizzare.

  • Costruire un Elenco che semplicemente ordina stesso con l'aggiunta di nuovi elementi.Questo è un vero e proprio dolore...se è stata utilizzata una struttura collegata, è possibile effettuare un efficace inserimento sorta, ma la località è male.Se si è utilizzata una matrice-sostenuta struttura, ordinamento per inserzione è un dolore, ma l'attraversamento è meglio.Se iterazione/attraversamento non è frequente, si potrebbe tenere il contenuto di un elenco non ordinato e ordina solo su richiesta.

  • Considerare l'utilizzo di un PriorityQueue come ho suggerito, e nel caso in cui è necessario scorrere in ordine, scrivere un wrapper iteratore:

    class PqIter implements Iterator<T>
{
   final PriorityQueue<T> pq;
   public PqIter(PriorityQueue <T> source)
   {
     pq = new PriorityQueue(source); 
   }

   @Override
   public boolean hasNext()
   {
     return pq.peek() != null
   }

   @Override
   public T next()
   { return pq.poll(); }

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

  • Utilizzare Guava s TreeMultiSet.Ho provato il seguente codice Integer e sembra di fare la cosa giusta.

    import com.google.common.collect.TreeMultiset;

public class TreeMultiSetTest { 
  public static void main(String[] args) {
    TreeMultiset<Integer> ts = TreeMultiset.create();
    ts.add(1);  ts.add(0); ts.add(2);
    ts.add(-1); ts.add(5); ts.add(2);

    for (Integer i : ts) {
      System.out.println(i);
    } 
  } 
}

Al di sotto di indirizzi di unicità/filtro problema si ripresenta quando si utilizza un SortedSet.Vedo che anche voi volete un iteratore, in modo che questo non funziona.

Se ciò che si vuole veramente è un ordine elenco-come cosa si può fare uso di un PriorityQueue. 

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

Prendere nota di ciò che la documentazione delle API dice circa il tempo di proprietà delle varie operazioni:

Attuazione nota:questa implementazione fornisce O(log(n)) tempo per il enqueing e dequeing metodi (offer, poll, remove() e add); lineare il tempo per la remove(Object) e contains(Object) metodi;e costante il tempo per il recupero dei metodi (peek, element, e size).

Si dovrebbe anche essere consapevoli del fatto che gli iteratori prodotto da PriorityQueue non si comportano come ci si potrebbe aspettare:

Il Iterator fornito nel metodo iterator() non è garantito per attraversare gli elementi della coda di priorità in alcun ordine particolare.Se hai bisogno di ordinare l'attraversamento, considerare l'utilizzo di Arrays.sort(pq.toArray()).

Ho appena notato che Guava fornisce un MinMaxPriorityQueue.Questa implementazione è di matrice-sostenuta, piuttosto che collegato apposito modulo JDK PriorityQueue, e quindi è probabile che ha diversi tempi di comportamento.Se si sta facendo qualcosa di prestazioni sensibili, si potrebbe desiderare di dare un'occhiata.Mentre le note danno leggermente diverso (lineare e logaritmica), big-O volte, tutte quelle volte che dovrebbero essere delimitata, che può essere utile.

Non c'è un List implementazione di per sé che mantiene l'ordine, ma quello che si sono probabilmente alla ricerca di implementazioni di SortedSet.Un TreeSet è il più comune.L'altra implementazione, un ConcurrentSkipListSet è per più usi specifici.Nota che un SortedSet fornisce ordine, ma non consente di voci duplicate, come un List.

Rif:

Altri suggerimenti

Ho un problema simile e sto pensando di usare un trending.Per evitare di escludere elementi "uguali", modificherò il comparatore, quindi invece di restituire 0 restituirà un numero casuale tra (-1,1) o restituirà sempre 1.

Se non hai alcun controllo sul comparatore o se lo stai usando per qualcos'altro diverso dall'inserimento di questa soluzione non funzionerà per te.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top