Posortowana kolekcja w Javie

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.

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).

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

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ę.

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.

Chcesz implementacji SortedSet , a mianowicie TreeSet .

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 .

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 .

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

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

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.

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

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.

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.

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.

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

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

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

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

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

    }

}

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