Ich bin verblüfft, dass ich darauf keine schnelle Antwort finden kann. Ich suche im Wesentlichen nach einer Datenstruktur in Java, die die java.util.List
Schnittstelle implementiert , aber ihre Mitglieder in einer sortierten Reihenfolge speichert. Ich weiß, dass Sie ein normales verwenden ArrayList
und es verwenden Collections.sort()
können, aber ich habe ein Szenario, in dem ich gelegentlich Mitglieder zu meiner Liste hinzufüge und diese häufig abrufe, und ich möchte es nicht jedes Mal sortieren müssen, wenn ich ein Mitglied abrufe, falls a neue wurde hinzugefügt. Kann mich jemand auf so etwas hinweisen, das im JDK oder sogar in Bibliotheken von Drittanbietern existiert?
EDIT : Die Datenstruktur müssen Duplikate bewahren.
ANTWORT ZUSAMMENFASSUNG : Ich fand das alles sehr interessant und habe viel gelernt. Insbesondere Aioobe verdient Erwähnung für seine Beharrlichkeit bei dem Versuch, meine oben genannten Anforderungen zu erfüllen (hauptsächlich eine sortierte Implementierung von java.util.List, die Duplikate unterstützt). Ich habe seine Antwort als die genaueste für das akzeptiert, was ich gefragt habe, und am meisten zum Nachdenken über die Auswirkungen dessen, wonach ich gesucht habe, auch wenn das, was ich gefragt habe, nicht genau das war, was ich brauchte.
Das Problem mit dem, wonach ich gefragt habe, liegt in der List-Schnittstelle selbst und dem Konzept optionaler Methoden in einer Schnittstelle. Um den Javadoc zu zitieren:
Der Benutzer dieser Schnittstelle hat eine genaue Kontrolle darüber, wo in der Liste jedes Element eingefügt wird.
Das Einfügen in eine sortierte Liste hat keine genaue Kontrolle über die Einfügemarke. Dann müssen Sie sich überlegen, wie Sie mit einigen Methoden umgehen werden. Nehmen Sie add
zum Beispiel:
public boolean add (Objekt o)
Appends the specified element to the end of this list (optional operation).
Sie befinden sich jetzt in der unangenehmen Situation, entweder 1) den Vertrag zu brechen und eine sortierte Version von add zu implementieren. 2) add
ein Element am Ende der Liste hinzufügen zu lassen, Ihre sortierte Reihenfolge zu brechen. 3 add
) durch Werfen auszulassen (optional) ein UnsupportedOperationException
und ein anderes Verfahren implementiert , welche Elemente in einer sortierten Reihenfolge hinzufügt.
Option 3 ist wahrscheinlich die beste, aber ich finde es unappetitlich, eine Add-Methode zu haben, die Sie nicht verwenden können, und eine andere sortierte Add-Methode, die nicht in der Benutzeroberfläche enthalten ist.
Andere verwandte Lösungen (in keiner bestimmten Reihenfolge):
- java.util.PriorityQueue, die wahrscheinlich dem am nächsten kommt, was ich brauchte, als das, wonach ich gefragt habe. Eine Warteschlange ist in meinem Fall nicht die genaueste Definition einer Sammlung von Objekten, aber funktional macht sie alles, was ich brauche.
- net.sourceforge.nite.util.SortedList . Diese Implementierung bricht jedoch den Vertrag der List-Schnittstelle, indem sie die Sortierung in der
add(Object obj)
Methode implementiert , und hat bizarrerweise eine Methode ohne Auswirkung füradd(int index, Object obj)
. Allgemeiner Konsens legt nahe,throw new UnsupportedOperationException()
dass in diesem Szenario eine bessere Wahl sein könnte. - Guavas TreeMultiSet Eine Set-Implementierung, die Duplikate unterstützt
- ca.odell.glazedlists.SortedList Diese Klasse enthält die Einschränkung in ihrem Javadoc:
Warning: This class breaks the contract required by List
quelle
Antworten:
Minimalistische Lösung
Hier ist eine "minimale" Lösung.
Das Einfügen wird in linearer Zeit ausgeführt, aber das würden Sie ohnehin mit einer ArrayList erhalten (alle Elemente rechts vom eingefügten Element müssten in die eine oder andere Richtung verschoben werden).
Das Einfügen von nicht vergleichbaren Ergebnissen führt zu einer ClassCastException. (Dies ist auch der Ansatz von
PriorityQueue
: Eine Prioritätswarteschlange, die auf natürlicher Reihenfolge beruht, erlaubt auch nicht das Einfügen nicht vergleichbarer Objekte (dies kann zu ClassCastException führen). )Überschreiben
List.add
Beachten Sie, dass das Überschreiben
List.add
(oder auchList.addAll
das Sortieren) zum sortierten Einfügen von Elementen eine direkte Verletzung der Schnittstellenspezifikation darstellt . Was Sie tun könnten , ist, diese Methode zu überschreiben, um eine zu werfenUnsupportedOperationException
.Aus den Dokumenten von
List.add
:Die gleiche Begründung gilt für beide Versionen von
add
, beide Versionen vonaddAll
undset
. (All dies sind optionale Operationen gemäß der Listenschnittstelle.)Einige Tests
.... druckt:
quelle
The user of this interface has precise control over where in the list each element is inserted
ist nicht die beste Beschreibung zum sortierten Einfügen von Elementen, und Sie müssen sich immer noch mit deradd(int index, Object obj)
Schnittstellenmethode befassen . Diese Probleme erklären wahrscheinlich, warum List nicht sortiert implementiert wurde..add
einer SortedArrayList eine UnsupportedExceptionOperation erhalten würde. Ja, die gleiche Begründung gilt für beide Versionen von add, beide Versionen von addAll und set. (All dies sind optionale Operationen gemäß derVerwenden Sie
java.util.PriorityQueue
.quelle
Schauen Sie sich SortedList an
quelle
addAll()
alle Elemente sortiert verwendet und denkt. Stimmen Sie auch der UnsupportedOperationException zu.Sie können versuchen , Guava des TreeMultiSet .
quelle
A collection that supports order-independent equality, like Set, but may have duplicate elements
Aioobes Ansatz ist der richtige Weg. Ich möchte jedoch die folgende Verbesserung gegenüber seiner Lösung vorschlagen.
Die Lösung von aioobe wird bei Verwendung großer Listen sehr langsam. Durch die Verwendung der sortierten Liste können wir den Einfügepunkt für neue Werte mithilfe der binären Suche finden.
Ich würde auch Komposition über Vererbung verwenden, etwas in der Art von
quelle
Listen behalten normalerweise die Reihenfolge bei, in der Elemente hinzugefügt werden. Benötigen Sie definitiv eine Liste oder wäre ein sortiertes Set (zB
TreeSet<E>
) für Sie in Ordnung? Müssen Sie grundsätzlich Duplikate aufbewahren?quelle
Es ist vielleicht etwas zu schwer für Sie, aber GlazedLists verfügt über eine SortedList , die sich perfekt als Modell für eine Tabelle oder JList eignet
quelle
Sie können ArrayList in eine Unterklasse unterteilen und Collections.sort (this) aufrufen, nachdem ein Element hinzugefügt wurde. Dazu müssten Sie zwei Versionen von add und zwei von addAll überschreiben.
Die Leistung wäre nicht so gut wie eine intelligentere Implementierung, bei der Elemente an der richtigen Stelle eingefügt wurden, aber sie würde den Job erledigen. Wenn das Hinzufügen zur Liste selten ist, sollten die über alle Vorgänge auf der Liste amortisierten Kosten niedrig sein.
quelle
Erstelle einfach eine neue Klasse wie diese:
Sie können es so testen:
quelle
Ich denke, die Wahl zwischen SortedSets / Lists und 'normalen' sortierbaren Sammlungen hängt davon ab, ob Sie nur zu Präsentationszwecken oder zu fast jedem Zeitpunkt zur Laufzeit sortieren müssen. Die Verwendung einer sortierten Sammlung kann viel teurer sein, da die Sortierung jedes Mal erfolgt, wenn Sie ein Element einfügen.
Wenn Sie sich im JDK nicht für eine Sammlung entscheiden können, können Sie sich die Apache Commons-Sammlungen ansehen
quelle
Da die derzeit vorgeschlagenen Implementierungen, die eine sortierte Liste durch Aufheben der Sammlungs-API implementieren, eine eigene Implementierung eines Baums oder ähnliches haben, war ich neugierig, wie eine Implementierung auf der Basis der TreeMap funktionieren würde. (Insbesondere, da das TreeSet auch auf TreeMap basiert)
Wenn sich auch jemand dafür interessiert, kann er oder sie sich gerne darum kümmern:
Baumstruktur
Es ist Teil der Kernbibliothek und kann natürlich über die Maven-Abhängigkeit hinzugefügt werden. (Apache-Lizenz)
Derzeit scheint sich die Implementierung auf derselben Ebene wie die Guave SortedMultiSet und die TreeList der Apache Commons-Bibliothek recht gut zu vergleichen.
Aber ich würde mich freuen, wenn mehr als nur ich die Implementierung testen würde, um sicherzugehen, dass ich nichts Wichtiges verpasst habe.
Freundliche Grüße!
quelle
Ich hatte das gleiche Problem. Also nahm ich den Quellcode von java.util.TreeMap und schrieb IndexedTreeMap . Es implementiert meine eigene IndexedNavigableMap :
Die Implementierung basiert auf der Aktualisierung der Knotengewichte im rot-schwarzen Baum, wenn diese geändert werden. Das Gewicht ist die Anzahl der untergeordneten Knoten unter einem bestimmten Knoten plus eins. Zum Beispiel, wenn ein Baum nach links gedreht wird:
updateWeight aktualisiert einfach die Gewichte bis zur Wurzel:
Und wenn wir das Element anhand des Index finden müssen, ist hier die Implementierung, die Gewichte verwendet:
Es ist auch sehr praktisch, den Index eines Schlüssels zu finden:
Das Ergebnis dieser Arbeit finden Sie unter http://code.google.com/p/indexed-tree-map/
TreeSet / TreeMap (sowie deren indizierte Gegenstücke aus dem Projekt "Indexed Tree Map") erlauben keine doppelten Schlüssel. Sie können 1 Schlüssel für ein Array von Werten verwenden. Wenn Sie ein SortedSet mit Duplikaten benötigen, verwenden Sie TreeMap mit Werten als Arrays. Ich würde das tun.
quelle