Collection sortingée en Java

Cela arrive très tard, mais il y a une classe dans le JDK juste pour avoir une liste sortingée. Il est nommé (quelque peu hors d’usage avec les autres interfaces Sorted* ) ” java.util.PriorityQueue “. Il peut sortinger soit Comparable S ou en utilisant un Comparator .

La différence avec une List sortingée à l’aide de Collections.sort(...) est que cela maintiendra un ordre partiel à tout moment, avec une performance d’insertion (log (n)), en utilisant une structure de données de tas, alors que l’insertion dans un sorting ArrayList sera O (n) (c’est-à-dire en utilisant la recherche et le déplacement binarys).

Cependant, contrairement à une List , PriorityQueue ne supporte pas l’access indexé ( get(5) ), le seul moyen d’accéder aux éléments d’un tas est de les sortir, un à la fois (donc le nom PriorityQueue ).

TreeMap et TreeSet vous donneront une itération sur le contenu dans l’ordre sortingé. Ou vous pouvez utiliser un ArrayList et utiliser Collections.sort () pour le sortinger. Toutes ces classes sont dans java.util

Si vous souhaitez conserver une liste sortingée que vous modifiez fréquemment (c’est-à-dire une structure qui, en plus d’être sortingée, autorise les doublons et dont les éléments peuvent être efficacement référencés par index), utilisez une ArrayList mais lorsque vous devez insérer un élément , utilisez toujours Collections.binarySearch () pour déterminer l’index auquel vous ajoutez un élément donné. Cette dernière méthode vous indique l’index à insérer pour conserver votre liste dans l’ordre sortingé.

Utilisez TreeMultiset de Google Goyave. La goyave est une API de collections spectaculaire.

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

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

La promesse faite dans les Javadocs de la méthode ‘add’ est un problème lié à la mise en œuvre d’une implémentation de List qui conserve l’ordre sortingé.

Il y a quelques options. Je suggère TreeSet si vous ne voulez pas de doublons et que les objects que vous insérez sont comparables.

Pour ce faire, vous pouvez également utiliser les méthodes statiques de la classe Collections.

Voir Collections # sort (java.util.List) et TreeSet pour plus d’informations.

Vous voulez les implémentations SortedSet , à savoir TreeSet .

Si vous voulez simplement sortinger une liste, utilisez n’importe quel type de liste et utilisez Collections.sort () . Si vous voulez vous assurer que les éléments de la liste sont uniques et toujours sortingés, utilisez un SortedSet .

Ce que j’ai fait, c’est implémenter List avec une instance interne avec toutes les méthodes déléguées.

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

Après, j’ai implémenté une nouvelle méthode “putOrdered” qui insère dans la position correcte si l’élément n’existe pas ou remplace juste au cas où il existerait.

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

Si vous souhaitez autoriser des éléments répétés, implémentez simplement addOrdered (ou les deux).

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

Si vous souhaitez éviter les insertions, vous pouvez également lancer une exception d'opération non prise en charge sur les méthodes "Ajouter" et "Définir".

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

... et aussi Vous devez faire attention aux méthodes ListIterator car elles peuvent modifier votre liste interne. Dans ce cas, vous pouvez retourner une copie de la liste interne ou lancer à nouveau une exception.

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

TreeSet ne fonctionnerait pas car ils n’autorisent pas les doublons et ne fournissent pas de méthode pour récupérer les éléments à une position spécifique. PriorityQueue ne fonctionnerait pas car il ne permet pas de récupérer des éléments à une position spécifique, ce qui est une condition de base pour une liste. Je pense que vous devez implémenter votre propre algorithme pour maintenir une liste sortingée dans Java avec O (logn) insert time, sauf si vous n’avez pas besoin de doublons. Une solution pourrait peut-être utiliser un TreeMap où la clé est une sous-classe de l’élément qui remplace la méthode equals afin que les doublons soient autorisés.

Utiliser LambdaJ

Vous pouvez essayer de résoudre ces tâches avec LambdaJ si vous utilisez des versions antérieures à Java 8. Vous pouvez le trouver ici: http://code.google.com/p/lambdaj/

Ici vous avez un exemple:

Sort Iterative

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

Trier avec LambdaJ

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

Bien sûr, avoir ce genre de beauté a un impact sur la performance (en moyenne 2 fois), mais pouvez-vous trouver un code plus lisible?

Trier avec Java 8 en utilisant l’expression lambda

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

Le moyen le plus efficace d’implémenter une liste sortingée comme vous le souhaitez serait d’implémenter un skiplist indexable comme ici: Wikipedia: Skiplist indexable . Cela permettrait d’avoir des insertions / retraits dans O (log (n)) et permettrait d’avoir un access indexé en même temps. Et cela permettrait également les doublons.

Skiplist est une structure de données très intéressante et, je dirais, sous-estimée. Malheureusement, il n’y a pas d’implémentation skiplist dans la bibliothèque de base Java, mais vous pouvez utiliser l’une des implémentations open source ou l’implémenter vous-même.

Le problème avec PriorityQueue est qu’il est sauvegardé par un tableau simple, et la logique qui obtient les éléments dans l’ordre est faite par le truc “queue [2 * n + 1] et queue [2 * (n + 1)]”. Cela fonctionne très bien si vous tirez simplement de la tête, mais le rend inutile si vous essayez d’appeler le .toArray dessus à un moment donné.

Je contourner ce problème en utilisant com.google.common.collect.TreeMultimap, mais je fournis un comparateur personnalisé pour les valeurs, enveloppé dans un ordre, qui ne renvoie jamais 0.

ex. pour Double:

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

De cette façon, j'obtiens les valeurs dans l'ordre lorsque j'appelle .toArray (), et j'ai également des doublons.

Ce que vous voulez, c’est un arbre de recherche binary. Il maintient l’ordre sortingé tout en offrant un access logarithmique pour les recherches, les suppressions et les insertions (sauf si vous avez un arbre dégénéré – alors c’est linéaire). Il est assez facile à implémenter et vous pouvez même le faire implémenter l’interface List, mais alors, l’access à l’index devient compliqué.

La deuxième approche consiste à avoir une ArrayList puis une implémentation de sorting par bulles. Comme vous insérez ou supprimez un élément à la fois, les temps d’access aux insertions et aux retraits sont linéaires. Les recherches sont logarithmiques et l’access à l’index est constant (les temps peuvent être différents pour LinkedList). Le seul code dont vous avez besoin est 5, peut-être 6 lignes de sorting à bulles.

Vous pouvez utiliser Arraylist et Treemap, car vous avez dit vouloir des valeurs répétées, mais vous ne pouvez pas utiliser TreeSet, bien qu’il soit également sortingé, mais vous devez définir un comparateur.

Utilisez la méthode sort () pour sortinger la liste comme ci-dessous:

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

Pour référence, voir le lien: http://tutorials.jenkov.com/java-collections/sorting.html

Utilisez TreeSet qui donne des éléments dans l’ordre sortingé. OU utilisez Collection.sort() pour le sorting externe avec 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); } 

avec Java 8 Comparator, si nous voulons sortinger la liste, voici les 10 villes les plus peuplées du monde et nous souhaitons les sortinger par nom, tel que rapporté par Time. Osaka, Japon. … Mexico, Mexique. … Pékin, Chine. … São Paulo, Brésil. … Mumbai, Inde. … Shangai, Chine. … Delhi, Inde. … Tokyo, Japon.

  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(Ssortingng[] 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(Ssortingng.CASE_INSENSITIVE_ORDER) & Sorting List is:-"); cities.sort(Ssortingng.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); } }