Listenimplementierung, die die Reihenfolge aufrechterhält
-
12-12-2019 - |
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:
- Verwenden Sie eine verknüpfte Struktur (sozusagen) B-Baum oder ähnliches
- 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
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 ziehenArrays.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 getestetInteger
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()
Undadd
); linear Zeit für dieremove(Object)
Undcontains(Object)
Methoden;Und Konstante Zeit für die Abrufmethoden (peek
,element
, Undsize
).
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 bereitgestelltiterator()
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 ziehenArrays.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:
- Blogeintrag
PriorityQueue
Iterator ist nicht geordnet - ALSO Frage an PQ bestellter Iterator
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.