Listenimplementierung, die die Reihenfolge aufrechterhält

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

Frage

Gibt es eine vorhandene List Implementierung in Java, die die Reihenfolge basierend auf den bereitgestellten Informationen aufrechterhält Comparator?

Etwas, das auf folgende Weise verwendet werden kann:

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

so dass someT wird so eingefügt, dass die Reihenfolge in der Liste entsprechend beibehalten wird cmp

(Auf Vorschlag von @andersoj ergänze ich meine Frage mit einer weiteren Bitte)

Außerdem möchte ich in der Lage sein, die Liste in sortierter Reihenfolge zu durchlaufen, ohne die Elemente zu entfernen, d. h.:

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

sollte vergehen.

Alle Vorschläge sind willkommen (außer mir zu sagen, dass ich sie verwenden soll). Collections.sort (auf der ungeordneten vollständigen Liste) würde ich jedoch etwas in bevorzugen java.* oder irgendwann org.apache.* da es derzeit schwierig wäre, neue Bibliotheken einzuführen.

Notiz:(UPDATE4) Mir wurde klar, dass Implementierungen dieser Art von Liste eine unzureichende Leistung erbringen würden.Es gibt zwei allgemeine Ansätze:

  1. Verwenden Sie eine verknüpfte Struktur (sozusagen) B-Baum oder ähnliches
  2. Array und Einfügung verwenden (mit binärer Suche)

Nr. 1.hat ein Problem mit CPU -Cache Misse Nr. 2.hat ein Problem mit der Verschiebung von Elementen im Array.

UPDATE2: TreeSet funktioniert nicht, da der bereitgestellte Komparator verwendet wird (MyComparator), um die Gleichheit zu prüfen und auf dieser Grundlage davon auszugehen, dass die Elemente gleich sind, und schließt sie aus.Ich benötige diesen Komparator nur zum Ordnen, nicht zum Filtern nach „Einzigartigkeit“ (da die Elemente aufgrund ihrer natürlichen Reihenfolge nicht gleich sind).

UPDATE3: PriorityQueue Funktioniert nicht als List (wie ich es brauche), da es keine Möglichkeit gibt, es in der Reihenfolge zu durchlaufen, in der es „sortiert“ ist. Um die Elemente in der sortierten Reihenfolge zu erhalten, müssen Sie sie aus der Sammlung entfernen.

AKTUALISIEREN:

Ähnliche Frage:
Eine gute sortierte Liste für Java
Sortierte Array-Liste in Java

War es hilfreich?

Lösung

Reaktion auf neue Anforderungen.Ich sehe zwei Potenziale:

  • Tun Sie, wozu das JavaDoc dient PriorityQueue sagt:

    Diese Klasse und ihr Iterator implementieren alle optionalen Methoden der Collection- und Iterator-Schnittstellen.Der in der Methode bereitgestellte Iterator iterator() Es ist nicht garantiert, dass die Elemente der Prioritätswarteschlange in einer bestimmten Reihenfolge durchlaufen werden.Wenn Sie eine geordnete Durchquerung benötigen, sollten Sie die Verwendung in Betracht ziehen Arrays.sort(pq.toArray()).

    Ich gehe davon aus, dass dies angesichts Ihrer Anforderungen die beste Leistung bringt.Wenn dies nicht akzeptabel ist, müssen Sie besser erklären, was Sie erreichen möchten.

  • Bau ein Aufführen das sortiert sich einfach von selbst, wenn neue Elemente hinzugefügt werden.Das ist ein echter Schmerz...Wenn Sie eine verknüpfte Struktur verwendet haben, können Sie eine effiziente Einfügungssortierung durchführen, aber die Lokalität ist schlecht.Wenn Sie eine Array-gestützte Struktur verwendet haben, ist die Einfügungssortierung mühsam, aber das Durchlaufen ist besser.Wenn die Iteration/Durchquerung selten erfolgt, können Sie die Listeninhalte unsortiert halten und nur bei Bedarf sortieren.

  • Erwägen Sie die Verwendung von a Prioritätswarteschlange Schreiben Sie, wie ich vorgeschlagen habe, und für den Fall, dass Sie der Reihe nach iterieren müssen, einen Wrapper-Iterator:

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

  • Verwenden Sie Guaven TreeMultiSet.Ich habe den folgenden Code mit getestet Integer und es scheint das Richtige zu tun.

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

Das Folgende befasst sich mit dem Eindeutigkeits-/Filterproblem, das Sie bei der Verwendung von a hatten SortedSet.Ich sehe, dass Sie auch einen Iterator wollen, also wird das nicht funktionieren.

Wenn Sie wirklich etwas Bestelltes wollen listenartig Ding, Sie können eine verwenden PriorityQueue. 

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

Beachten Sie, was die API-Dokumentation über die Zeiteigenschaften verschiedener Vorgänge sagt:

Implementierungshinweis:Diese Implementierung bietet O(log(n)) Zeit für die Enqueing- und Dequeing-Methoden (offer, poll, remove() Und add); linear Zeit für die remove(Object) Und contains(Object) Methoden;Und Konstante Zeit für die Abrufmethoden (peek, element, Und size).

Sie sollten sich auch darüber im Klaren sein, dass die von erzeugten Iteratoren PriorityQueue Verhalten Sie sich nicht so, wie man es erwarten würde:

Der Iterator in der Methode bereitgestellt iterator() Es ist nicht garantiert, dass die Elemente der Prioritätswarteschlange in einer bestimmten Reihenfolge durchlaufen werden.Wenn Sie eine geordnete Durchquerung benötigen, sollten Sie die Verwendung in Betracht ziehen Arrays.sort(pq.toArray()).

Mir ist gerade aufgefallen, dass Guava eine bietet MinMaxPriorityQueue.Diese Implementierung basiert auf einem Array und nicht auf der verknüpften Form, die in den JDKs bereitgestellt wird PriorityQueue, und weist daher wahrscheinlich ein unterschiedliches Timing-Verhalten auf.Wenn Sie etwas tun, bei dem es auf die Leistung ankommt, sollten Sie einen Blick darauf werfen.Während die Noten leicht unterschiedliche (lineare und logarithmische) Big-O-Zeiten ergeben, sollten alle diese Zeiten auch begrenzt sein, was nützlich sein kann.

Da ist kein List Implementierung per se, die die Reihenfolge aufrechterhält, aber was Sie wahrscheinlich suchen, sind Implementierungen davon SortedSet.A TreeSet ist am häufigsten.Die andere Implementierung, a ConcurrentSkipListSet ist für spezifischere Zwecke gedacht.Beachten Sie, dass a SortedSet Bietet Ordnung, erlaubt jedoch keine doppelten Einträge, wie z. B. a List.

Refs:

Andere Tipps

Sie sollten wahrscheinlich a verwenden TreeSet:

Die Reihenfolge der Elemente erfolgt anhand ihrer natürlichen Reihenfolge oder durch einen Komparator, der zum festgelegten Erstellungszeitpunkt bereitgestellt wird, je nachdem, welcher Konstruktor verwendet wird.

Beispiel:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

Beachten Sie, dass dies ein ist Satz, daher sind keine doppelten Einträge zulässig.Dies kann für Ihren spezifischen Anwendungsfall funktionieren oder auch nicht.

Ich habe ein ähnliches Problem und denke darüber nach, ein TreeSet zu verwenden.Um zu vermeiden, dass „gleiche“ Elemente ausgeschlossen werden, werde ich den Komparator so ändern, dass er statt 0 eine Zufallszahl zwischen (-1,1) zurückgibt oder immer 1 zurückgibt.

Wenn Sie keine Kontrolle über den Komparator haben oder ihn für etwas anderes als das Einfügen verwenden, wird diese Lösung für Sie nicht funktionieren.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top