Warum gibt es in Java keine SortedList?

503

In Java gibt es die SortedSetund SortedMapSchnittstellen. Beide gehören zum Java Collections-Framework und bieten eine sortierte Möglichkeit, auf die Elemente zuzugreifen.

Nach meinem Verständnis gibt es jedoch kein SortedListJava. Sie können java.util.Collections.sort()eine Liste sortieren.

Irgendeine Idee, warum es so gestaltet ist?

Jijoy
quelle
6
Was ist Ihr erwartetes Ergebnis, wenn Sie ein Element in die Mitte der Liste einfügen?
Bests
4
@bestsss Es wäre durchaus möglich, eine SortedList-Klasse zu haben, die die Schnittstelle java.util.List nicht implementiert. Lesen Sie die Frage als Anfrage, warum es keine Datenstruktur gibt, die die angeforderte Funktionalität unterstützt. Lassen Sie sich nicht von unbedeutenden Details wie der Benennung ablenken.
Alderath
@Alderath, die übliche Struktur hierfür ist ein Baum (rot / schwarz, avl oder btree) mit zusätzlichen vorherigen / nächsten Links zur Unterstützung der Bestellung. Ich benutze ähnliche Struktur rot / schwarz w / prev / next Links. Es ist jedoch eine ziemlich Nischenanwendung. Der Baum kann sowohl geordnet als auch Einfügereihenfolge durchlaufen werden, hat O (logn) find / enthält, aber get (int) ist O (n). Angesichts der Nischenanwendbarkeit würde ich davon ausgehen, dass es den Entwicklern überlassen war, bei Bedarf eine zu implementieren.
Bests
3
Die Frage "Warum" wird nicht beantwortet, aber die einfachste Problemumgehung für TreeSet besteht darin, einen Komparator zu verwenden, der niemals Null zurückgibt, z int diff = this.score - that.score; return (diff == 0) ? 1 : diff; .
Earcam

Antworten:

682

Listeniteratoren garantieren in erster Linie, dass Sie die Elemente der Liste in der internen Reihenfolge der Liste (auch bekannt als Einfügereihenfolge ) erhalten. Genauer gesagt in der Reihenfolge, in der Sie die Elemente eingefügt haben oder wie Sie die Liste bearbeitet haben. Das Sortieren kann als Manipulation der Datenstruktur angesehen werden, und es gibt verschiedene Möglichkeiten, die Liste zu sortieren.

Ich werde die Wege in der Reihenfolge ihrer Nützlichkeit ordnen, wie ich es persönlich sehe:

1. Erwägen Sie stattdessen die Verwendung von Setoder BagSammlungen

HINWEIS: Ich habe diese Option oben platziert, da Sie dies normalerweise sowieso tun möchten.

Ein sortierter Satz sortiert die Sammlung beim Einfügen automatisch. Dies bedeutet, dass die Sortierung durchgeführt wird, während Sie der Sammlung Elemente hinzufügen. Dies bedeutet auch, dass Sie es nicht manuell sortieren müssen.

Wenn Sie sicher sind, dass Sie sich keine Gedanken über doppelte Elemente machen müssen (oder haben), können Sie TreeSet<T>stattdessen das verwenden. Es implementiert SortedSetund NavigableSetverbindet und funktioniert so, wie Sie es wahrscheinlich von einer Liste erwarten würden:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Wenn Sie die natürliche Reihenfolge nicht möchten, können Sie den Konstruktorparameter verwenden, der a akzeptiert Comparator<T>.

Alternativ Sie können Multimengen (auch bekannt als Beutel ) , das ist eine , Setdie doppelten Elemente erlaubt es , statt und es gibt Drittanbieter - Implementierungen von ihnen. Vor allem aus den Guava-Bibliotheken gibt es eine TreeMultiset, die sehr ähnlich funktioniert wie die TreeSet.

2. Sortieren Sie Ihre Liste mit Collections.sort()

Wie oben erwähnt, ist das Sortieren von Lists eine Manipulation der Datenstruktur. In Situationen, in denen Sie "eine Quelle der Wahrheit" benötigen, die auf verschiedene Arten sortiert wird, ist das manuelle Sortieren der richtige Weg.

Sie können Ihre Liste mit der java.util.Collections.sort()Methode sortieren . Hier ist ein Codebeispiel, wie:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Komparatoren verwenden

Ein klarer Vorteil ist, dass Sie Comparatorin der sortMethode verwenden können. Java bietet auch einige Implementierungen für Comparatorsolche, wie z. B. die, Collatordie für länderspezifische Sortierzeichenfolgen nützlich sind. Hier ist ein Beispiel:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Sortieren in gleichzeitigen Umgebungen

Beachten Sie jedoch, dass die Verwendung der sortMethode in gleichzeitigen Umgebungen nicht benutzerfreundlich ist, da die Sammlungsinstanz manipuliert wird und Sie stattdessen die Verwendung unveränderlicher Sammlungen in Betracht ziehen sollten. Dies ist etwas, was Guava in der OrderingKlasse bietet und ist ein einfacher Einzeiler:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Wickeln Sie Ihre Liste mit ein java.util.PriorityQueue

Obwohl es in Java keine sortierte Liste gibt, gibt es eine sortierte Warteschlange, die wahrscheinlich genauso gut für Sie funktionieren würde. Es ist die java.util.PriorityQueueKlasse.

Nico Haase hat in den Kommentaren eine verwandte Frage verlinkt , die auch diese beantwortet.

In einer sortierten Sammlung möchten Sie höchstwahrscheinlich die interne Datenstruktur nicht manipulieren, weshalb PriorityQueue die List-Schnittstelle nicht implementiert (da Sie dadurch direkten Zugriff auf ihre Elemente erhalten).

Vorsichtsmaßnahme für den PriorityQueueIterator

Die PriorityQueueKlasse implementiert die Schnittstellen Iterable<E>und Collection<E>, sodass sie wie gewohnt iteriert werden kann. Es ist jedoch nicht garantiert, dass der Iterator Elemente in der sortierten Reihenfolge zurückgibt. Stattdessen müssen Sie (wie Alderath in den Kommentaren hervorhebt) in poll()die Warteschlange gestellt werden, bis sie leer ist.

Beachten Sie, dass Sie eine Liste über den Konstruktor, der eine beliebige Sammlung akzeptiert, in eine Prioritätswarteschlange konvertieren können :

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Schreiben Sie Ihre eigene SortedListKlasse

HINWEIS: Sie sollten dies nicht tun müssen.

Sie können Ihre eigene List-Klasse schreiben, die jedes Mal sortiert wird, wenn Sie ein neues Element hinzufügen. Dies kann abhängig von Ihrer Implementierung ziemlich rechenintensiv werden und ist aus zwei Hauptgründen sinnlos , es sei denn, Sie möchten es als Übung ausführen:

  1. Es bricht den Vertrag, den die List<E>Schnittstelle hat, weil die addMethoden sicherstellen sollten, dass sich das Element in dem vom Benutzer angegebenen Index befindet.
  2. Warum das Rad neu erfinden? Sie sollten stattdessen das TreeSet oder Multisets verwenden, wie im ersten Punkt oben ausgeführt.

Wenn Sie dies jedoch als Übung ausführen möchten, verwenden Sie hier ein Codebeispiel, um den Einstieg zu erleichtern. Es wird die AbstractListabstrakte Klasse verwendet:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Beachten Sie , wenn Sie die Methoden nicht außer Kraft gesetzt haben , Sie benötigen, dann von dem Standardimplementierungen AbstractListwerfen UnsupportedOperationExceptions.

Spoike
quelle
12
+1. Imo, das ist konstruktiver als die am besten gewählte Antwort. Es hat jedoch zwei kleinere Nachteile. Die PriorityQueue unterstützt keinen Direktzugriff. Sie können nicht peek (elementIndex). Sie können also zB nicht tun Integer maxVal = prioQueue.peek(prioQueue.size() - 1);. Zweitens, wenn Sie beabsichtigen, die PriorityQueue einfach als sortierte Liste zu verwenden, klingt es weniger intuitiv, PriorityQueueim Code zu sehen SortedList, als es gewesen wäre , wenn eine solche Datenstruktur existiert hätte.
Alderath
12
Und nachdem Sie sich die andere Frage angesehen haben, die jemand in den Kommentaren verlinkt hat, besteht ein weiterer großer Nachteil darin, dass dem Iterator von PriorityQueue nicht garantiert wird, dass er Elemente in einer bestimmten Reihenfolge zurückgibt. Wenn ich also nichts übersehen habe, besteht die einzige Möglichkeit, z. B. alle Objekte in der PriorityQueue zu drucken, darin, die Warteschlange wiederholt abzufragen (), bis sie leer ist. Für mich fühlt sich das grenzwertig neu an. Um die Objekte in einer PriorityQueue zweimal zu drucken, müssen Sie zuerst die PriorityQueue kopieren und dann alle Objekte aus der ursprünglichen PriorityQueue abfragen () und dann alle Objekte aus der Kopie pol () l.
Alderath
1
Hmm ... sieht so aus, als hättest du recht, Alderath. Sie können den Iterator von PriorityQueue nicht verwenden, um die Elemente in der erwarteten Reihenfolge abzurufen. Sieht so aus, als müsste ich meine Antwort bearbeiten.
Spoike
7
Die Prioritätswarteschlange ist nur ein Haufen, Sie können nur auf die oberste Ebene zugreifen, da sie nicht zur Antwort auf die Frage gehört.
Bests
1
Erwähnenswert ist auch, dass Sie Collections.sort()sogar die Vergleichsfunktion definieren können, die zum Sortieren mithilfe eines ComparatorObjekts verwendet wird.
Mike 'Pomax' Kamermans
71

Weil das Konzept einer Liste nicht mit dem Konzept einer automatisch sortierten Sammlung kompatibel ist. Der Punkt einer Liste ist, dass nach dem Aufruf list.add(7, elem)ein Anruf an zurückgegeben list.get(7)wird elem. Bei einer automatisch sortierten Liste könnte das Element an einer beliebigen Position landen.

Michael Borgwardt
quelle
26

Da alle Listen bereits nach der Reihenfolge "sortiert" sind, in der die Elemente hinzugefügt wurden (FIFO-Reihenfolge), können Sie sie mit einer anderen Reihenfolge "neu sortieren", einschließlich der natürlichen Reihenfolge der Elemente java.util.Collections.sort().

BEARBEITEN:

Listen als Datenstrukturen basieren auf der Reihenfolge, in der die Elemente eingefügt wurden.

Sets haben diese Informationen nicht.

Wenn Sie durch Hinzufügen von Zeit bestellen möchten, verwenden Sie List. Wenn Sie nach anderen Kriterien bestellen möchten, verwenden Sie SortedSet.

SJuan76
quelle
22
Set erlaubt keine Duplikate
Bests
10
Ich denke nicht, dass dies eine sehr gute Antwort ist. Sicher, Listen in der Java-API haben eine bestimmte Reihenfolge, die davon abhängt, wann / wie die Elemente eingefügt wurden. Das Vorhandensein von Listen, die in einer Weise angeordnet sind, die von der Einfügemethode / -zeit abhängt, verhindert jedoch nicht, dass andere Datenstrukturen vorhanden sind, in denen die Reihenfolge auf andere Weise bestimmt wird (z. B. durch einen Komparator). Grundsätzlich fragt das OP, warum es keine Datenstruktur gibt, die einem SortedSet entspricht, mit der Ausnahme, dass die Datenstruktur mehrere Vorkommen von Elementen zulassen sollte, die gleich sind.
Alderath
5
Meine Folgefrage wäre also: " Warum gibt es keine Datenstruktur, die wie ein SortedSet funktioniert, aber mehrere gleiche Elemente enthalten kann? " (Und bitte nicht antworten, " weil Sets nur ein Element enthalten können ")
Alderath
@Alderath: Siehe stackoverflow.com/questions/416266/sorted-collection-in-java . Kurz gesagt: Verwenden Sie Guavas TreeMultiset
Janus Troelsen
4
Listen werden NICHT "sortiert", auch wenn Sie "sortiert" in doppelte Anführungszeichen setzen. Sie werden bestellt.
Koray Tugay
21

Set und Map sind nichtlineare Datenstrukturen. Liste ist lineare Datenstruktur.

Geben Sie hier die Bildbeschreibung ein


Die Baumdatenstruktur SortedSetund SortedMapSchnittstellen implementiert TreeSetund TreeMapjeweils verwendete Verwendung Rot-Schwarz - Baum Implementierung Algorithmus. So wird sichergestellt, dass keine doppelten Elemente (oder Schlüssel im Fall von Map) vorhanden sind.

  • List Wird bereits eine geordnete Sammlung und indexbasierte Datenstruktur gepflegt, sind Bäume keine indexbasierten Datenstrukturen.
  • Tree per definitionem dürfen keine Duplikate enthalten sein.
  • In können Listwir Duplikate haben, also gibt es keine TreeList(dh keine SortedList).
  • Liste verwaltet Elemente in Einfügereihenfolge. Wenn wir also die Liste sortieren wollen, müssen wir sie verwenden java.util.Collections.sort(). Es sortiert die angegebene Liste in aufsteigender Reihenfolge entsprechend der natürlichen Reihenfolge ihrer Elemente.
Premraj
quelle
14

JavaFX SortedList

Obwohl es eine Weile gedauert hat, hat Java 8 eine sortierte List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Wie Sie in den Javadocs sehen können, ist es Teil der JavaFX- Sammlungen, die eine sortierte Ansicht einer ObservableList bereitstellen sollen.

Update: Beachten Sie, dass mit Java 11 das JavaFX-Toolkit außerhalb des JDK verschoben wurde und jetzt eine separate Bibliothek ist. JavaFX 11 ist als herunterladbares SDK oder bei MavenCentral erhältlich. Siehe https://openjfx.io

swpalmer
quelle
2
Leider funktioniert diese SortedList nicht wie eine normale Liste - zum Beispiel hat sie keinen Standardkonstruktor (Sie müssen sie mit einer ObservableList erstellen, was auch immer das bedeutet ...)
Erel Segal-Halevi
Die SortedList von JavaFX ist eindeutig für die Verwendung von GUI-Komponenten und wegen des Overheads NICHT geeignet, um nur eine Liste sortierter Objekte zu haben. Es würde auch bedeuten, auf das gesamte FX-Modul zu verweisen, selbst wenn die GUI im Projekt nicht verwendet wird.
COBRA.cH
1
@ COBRA.cH Ja, das stimmt. Eine leistungsfähigere sortierte Liste könnte wahrscheinlich ein dünner Wrapper um eine TreeMap sein, in dem eine Ganzzahl verwendet wird, um Duplikate des Schlüssels zu zählen. Sie können auch ein TreeSet mit einem Komparator verwenden, der niemals 0 zurückgibt.
swpalmer
Warum die Abstimmungen? Die Frage beginnt mit der Voraussetzung, dass es in den JDK-Bibliotheken keine sortierte Liste gibt. Diese Antwort korrigiert diese Annahme. Ob Sie die Implementierung dieser bestimmten sortierten Liste mögen oder nicht, ist kein Grund, abzustimmen. Diese Antwort empfiehlt die Klasse nicht, sondern weist lediglich auf ihre Existenz hin.
Basil Bourque
10

Für alle Neulinge hat Android ab April 2015 eine SortedList- Klasse in der Support-Bibliothek, die speziell für die Arbeit mit entwickelt wurde RecyclerView. Hier ist der Blog-Beitrag darüber.

Amagi82
quelle
1
Es ist erwähnenswert, dass Androids SortedList zum Zeitpunkt dieses Kommentars die onItemMoved () -Funktionalität mit RecyclerView nicht unterstützt. Ich musste meine eigene SortedList schreiben, die weniger effizient ist, um die Einschränkungen zu umgehen.
Matthew
4

Ein weiterer Punkt ist die zeitliche Komplexität von Einfügeoperationen. Für eine Listeneinfügung erwartet man eine Komplexität von O (1). Dies konnte jedoch mit einer sortierten Liste nicht garantiert werden.

Und der wichtigste Punkt ist, dass Listen nichts über ihre Elemente annehmen. Sie können beispielsweise Listen mit Dingen erstellen, die nicht implementiert sind equalsoder compare.

Ingo
quelle
Sie können eine Liste ohne (logn) Einfügen / Löschen / Finden / Enthalten haben, aber nicht mit Get (Int).
Bests
3
Der letzte Punkt ist keine wirklich gute Erklärung. Sie können SortedSetDinge erstellen, die nicht implementiert werden Comparable. Siehe diesen TreeSet-Konstruktor .
Alderath
1
@Alderath - vielleicht war mein Wortlaut zu schwach. Die Beobachtung besagt jedoch, dass Elemente von Mengen und Schlüssel von Bäumen zumindest für die Gleichheit vergleichbar sein müssen, während Listenelemente dies nicht müssen. Ob die Reihenfolge / Gleichheitsbeziehung für Mengen und Bäume in einem Komparator oder anderswo implementiert ist, ist unerheblich - aber Sie benötigen eine.
Ingo
Listen garantieren nicht das Einfügen von O (1) , sondern den Zugriff auf O (1) . bigocheatsheet.com
Matt Quigley
1
@ Betlista du hast recht! Ich kann meinen Kommentar nicht aktualisieren, aber die Java- ListOberfläche garantiert keine Leistungsspezifikationen für ihre Methoden.
Matt Quigley
3

Stellen Sie sich das so vor: Die ListSchnittstelle verfügt über Methoden wie add(int index, E element), set(int index, E element). Der Vertrag sieht vor, dass Sie ein Element an Position X dort finden, wenn Sie es hinzugefügt haben, es sei denn, Sie fügen zuvor Elemente hinzu oder entfernen sie.

Wenn eine Listenimplementierung Elemente in einer anderen Reihenfolge als basierend auf dem Index speichern würde, wären die obigen Listenmethoden nicht sinnvoll.

Costi Ciudatu
quelle
2

Die erste Zeile in der Listen-API besagt, dass es sich um eine geordnete Sammlung handelt (auch als Sequenz bezeichnet). Wenn Sie die Liste sortieren, können Sie die Reihenfolge nicht beibehalten, sodass in Java keine Baumliste vorhanden ist.
Wie API sagt, wurde Java List von Sequence inspiriert und siehe die Sequenzeigenschaften http://en.wikipedia.org/wiki/Sequence_(mathematics )

Dies bedeutet nicht, dass Sie die Liste nicht sortieren können, aber Java entspricht seiner Definition und bietet standardmäßig keine sortierten Versionen von Listen.

Syam
quelle
2

Wenn Sie nach einer Möglichkeit suchen, Elemente zu sortieren, aber auch effizient über einen Index darauf zugreifen können, haben Sie folgende Möglichkeiten:

  1. Verwenden Sie einen Direktzugriffsliste für die Lagerung (zB ArrayList)
  2. Stellen Sie sicher, dass es immer sortiert ist

Um dann ein Element hinzuzufügen oder zu entfernen, können Collections.binarySearchSie den Einfüge- / Entfernungsindex abrufen. Da Ihre Liste einen Direktzugriff implementiert, können Sie die Liste mit dem ermittelten Index effizient ändern.

Beispiel:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}
Marcono1234
quelle
1

Erwägen Sie die Verwendung einer indizierten Baumkarte . Es handelt sich um ein erweitertes JDK-TreeSet, das den Zugriff auf Elemente über den Index ermöglicht und den Index eines Elements ohne Iteration oder versteckte zugrunde liegende Listen findet, die den Baum sichern. Der Algorithmus basiert auf der Aktualisierung der Gewichte sich ändernder Knoten bei jeder Änderung.

Vitaly Sazanovich
quelle