Posortowana kolekcja w Javie

161

Jestem początkującym w Javie. Proszę zasugerować, które kolekcje mogą / powinny być używane do utrzymywania posortowanej listy w Javie. Próbowałem Mapi Set, ale nie były tym, czego szukałem.

b4hand
źródło

Odpowiedzi:

187

Dzieje się to bardzo późno, ale w JDK znajduje się klasa, której celem jest posortowana lista. Nazywa się (nieco poza kolejnością z innymi Sorted*interfejsami) „ java.util.PriorityQueue”. Może sortować Comparable<?>s lub używając pliku Comparator.

Różnica w stosunku do Listposortowanego użycia Collections.sort(...)polega na tym, że będzie to utrzymywać częściową kolejność przez cały czas, z wydajnością wstawiania O (log (n)), przy użyciu struktury danych sterty, podczas gdy wstawianie posortowane ArrayListbędzie miało wartość O (n) (tj. za pomocą wyszukiwania binarnego i przenoszenia).

Jednak w przeciwieństwie do a List, PriorityQueuenie obsługuje indeksowanego access ( get(5)), jedynym sposobem uzyskania dostępu do elementów w stercie jest wyjęcie ich pojedynczo (stąd nazwa PriorityQueue).

Martin Probst
źródło
4
imo ta odpowiedź zasługuje na więcej głosów, ponieważ wskazuje jedyną kolekcję, która ma taką możliwość w JDK
nimcap
96
Z Javadoc: „Iterator udostępniony w metodzie iterator () nie gwarantuje przejścia elementów PriorityQueue w jakiejkolwiek określonej kolejności”.
Christoffer Hammarström
10
@giraff: kolejka priorytetowa to po prostu taka struktura danych, która jest bardzo wydajna w utrzymywaniu kolejki priorytetowej. Możesz sondować z przodu i uzyskać dane w posortowanej kolejności. Jednak sterty nie utrzymują wewnętrznie całkowitej kolejności elementów (dlatego są tak wydajne), więc nie ma możliwości uzyskania dostępu do elementów w kolejności bez wykonania operacji odpytywania.
Martin Probst
2
@chrispy zależy to trochę od tego, co dokładnie chcesz osiągnąć ze strukturą danych. Sterty są skutecznym sposobem na utrzymanie listy elementów i późniejsze ich pobieranie w uporządkowanej formie - użycie iteratora nie działa, ale jeśli sondujesz z niego, otrzymasz dane w kolejności. Odzyskiwanie jest destrukcyjne, ale w wielu przypadkach może to być w porządku. Więc myślę, że ta odpowiedź jest dobra.
Martin Probst
4
@MartinProbst Popraw swoją odpowiedź, WYRAŹNIE zaznacz, że ta kolekcja NIE MOŻE BYĆ ITEROWANA w oczekiwanej kolejności. Jak wielu powiedziało, jest to wyjątkowo mylące!
Jorge Galvão,
53

TreeMap i TreeSet zapewnią iterację po zawartości w posortowanej kolejności. Lub możesz użyć ArrayList i użyć Collections.sort () do sortowania. Wszystkie te klasy znajdują się w java.util

Michael Borgwardt
źródło
27
Ma to jednak dwie główne wady, z których pierwsza polega na tym, że zestaw nie może mieć duplikatów. Po drugie, jeśli używasz list i Collections.sort (), masz tendencję do ciągłego sortowania ogromnych list i daje słabą wydajność. Oczywiście możesz użyć flagi „brudnej”, ale to nie to samo.
Jeach
To nasuwa pytanie, czy mamy opcję w Javie, która pozwala na duplikaty, a także daje wyniki podobne do Set (Balanced Binary Tree)
mankadnandan
32

Jeśli chcesz zachować posortowaną listę, którą będziesz często modyfikować (tj. Strukturę, która oprócz tego, że jest posortowana, pozwala na duplikaty i której elementy można skutecznie odwoływać się za pomocą indeksu), użyj ArrayList, ale gdy musisz wstawić element , zawsze używaj Collections.binarySearch () do określenia indeksu, w którym dodajesz dany element. Druga metoda określa indeks, w którym należy wstawić listę, aby zachować posortowaną listę.

Neil Coffey
źródło
11
n wstawek będzie równe O (n ^ 2). TreeSet zapewni czystszy kod i O (n log n). OTOH, w przypadku rzadkich modyfikacji wyszukiwanie binarne tablicy będzie szybsze i zużywa mniej pamięci (a więc mniej narzutu GC).
Tom Hawtin - tackline
Aby kod był czysty i nadal pozwalał na duplikaty, wystarczyłoby utworzyć klasę SortedList, która wstawia wartości w kolejności posortowanej.
Mr. Shiny and New 安 宇
To o wiele lepsza odpowiedź niż najbardziej pozytywna odpowiedź, imo, jeśli możesz żyć z zastrzeżeniem wspomnianym przez @ TomHawtin-tackline. To, że iterator działa zgodnie z oczekiwaniami, ma kluczowe znaczenie w większości przypadków.
DuneCat
Nawiasem mówiąc, Tom ma rację co do tego konkretnego zachowania: zestaw drzew da ci bardziej wydajną modyfikację. Ale zestaw drzew nie jest listą (w ścisłym sensie posiadania elementów, do których odwołuje się indeks i zezwalających na duplikaty), a plakat powiedział, że chce listy.
Neil Coffey
Dziękuję Neil, to było cholernie niesamowite!
vikingsteve
31

Użyj klasy TreeMultiset Google Guava . Guava ma spektakularne API kolekcji.

Jednym z problemów związanych z zapewnieniem implementacji List, która utrzymuje posortowaną kolejność, jest obietnica złożona w JavaDocs add()metody.

jtb
źródło
Uznanie za sugestię
multiset
5
+1 za wzmiankę o wymaganiu, które Listzawsze dodaje na końcu.
Roland Illig
2
Zauważ, że TreeMultiSet nadal nie zezwala na zduplikowane elementy (elementy, które compareTo () zwracają 0, a nie sprawdzanie równości ()). Jeśli masz tendencję do dodawania więcej niż jednego przedmiotu o tym samym priorytecie, zwiększy to tylko liczbę tych, które zostały dodane jako pierwsze, odrzucając inne i skutecznie wdrażając worek liczenia.
bekce
12

Chcesz implementacji SortedSet , a mianowicie TreeSet .

cletus
źródło
10
Niekoniecznie; zestawy nie mogą mieć zduplikowanych wartości. To zależy od wymagań PO.
Zach Langley,
12

Jest kilka opcji. Sugerowałbym TreeSet, jeśli nie chcesz duplikatów, a wstawiane obiekty są porównywalne.

W tym celu można również użyć statycznych metod klasy Collections.

Aby uzyskać więcej informacji, zobacz Kolekcje # sort (java.util.List) i TreeSet .

BenM
źródło
10

Jeśli chcesz tylko posortować listę, użyj dowolnego rodzaju listy i użyj kolekcji.sort () . Jeśli chcesz mieć pewność, że elementy na liście są unikalne i zawsze posortowane, użyj SortedSet .

Guillaume
źródło
5

To, co zrobiłem, to zaimplementowanie List z wewnętrzną instancją z delegowanymi wszystkimi metodami.

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

Następnie zaimplementowałem nową metodę "putOrdered", która wstawia we właściwej pozycji, jeśli element nie istnieje lub zamienia na wypadek, gdyby istniał.

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

Jeśli chcesz zezwolić na powtarzające się elementy, po prostu zaimplementuj addOrdered (lub oba).

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

Jeśli chcesz uniknąć operacji wstawiania, możesz również zgłosić wyjątek dotyczący nieobsługiwanej operacji dla metod „add” i „set”.

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

... a także musisz uważać na metody ListIterator, ponieważ mogą one modyfikować Twoją listę wewnętrzną. W takim przypadku możesz zwrócić kopię listy wewnętrznej lub ponownie zgłosić wyjątek.

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}
Carlos Verdes
źródło
Problem w tym, że to narusza Listumowę. Może lepiej byłoby tylko wdrożyć Collection. A jeśli ContactListjest posortowany, contains()można go również zaimplementować za pomocą, binarySearchaby był bardziej wydajny.
Marcono1234,
5

Najbardziej wydajnym sposobem zaimplementowania posortowanej listy, tak jak chcesz, byłoby zaimplementowanie indeksowalnej listy pominięć, jak tutaj: Wikipedia: Indeksowalna lista pomijana . Pozwoliłoby to na wstawianie / usuwanie w O (log (n)) i pozwoliłoby na indeksowany dostęp w tym samym czasie. Pozwoliłoby to również na duplikaty.

Skiplist jest dość interesującą i, powiedziałbym, niedocenianą strukturą danych. Niestety nie ma implementacji indeksowanej listy pominięć w podstawowej bibliotece Java, ale możesz użyć jednej z implementacji open source lub zaimplementować ją samodzielnie. Istnieją regularne implementacje Skiplist, takie jak ConcurrentSkipListSet i ConcurrentSkipListMap

vladich
źródło
4

TreeSet nie zadziała, ponieważ nie zezwalają na duplikaty oraz nie zapewniają metody pobierania elementu z określonej pozycji. PriorityQueue nie zadziała, ponieważ nie pozwala na pobieranie elementów z określonej pozycji, co jest podstawowym wymaganiem dla listy. Myślę, że musisz zaimplementować własny algorytm, aby utrzymać posortowaną listę w Javie z czasem wstawiania O (logn), chyba że nie potrzebujesz duplikatów. Może rozwiązaniem mogłoby być użycie TreeMap, w której klucz jest podklasą elementu, przesłaniając metodę equals, tak aby możliwe były duplikaty.

Giuseppe
źródło
4

Korzystanie z LambdaJ

Możesz spróbować rozwiązać te zadania za pomocą LambdaJ, jeśli używasz wcześniejszych wersji java 8. Możesz je znaleźć tutaj: http://code.google.com/p/lambdaj/

Tutaj masz przykład:

Sortuj iteracyjnie

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

Sortuj według LambdaJ

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

Oczywiście posiadanie tego rodzaju piękna wpływa na wydajność (średnio 2 razy), ale czy możesz znaleźć bardziej czytelny kod?

Sortuj według java 8, używając wyrażenia lambda

Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));
Federico Piazza
źródło
W ostatnim przykładzie z wyrażeniem lambda w języku Java 8, jak można sortować odwrotne?
Rajat Shah
1
@RajatShah Myślę, że możesz po prostu zrobić-(p1.getAge().compareTo(p2.getAge()))
Federico Piazza,
@RajatShah cieszy się, że może pomóc
Federico Piazza
2

Problem z PriorityQueue polega na tym, że jest on zabezpieczony prostą tablicą, a logika, która pobiera elementy w kolejności, jest wykonywana przez „queue [2 * n + 1] i queue [2 * (n + 1)]”. Działa świetnie, jeśli po prostu pociągniesz od głowy, ale czyni to bezużytecznym, jeśli w pewnym momencie próbujesz wywołać na nim .toArray.

Omawiam ten problem, używając com.google.common.collect.TreeMultimap, ale dla wartości dostarczam niestandardowy komparator, zawarty w kolejności, która nigdy nie zwraca 0.

dawny. dla 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;
        }
    }
});

W ten sposób otrzymuję wartości w kolejności, gdy wywołuję .toArray (), a także mam duplikaty.

Martin Klosi
źródło
1

To, czego chcesz, to binarne drzewo wyszukiwania. Utrzymuje posortowaną kolejność, oferując logarytmiczny dostęp do wyszukiwania, usuwania i wstawiania (chyba że masz zdegenerowane drzewo - wtedy jest liniowe). Jest dość łatwy do zaimplementowania, a nawet można go zaimplementować interfejs List, ale wtedy dostęp do indeksu staje się skomplikowany.

Drugie podejście polega na zastosowaniu ArrayList, a następnie implementacji sortowania bąbelkowego. Ponieważ wstawiasz lub usuwasz jeden element na raz, czasy dostępu do wstawiania i usuwania są liniowe. Wyszukiwania są logarytmiczne i mają stałą dostępu do indeksu (czasy mogą być różne dla LinkedList). Jedyny potrzebny kod to 5, może 6 wierszy sortowania bąbelkowego.

Jakub Zaverka
źródło
1

Możesz używać Arraylist i Treemap, ponieważ powiedziałeś, że chcesz również powtarzać wartości, nie możesz użyć TreeSet, chociaż jest on również posortowany, ale musisz zdefiniować komparator.


źródło
1

W zestawie możesz użyć TreeSet. TreeSet porządkuje swoje elementy na podstawie naturalnego porządku lub dowolnej kolejności sortowania przekazanej do Porównywalnego dla tego konkretnego obiektu. Do mapy użyj TreeMap. TreeMap zapewnia sortowanie według kluczy. Aby dodać obiekt jako klucz do TreeMap, ta klasa powinna implementować porównywalny interfejs, który z kolei wymusza implementację metody compare to (), która zawiera definicję kolejności sortowania. http://techmastertutorial.in/java-collection-impl.html

Avi Tyagi
źródło
0

Użyj metody sort (), aby posortować listę jak poniżej:

List list = new ArrayList();

//add elements to the list

Comparator comparator = new SomeComparator();

Collections.sort(list, comparator);

W celach informacyjnych zobacz link: http://tutorials.jenkov.com/java-collections/sorting.html

Shashank Mungantiwar
źródło
0

Użyj, TreeSetktóra daje elementy w posortowanej kolejności. LUB użyj Collection.sort()do sortowania zewnętrznego z Comparator().

Hari
źródło
TreeSet nie pozwala na powielanie elementów. Czasami jest to pożądana funkcja, innym nie. Biorąc pod uwagę, że OP wypróbował sety, myślę, że nie
usr-local-ΕΨΗΕΛΩΝ
Nie bądź złośliwy, zwróć też uwagę na TreeMap: 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
źródło
0

z Java 8 Comparator, jeśli chcemy posortować listę, to Oto 10 najbardziej zaludnionych miast na świecie i chcemy posortować je według nazwy, zgodnie z raportem Czas. Osaka, Japonia. ... Miasto Meksyk, Meksyk. ... Pekin, Chiny. ... São Paulo, Brazylia. ... Mumbai w Indiach. ... Szanghai Chiny. ... Delhi, Indie. ... Tokio, Japonia.

 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
źródło
0

Sortowanie ArrayList według kryteriów zdefiniowanych przez użytkownika.

Klasa modelu

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

Sortowanie klasy

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

Klasa główna

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

Wynik

 Unsorted
 111 bbbb london
 131 aaaa nyc
 121 cccc jaipur

 Sorted by rollno
 111 bbbb london
 121 cccc jaipur
 131 aaaa nyc
skpaik
źródło