Raccolta ordinata in Java

Sono un principiante in Java. Si prega di suggerire quale / i raccolta / i possa / devono essere utilizzata per mantenere una lista ordinata in Java. Ho provato Map e Set , ma non erano quello che stavo cercando.

Questo arriva molto tardi, ma c’è una class nel JDK solo allo scopo di avere una lista ordinata. È denominato (un po ‘fuori uso con le altre interfacce Sorted* ) ” java.util.PriorityQueue “. Può ordinare i Comparable< ?> o usando un Comparator .

La differenza con una List ordinata usando Collections.sort(...) è che questo manterrà sempre un ordine parziale, con O (log (n)) performance di inserimento, usando una struttura di dati heap, mentre inserendo in una lista ordinata ArrayList sarà O (n) (cioè, utilizzando la ricerca e lo spostamento binari).

Tuttavia, diversamente da un List , PriorityQueue non supporta l’accesso indicizzato ( get(5) ), l’unico modo per accedere agli elementi in un heap è di eliminarli, uno alla volta (quindi il nome PriorityQueue ).

TreeMap e TreeSet ti daranno un’iterazione sui contenuti in ordine. Oppure puoi usare un ArrayList e usare Collections.sort () per ordinarlo. Tutte quelle classi sono in java.util

Se si desidera mantenere un elenco ordinato che si modificherà frequentemente (ovvero una struttura che, oltre ad essere ordinata, consente duplicati e ai cui elementi è ansible fare riferimento in modo efficiente per indice), quindi utilizzare un ArrayList ma quando è necessario inserire un elemento , usa sempre Collections.binarySearch () per determinare l’indice a cui aggiungi un dato elemento. Il secondo metodo ti dice l’indice che devi inserire per mantenere la lista in ordine.

Utilizza Google Guava’s TreeMultiset. Guava è una spettacolare API delle collezioni.

Guava: https://github.com/google/guava

TreeMultiset: https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/TreeMultiset.html

Un problema nel fornire un’implementazione di List che mantenga l’ordine ordinato è la promise fatta nei Javadoc del metodo ‘add’.

Ci sono alcune opzioni Suggerirei TreeSet se non vuoi duplicati e gli oggetti che stai inserendo sono comparabili.

Puoi anche usare i metodi statici della class Collections per fare ciò.

Vedi Raccolte # ordinamento (java.util.List) e TreeSet per maggiori informazioni.

Vuoi le implementazioni SortedSet , ovvero TreeSet .

Se si desidera solo ordinare un elenco, utilizzare qualsiasi tipo di elenco e utilizzare Collections.sort () . Se si desidera assicurarsi che gli elementi nell’elenco siano univoci e sempre ordinati, utilizzare un SortedSet .

Quello che ho fatto è implementare List con un’istanza interna con tutti i metodi delegati.

  public class ContactList implements List, Serializable { private static final long serialVersionUID = -1862666454644475565L; private final List list; public ContactList() { super(); this.list = new ArrayList(); } public ContactList(List list) { super(); //copy and order list Listaux= new ArrayList(list); Collections.sort(aux); this.list = aux; } public void clear() { list.clear(); } public boolean contains(Object object) { return list.contains(object); } 

Dopo, ho implementato un nuovo metodo “putOrdered” che inserisce nella posizione corretta se l’elemento non esiste o lo sostituisce nel caso esista.

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

Se si desidera consentire elementi ripetuti, implementare invece addOrdered (o entrambi).

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

Se si desidera evitare gli inserimenti, è ansible anche eseguire un'eccezione di operazione non supportata sui metodi "aggiungi" e "imposta".

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

... e anche Devi stare attento con i metodi ListIterator perché potrebbero modificare la tua lista interna. In questo caso è ansible restituire una copia dell'elenco interno o generare nuovamente un'eccezione.

 public ListIterator listIterator() { return (new ArrayList(list)).listIterator(); } 

TreeSet non funzionerebbe perché non consentono duplicati e non forniscono metodi per recuperare elementi in una posizione specifica. PriorityQueue non funzionerebbe perché non consente il recupero di elementi in una posizione specifica che è un requisito di base per un elenco. Penso che sia necessario implementare il proprio algoritmo per mantenere un elenco ordinato in Java con O (logn), inserire il tempo, a meno che non siano necessari duplicati. Forse una soluzione potrebbe utilizzare una TreeMap in cui la chiave è una sottoclass dell’elemento che sovrascrive il metodo equals in modo tale che i duplicati siano consentiti.

Utilizzando LambdaJ

Puoi provare a risolvere questi compiti con LambdaJ se utilizzi versioni precedenti di java 8. Puoi trovarlo qui: http://code.google.com/p/lambdaj/

Ecco un esempio:

Ordina Iterativo

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

Ordina con LambdaJ

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

Certamente, avere questo tipo di bellezza ha un impatto sulle prestazioni (una media di 2 volte), ma puoi trovare un codice più leggibile?

Ordina con java 8 usando l’espressione lambda

 Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge())); //or persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge())); 

Il modo più efficace per implementare una lista ordinata come si vorrebbe sarebbe implementare skiplist indicizzabile come qui: Wikipedia: skiplist indicizzabile . Permetterebbe di avere inserti / rimozioni in O (log (n)) e permetterebbe di avere accesso indicizzato allo stesso tempo. E permetterebbe anche duplicati.

Skiplist è una struttura di dati piuttosto interessante e, direi, sottovalutata. Sfortunatamente non esiste un’implementazione skiplist nella libreria di base Java, ma puoi usare una delle implementazioni open source o implementarla tu stesso.

Il problema con PriorityQueue è che viene eseguito il backup da un array semplice, e la logica che ottiene gli elementi in ordine viene eseguita dalla cosa “coda [2 * n + 1] e coda [2 * (n + 1)]”. Funziona alla grande se si tira fuori dalla testa, ma lo rende inutile se si tenta di chiamare il .toArray su di esso ad un certo punto.

Ho risolto questo problema utilizzando com.google.common.collect.TreeMultimap, ma fornisco un comparatore personalizzato per i valori, racchiuso in un ordine, che non restituisce mai 0.

ex. per il doppio:

 private static final Ordering NoEqualOrder = Ordering.from(new Comparator() { @Override public int compare(Double d1, Double d2) { if (d1 < d2) { return -1; } else { return 1; } } }); 

In questo modo ottengo i valori nell'ordine quando chiamo .toArray () e ho anche dei duplicati.

Quello che vuoi è un albero di ricerca binario. Mantiene l’ordine ordinato mentre offre l’accesso logaritmico per le ricerche, le rimozioni e le inserzioni (a meno che tu non abbia un albero degenerato, quindi è lineare). È abbastanza facile da implementare e puoi addirittura implementare l’interfaccia List, ma l’accesso all’indice diventa complicato.

Il secondo approccio consiste nell’avere una ArrayList e quindi un’implementazione bubble sort. Poiché stai inserendo o rimuovendo un elemento alla volta, i tempi di accesso per gli inserimenti e le rimozioni sono lineari. Le ricerche sono costanti di accesso logaritmico e indice (i tempi possono essere diversi per LinkedList). L’unico codice di cui hai bisogno è 5, forse 6 linee di ordinamento a bolle.

Puoi usare Arraylist e Treemap, come hai detto che vuoi anche valori ripetuti, quindi non puoi usare TreeSet, anche se è ordinato, ma devi definire il comparatore.

Usa il metodo sort () per ordinare l’elenco come di seguito:

 List list = new ArrayList(); //add elements to the list Comparator comparator = new SomeComparator(); Collections.sort(list, comparator); 

Per riferimento vedi il link: http://tutorials.jenkov.com/java-collections/sorting.html

Usa TreeSet che fornisce elementi in ordine ordinato. O utilizzare Collection.sort() per l’ordinamento esterno con Comparator() .

 import java.util.TreeSet; public class Ass3 { TreeSetstr=new TreeSet(); str.add("dog"); str.add("doonkey"); str.add("rat"); str.add("rabbit"); str.add("elephant"); System.out.println(str); } 

con Java 8 Comparator, se vogliamo ordinare la lista, ecco le 10 città più popolate al mondo e vogliamo ordinarle per nome, come riportato da Time. Osaka, Giappone. … Città del Messico, Messico. … Pechino, Cina. … San Paolo, Brasile. … Mumbai, India. … Shanghai, Cina. … Delhi, India. … Tokyo, Giappone.

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