Sortierte Sammlung in Java

161

Ich bin ein Anfänger in Java. Bitte schlagen Sie vor, welche Sammlung (en) für die Pflege einer sortierten Liste in Java verwendet werden können. Ich habe es versucht Mapund Set, aber sie waren nicht das, wonach ich gesucht habe.

b4hand
quelle

Antworten:

187

Dies kommt sehr spät, aber es gibt eine Klasse im JDK, nur um eine sortierte Liste zu haben. Es heißt (etwas außer Betrieb mit den anderen Sorted*Schnittstellen) " java.util.PriorityQueue". Es kann entweder Comparable<?>s oder mit a sortieren Comparator.

Der Unterschied zu einer Listsortierten Verwendung Collections.sort(...)besteht darin, dass durch die Verwendung einer Heap-Datenstruktur ArrayListjederzeit eine Teilreihenfolge mit einer Einfügungsleistung von O (log (n)) beibehalten wird, während die Einfügung in eine sortierte Reihenfolge O (n) ist (dh mit binärer Suche und Bewegung).

Doch im Gegensatz zu einem List, PriorityQueuebietet keine Unterstützung für den indizierten Zugriff ( get(5)), die einzige Möglichkeit , den Zugriff auf Elemente in einem Haufen sie aus, einer nach dem anderen zu nehmen ist (daher der Name PriorityQueue).

Martin Probst
quelle
4
Imo verdient diese Antwort mehr positive Stimmen, da sie auf die einzige Sammlung hinweist, die die Fähigkeit in JDK hat
nimcap
96
Aus dem Javadoc: "Es ist nicht garantiert, dass der in Methode iterator () bereitgestellte Iterator die Elemente der PriorityQueue in einer bestimmten Reihenfolge durchläuft."
Christoffer Hammarström
10
@giraff: Eine Prioritätswarteschlange ist genau das, eine Datenstruktur, die eine Prioritätswarteschlange sehr effizient führt. Sie können von vorne abfragen und die Datenelemente in sortierter Reihenfolge abrufen. Heaps behalten jedoch intern nicht die Gesamtreihenfolge der Elemente bei (aus diesem Grund sind sie so effizient), sodass es keine Möglichkeit gibt, in der richtigen Reihenfolge auf Elemente zuzugreifen, ohne den Abfragevorgang auszuführen.
Martin Probst
2
@chrispy es hängt ein bisschen davon ab, was genau Sie mit Ihrer Datenstruktur erreichen wollen. Heaps sind eine effiziente Möglichkeit, eine Liste von Elementen zu verwalten und sie später in geordneter Weise abzurufen. Die Verwendung des Iterators funktioniert nicht, aber wenn Sie eine Abfrage durchführen, erhalten Sie Ihre Daten in der richtigen Reihenfolge. Das Abrufen ist destruktiv, aber das kann in vielen Fällen immer noch in Ordnung sein. Ich finde diese Antwort gut.
Martin Probst
4
@MartinProbst Bitte korrigieren Sie Ihre Antwort auf CLEARLY und geben Sie an, dass diese Sammlung NICHT in der erwarteten Reihenfolge bearbeitet werden kann. Wie viele gesagt haben, ist dies extrem irreführend!
Jorge Galvão
53

TreeMap und TreeSet geben Ihnen eine Iteration über den Inhalt in sortierter Reihenfolge. Oder Sie können eine ArrayList verwenden und Collections.sort () verwenden, um sie zu sortieren. Alle diese Klassen befinden sich in java.util

Michael Borgwardt
quelle
27
Dies hat jedoch zwei Hauptnachteile: Der erste besteht darin, dass ein Satz keine Duplikate enthalten kann. Das zweite ist, dass Sie, wenn Sie eine Liste und Collections.sort () verwenden, dazu neigen, ständig große Listen zu sortieren und eine schlechte Leistung zu erzielen. Sicher können Sie eine "schmutzige" Flagge verwenden, aber es ist nicht ganz dasselbe.
Jeach
Das wirft die Frage auf, ob wir in Java eine Option haben, die Duplikate zulässt und auch ähnliche Leistungen wie Set (Balanced Binary Tree)
bietet
32

Wenn Sie eine sortierte Liste pflegen möchten, die Sie häufig ändern (dh eine Struktur, die nicht nur sortiert ist, sondern auch Duplikate zulässt und deren Elemente effizient durch den Index referenziert werden können), verwenden Sie eine ArrayList, wenn Sie jedoch ein Element einfügen müssen Verwenden Sie immer Collections.binarySearch (), um den Index zu bestimmen, an dem Sie ein bestimmtes Element hinzufügen. Die letztere Methode gibt an, bei welchem ​​Index Sie einfügen müssen, um Ihre Liste in sortierter Reihenfolge zu halten.

Neil Coffey
quelle
11
n Einfügungen sind O (n ^ 2). Ein TreeSet gibt Ihnen saubereren Code und O (n log n). OTOH, für seltene Änderungen ist die binäre Suche eines Arrays schneller und benötigt weniger Speicher (also weniger GC-Overhead).
Tom Hawtin - Tackline
Um den Code sauber zu halten und dennoch Duplikate zuzulassen, wäre es einfach genug, eine SortedList-Klasse zu erstellen, die Werte in sortierter Reihenfolge einfügt.
Mr. Shiny und New
Dies ist eine weitaus bessere Antwort als die am besten bewertete Antwort, imo, wenn Sie mit der von @ TomHawtin-Tackline erwähnten Einschränkung leben können. Dass der Iterator wie erwartet funktioniert, ist in den meisten Fällen entscheidend.
DuneCat
Übrigens hat Tom Recht mit diesem spezifischen Verhalten: Ein Baumsatz bietet Ihnen eine effizientere Änderung. Ein Baumsatz ist jedoch keine Liste (im strengsten Sinne, wenn Elemente durch Index referenziert werden und Duplikate zulässig sind), und auf dem Poster wurde angegeben, dass eine Liste gewünscht wird.
Neil Coffey
Danke Neil, das war verdammt großartig!
Wikingersteve
31

Verwenden Sie die TreeMultiset- Klasse von Google Guava . Guave hat eine spektakuläre Sammlungs-API.

Ein Problem bei der Bereitstellung einer Implementierung von List, die die sortierte Reihenfolge beibehält, ist das in den JavaDocs der add()Methode gemachte Versprechen .

jtb
quelle
Ein
großes Lob
5
+1 für die Erwähnung der Anforderung, dass a Listimmer am Ende hinzugefügt wird.
Roland Illig
2
Beachten Sie, dass TreeMultiSet immer noch keine doppelten Elemente zulässt (Elemente, die compareTo () 0 zurückgibt, nicht equals () check). Wenn Sie dazu neigen, mehr als ein Element mit derselben Priorität hinzuzufügen, erhöht dies nur die Anzahl der zuerst hinzugefügten Elemente, verwirft andere und ist effektiv eine gute Counting Bag-Implementierung.
bekce
12

Sie möchten die SortedSet- Implementierungen, nämlich TreeSet .

Cletus
quelle
10
Nicht unbedingt; Sets dürfen keine doppelten Werte haben. Dies hängt von den Anforderungen des OP ab.
Zach Langley
12

Es gibt einige Optionen. Ich würde TreeSet vorschlagen, wenn Sie keine Duplikate möchten und die Objekte, die Sie einfügen, vergleichbar sind.

Sie können dazu auch die statischen Methoden der Collections-Klasse verwenden.

Weitere Informationen finden Sie unter Sammlungen # sort (java.util.List) und TreeSet .

BenM
quelle
10

Wenn Sie nur eine Liste sortieren möchten, verwenden Sie eine beliebige Liste und verwenden Sie Collections.sort () . Wenn Sie sicherstellen möchten, dass die Elemente in der Liste eindeutig und immer sortiert sind, verwenden Sie ein SortedSet .

Guillaume
quelle
5

Was ich getan habe, ist die Implementierung von List mit einer internen Instanz mit allen delegierten Methoden.

 public class ContactList implements List<Contact>, Serializable {
    private static final long serialVersionUID = -1862666454644475565L;
    private final List<Contact> list;

public ContactList() {
    super();
    this.list = new ArrayList<Contact>();
}

public ContactList(List<Contact> list) {
    super();
    //copy and order list
    List<Contact>aux= new ArrayList(list);
    Collections.sort(aux);

    this.list = aux;
}

public void clear() {
    list.clear();
}

public boolean contains(Object object) {
    return list.contains(object);
}

Danach habe ich eine neue Methode "putOrdered" implementiert, die an der richtigen Position einfügt, wenn das Element nicht existiert, oder ersetzt, nur für den Fall, dass es existiert.

public void putOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
        list.add(index, contact);
    }else{
        list.set(index, contact);
    }
}

Wenn Sie wiederholte Elemente zulassen möchten, implementieren Sie stattdessen addOrdered (oder beides).

public void addOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
    }
    list.add(index, contact);
}

Wenn Sie Einfügungen vermeiden möchten, können Sie auch eine Ausnahme für nicht unterstützte Operationen für die Methoden "add" und "set" auslösen.

public boolean add(Contact object) {
    throw new UnsupportedOperationException("Use putOrdered instead");
}

... und Sie müssen auch mit ListIterator-Methoden vorsichtig sein, da diese Ihre interne Liste ändern können. In diesem Fall können Sie eine Kopie der internen Liste zurückgeben oder erneut eine Ausnahme auslösen.

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}
Carlos Verdes
quelle
Das Problem ist, dass dies gegen den ListVertrag verstößt . Vielleicht wäre es besser, nur zu implementieren Collection. Und wenn ContactListes sortiert ist, contains()kann es auch implementiert werden binarySearch, um effizienter zu sein.
Marcono1234
5

Der effizienteste Weg, eine sortierte Liste wie gewünscht zu implementieren, besteht darin, eine indizierbare Skiplist wie hier zu implementieren: Wikipedia: Indexable Skiplist . Es würde Einfügungen / Entfernungen in O (log (n)) ermöglichen und gleichzeitig einen indizierten Zugriff ermöglichen. Und es würde auch Duplikate erlauben.

Skiplist ist eine ziemlich interessante und, ich würde sagen, unterschätzte Datenstruktur. Leider gibt es in der Java-Basisbibliothek keine indizierte Skiplist-Implementierung, aber Sie können eine der Open Source-Implementierungen verwenden oder selbst implementieren. Es gibt regelmäßige Skiplist-Implementierungen wie ConcurrentSkipListSet und ConcurrentSkipListMap

vladich
quelle
4

TreeSet würde nicht funktionieren, da sie keine Duplikate zulassen und keine Methode zum Abrufen von Elementen an einer bestimmten Position bereitstellen. PriorityQueue würde nicht funktionieren, da es nicht möglich ist, Elemente an einer bestimmten Position abzurufen, was eine Grundvoraussetzung für eine Liste ist. Ich denke, Sie müssen Ihren eigenen Algorithmus implementieren, um eine sortierte Liste in Java mit O (logn) Einfügezeit zu verwalten, es sei denn, Sie benötigen keine Duplikate. Möglicherweise könnte eine Lösung die Verwendung einer TreeMap sein, bei der der Schlüssel eine Unterklasse des Elements ist, das die Methode equals überschreibt, sodass Duplikate zulässig sind.

Giuseppe
quelle
4

Mit LambdaJ

Sie können versuchen, diese Aufgaben mit LambdaJ zu lösen, wenn Sie frühere Versionen von Java 8 verwenden. Sie finden sie hier: http://code.google.com/p/lambdaj/

Hier haben Sie ein Beispiel:

Iterativ sortieren

List<Person> sortedByAgePersons = new ArrayList<Person>(persons);
Collections.sort(sortedByAgePersons, new Comparator<Person>() {
        public int compare(Person p1, Person p2) {
           return Integer.valueOf(p1.getAge()).compareTo(p2.getAge());
        }
}); 

Sortieren mit LambdaJ

List<Person> sortedByAgePersons = sort(persons, on(Person.class).getAge()); 

Natürlich wirkt sich diese Art von Schönheit auf die Leistung aus (durchschnittlich zweimal), aber können Sie einen besser lesbaren Code finden?

Sortieren Sie mit Java 8 mit dem Lambda-Ausdruck

Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));
Federico Piazza
quelle
Wie kann man in Ihrem letzten Beispiel mit Java 8 Lambda-Ausdruck die Sortierung umkehren?
Rajat Shah
1
@ RajatShah Ich denke, Sie können einfach tun-(p1.getAge().compareTo(p2.getAge()))
Federico Piazza
@ RajatShah gerne helfen
Federico Piazza
2

Das Problem mit PriorityQueue besteht darin, dass es durch ein einfaches Array gesichert wird und die Logik, mit der die Elemente in der richtigen Reihenfolge abgerufen werden, vom Ding "Warteschlange [2 * n + 1] und Warteschlange [2 * (n + 1)]" ausgeführt wird. Es funktioniert gut, wenn Sie nur vom Kopf ziehen, macht es aber nutzlos, wenn Sie versuchen, das .toArray irgendwann darauf aufzurufen.

Ich gehe dieses Problem mit com.google.common.collect.TreeMultimap um, aber ich stelle einen benutzerdefinierten Komparator für die Werte bereit, die in eine Bestellung eingeschlossen sind und niemals 0 zurückgeben.

Ex. für Double:

private static final Ordering<Double> NoEqualOrder = Ordering.from(new Comparator<Double>() {

    @Override
    public int compare(Double d1, Double d2)
    {
        if (d1 < d2) {
            return -1;
        }
        else {
            return 1;
        }
    }
});

Auf diese Weise erhalte ich die Werte in der richtigen Reihenfolge, wenn ich .toArray () aufrufe, und habe auch Duplikate.

Martin Klosi
quelle
1

Was Sie wollen, ist ein binärer Suchbaum. Es behält die sortierte Reihenfolge bei und bietet gleichzeitig logarithmischen Zugriff für Suchen, Entfernen und Einfügen (es sei denn, Sie haben einen entarteten Baum - dann ist es linear). Es ist recht einfach zu implementieren und Sie können sogar die List-Schnittstelle implementieren lassen, aber dann wird der Indexzugriff kompliziert.

Der zweite Ansatz besteht darin, eine ArrayList und dann eine Implementierung für die Blasensortierung zu haben. Da Sie jeweils ein Element einfügen oder entfernen, sind die Zugriffszeiten für das Einfügen und Entfernen linear. Die Suche ist logarithmisch und die Indexzugriffskonstante (die Zeiten für LinkedList können unterschiedlich sein). Der einzige Code, den Sie benötigen, ist 5, vielleicht 6 Zeilen Blasensortierung.

Jakub Zaverka
quelle
1

Sie können Arraylist und Treemap verwenden, da Sie sagten, Sie möchten auch wiederholte Werte, dann können Sie TreeSet nicht verwenden, obwohl es ebenfalls sortiert ist, aber Sie müssen den Komparator definieren.


quelle
1

Für Set können Sie TreeSet verwenden. TreeSet ordnet seine Elemente auf der Grundlage einer natürlichen Reihenfolge oder einer Sortierreihenfolge an, die für dieses bestimmte Objekt an Comparable übergeben wird. Verwenden Sie für die Karte TreeMap. TreeMap bietet die Sortierung über Schlüssel. Um der TreeMap ein Objekt als Schlüssel hinzuzufügen, sollte diese Klasse eine vergleichbare Schnittstelle implementieren, die wiederum die Implementierung der Methode compare to () erzwingt, die die Definition der Sortierreihenfolge enthält. http://techmastertutorial.in/java-collection-impl.html

Avi Tyagi
quelle
0

Verwenden Sie die Methode sort (), um die Liste wie folgt zu sortieren:

List list = new ArrayList();

//add elements to the list

Comparator comparator = new SomeComparator();

Collections.sort(list, comparator);

Referenz finden Sie unter folgendem Link: http://tutorials.jenkov.com/java-collections/sorting.html

Shashank Mungantiwar
quelle
0

Verwenden Sie TreeSetdiese Option, um Elemente in sortierter Reihenfolge anzugeben. ODER Collection.sort()zur externen Sortierung mit verwenden Comparator().

Hari
quelle
TreeSet erlaubt keine Duplizierung von Elementen. Manchmal ist es eine gewünschte Funktion, andere nicht. In Anbetracht der Tatsache, dass das OP die Sets ausprobiert hat, schätze ich für den no
usr-local-ΕΨΗΕΛΩΝ
Seien Sie nicht gemein, weisen Sie auch auf die TreeMap hin: docs.oracle.com/javase/10/docs/api/java/util/TreeMap.html
Haakon Løtveit
0
import java.util.TreeSet;

public class Ass3 {
    TreeSet<String>str=new TreeSet<String>();
    str.add("dog");
    str.add("doonkey");
    str.add("rat");
    str.add("rabbit");
    str.add("elephant");
    System.out.println(str);    
}
Deepica MY
quelle
0

Wenn wir mit Java 8 Comparator die Liste sortieren möchten, dann sind hier die 10 bevölkerungsreichsten Städte der Welt, und wir möchten sie nach Namen sortieren, wie von Time angegeben. Osaka, Japan. ... Mexiko-Stadt, Mexiko. ... Peking, China. ... Sao Paulo, Brasilien. ... Mumbai, Indien. ... Shanghai, China. ... Delhi, Indien. ... Tokyo, Japan.

 import java.util.Arrays;
 import java.util.Comparator;
 import java.util.List;

public class SortCityList {

    /*
     * Here are the 10 most populated cities in the world and we want to sort it by
     * name, as reported by Time. Osaka, Japan. ... Mexico City, Mexico. ...
     * Beijing, China. ... São Paulo, Brazil. ... Mumbai, India. ... Shanghai,
     * China. ... Delhi, India. ... Tokyo, Japan.
     */
    public static void main(String[] args) {
        List<String> cities = Arrays.asList("Osaka", "Mexico City", "São Paulo", "Mumbai", "Shanghai", "Delhi",
                "Tokyo");
        System.out.println("Before Sorting List is:-");
        System.out.println(cities);
        System.out.println("--------------------------------");

        System.out.println("After Use of List sort(String.CASE_INSENSITIVE_ORDER) & Sorting List is:-");
        cities.sort(String.CASE_INSENSITIVE_ORDER);
        System.out.println(cities);
        System.out.println("--------------------------------");
        System.out.println("After Use of List sort(Comparator.naturalOrder()) & Sorting List is:-");
        cities.sort(Comparator.naturalOrder());
        System.out.println(cities);

    }

}
Vipul Gulhane
quelle
0

Sortieren einer ArrayList nach benutzerdefinierten Kriterien.

Modellklasse

 class Student 
 { 
     int rollno; 
     String name, address; 

     public Student(int rollno, String name, String address) 
     { 
         this.rollno = rollno; 
         this.name = name; 
         this.address = address; 
     }   

     public String toString() 
     { 
         return this.rollno + " " + this.name + " " + this.address; 
     } 
 } 

Klasse sortieren

 class Sortbyroll implements Comparator<Student> 
 {         
     public int compare(Student a, Student b) 
     { 
         return a.rollno - b.rollno; 
     } 
 } 

Hauptklasse

 class Main 
 { 
     public static void main (String[] args) 
     { 
         ArrayList<Student> ar = new ArrayList<Student>(); 
         ar.add(new Student(111, "bbbb", "london")); 
         ar.add(new Student(131, "aaaa", "nyc")); 
         ar.add(new Student(121, "cccc", "jaipur")); 

         System.out.println("Unsorted"); 
         for (int i=0; i<ar.size(); i++) 
             System.out.println(ar.get(i)); 

         Collections.sort(ar, new Sortbyroll()); 

         System.out.println("\nSorted by rollno"); 
         for (int i=0; i<ar.size(); i++) 
             System.out.println(ar.get(i)); 
     } 
 } 

Ausgabe

 Unsorted
 111 bbbb london
 131 aaaa nyc
 121 cccc jaipur

 Sorted by rollno
 111 bbbb london
 121 cccc jaipur
 131 aaaa nyc
skpaik
quelle