Collection triée en Java

161

Je suis un débutant en Java. Veuillez suggérer quelle (s) collection (s) peut / doivent être utilisée (s) pour maintenir une liste triée en Java. J'ai essayé Mapet Set, mais ce n'était pas ce que je cherchais.

b4hand
la source

Réponses:

188

Cela arrive très tard, mais il y a une classe dans le JDK juste dans le but d'avoir une liste triée. Il est nommé (quelque peu en désordre avec les autres Sorted*interfaces) " java.util.PriorityQueue". Il peut trier Comparable<?>s ou en utilisant un fichier Comparator.

La différence avec un Listtri en utilisant Collections.sort(...)est que cela maintiendra un ordre partiel à tout moment, avec des performances d'insertion O (log (n)), en utilisant une structure de données de tas, alors que l'insertion dans un tri ArrayListsera O (n) (c'est-à-dire, en utilisant la recherche binaire et le déplacement).

Cependant, contrairement à a List, PriorityQueuene prend pas en charge l'accès indexé ( get(5)), la seule façon d'accéder aux éléments d'un tas est de les retirer, un à la fois (d'où le nom PriorityQueue).

Martin Probst
la source
4
imo cette réponse mérite plus de votes positifs car elle souligne la seule collection qui a la capacité de JDK
nimcap
96
De la Javadoc: "L'itérateur fourni dans la méthode iterator () n'est pas garanti de traverser les éléments de la PriorityQueue dans un ordre particulier."
Christoffer Hammarström
10
@giraff: une file d'attente prioritaire n'est que cela, une structure de données très efficace pour garder une file d'attente prioritaire. Vous pouvez interroger de l'avant et obtenir les éléments de données dans un ordre trié. Cependant, les tas ne conservent pas un ordre total d'éléments en interne (c'est pourquoi ils sont si efficaces), il n'y a donc aucun moyen d'accéder aux éléments dans l'ordre sans exécuter l'opération d'interrogation.
Martin Probst
2
@chrispy cela dépend un peu de ce que vous voulez exactement faire avec votre structure de données. Les tas sont un moyen efficace de maintenir une liste d'éléments et de les récupérer de manière ordonnée plus tard - l'utilisation de l'itérateur ne fonctionne pas, mais si vous interrogez à partir de celui-ci, vous obtiendrez vos données dans l'ordre. La récupération est destructive, mais cela peut toujours être acceptable dans de nombreux cas. Je pense donc que cette réponse est bonne.
Martin Probst
4
@MartinProbst Veuillez rectifier votre réponse pour indiquer CLAIREMENT que cette collection NE PEUT PAS ÊTRE ITERATED dans l'ordre prévu. Comme beaucoup l'ont dit, c'est extrêmement trompeur!
Jorge Galvão
53

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

Michael Borgwardt
la source
27
Il y a cependant deux inconvénients majeurs à cela, le premier étant qu'un ensemble ne peut pas avoir de doublons. La seconde est que si vous utilisez une liste et Collections.sort (), vous avez tendance à trier constamment d'énormes listes et donne de mauvaises performances. Bien sûr, vous pouvez utiliser un drapeau «sale», mais ce n'est pas tout à fait la même chose.
Jeach
Cela amène à se demander si nous avons une option en Java qui permet les duplications et donne également des performances similaires à Set (Balanced Binary Tree)
mankadnandan
32

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

Neil Coffey
la source
11
n insertions sera O (n ^ 2). Un TreeSet vous donnera un code plus propre et O (n log n). OTOH, pour des modifications peu fréquentes , la recherche binaire d'un tableau sera plus rapide et utilisera moins de mémoire (donc moins de surcharge GC).
Tom Hawtin - tackline
Pour garder le code propre tout en autorisant les doublons, il serait assez facile de créer une classe SortedList qui insère les valeurs dans l'ordre trié.
Mr. Shiny and New 安 宇
C'est une réponse bien meilleure que la réponse la plus votée, imo, si vous pouvez vivre avec la mise en garde mentionnée par @ TomHawtin-tackline. Que l'itérateur fonctionne comme prévu est crucial dans la plupart des cas.
DuneCat
Incidemment, Tom a raison sur ce comportement spécifique: un ensemble d'arbres vous donnera une modification plus efficace. Mais un ensemble d'arbres n'est pas une liste (au sens strict d'avoir des éléments référencés par index et autorisant les doublons) et l'affiche a dit vouloir une liste.
Neil Coffey
Merci Neil, c'était vraiment génial!
vikingsteve
31

Utilisez la classe TreeMultiset de Google Guava . Guava a une API de collections spectaculaire.

Un problème avec la fourniture d'une implémentation de List qui maintient l'ordre trié est la promesse faite dans les JavaDocs de la add()méthode.

jtb
la source
Félicitations pour la suggestion multiset
darthtrevino
5
+1 pour avoir mentionné l'exigence qu'un Listajoute toujours à la fin.
Roland Illig
2
Notez que TreeMultiSet n'autorise toujours pas les éléments en double (les éléments qui compareTo () retourne 0, pas égal à () check). Si vous avez tendance à ajouter plus d'un élément de même priorité, cela ne fera qu'augmenter le nombre du premier élément ajouté, en rejetant les autres et en étant une bonne implémentation du sac de comptage.
bekce
12

Vous voulez que les SortedSet mises en œuvre, à savoir TreeSet .

cletus
la source
10
Pas nécessairement; les ensembles ne peuvent pas avoir de valeurs en double. Cela dépend des exigences du PO.
Zach Langley
12

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

Vous pouvez également utiliser les méthodes statiques de la classe Collections pour ce faire.

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

BenM
la source
10

Si vous souhaitez simplement trier 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 triés, utilisez un SortedSet .

Guillaume
la source
5

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

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

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

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 à la place (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 voulez éviter les insertions, vous pouvez également lancer une exception d'opération non prise en charge sur les méthodes "add" et "set".

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

... et aussi Vous devez être prudent avec les méthodes ListIterator car elles pourraient modifier votre liste interne. Dans ce cas, vous pouvez renvoyer une copie de la liste interne ou à nouveau lancer une exception.

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}
Carlos Verdes
la source
Le problème est que cela viole le Listcontrat. Il serait peut-être préférable de ne mettre en œuvre que Collection. Et si ContactListest trié, alors contains()peut être implémenté en utilisant binarySearchainsi pour être plus efficace.
Marcono1234
5

Le moyen le plus efficace d'implémenter une liste triée comme vous le souhaitez serait d'implémenter un skiplist indexable comme ici: Wikipedia: Indexable skiplist . Cela permettrait d'avoir des insertions / suppressions dans O (log (n)) et permettrait d'avoir un accès indexé en même temps. Et cela permettrait également les doublons.

Skiplist est une structure de données assez intéressante et, je dirais, sous-estimée. Malheureusement, il n'y a pas d'implémentation de skiplist indexée 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. Il existe des implémentations Skiplist régulières comme ConcurrentSkipListSet et ConcurrentSkipListMap

Vladich
la source
4

TreeSet ne fonctionnerait pas car ils n'autorisent pas les doublons et ne fournissent pas de méthode pour récupérer l'élément à 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 exigence de base pour une liste. Je pense que vous devez implémenter votre propre algorithme pour maintenir une liste triée en Java avec le temps d'insertion O (logn), 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 remplaçant la méthode equals afin que les doublons soient autorisés.

Giuseppe
la source
4

Utilisation de LambdaJ

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

Voici un exemple:

Trier itératif

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

Trier avec LambdaJ

List<Person> 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()));
Piazza Federico
la source
Dans votre dernier exemple avec l'expression lambda java 8, comment faire un tri inversé?
Rajat Shah
1
@RajatShah je suppose que vous pouvez le faire-(p1.getAge().compareTo(p2.getAge()))
Federico Piazza
@RajatShah heureux d'aider
Federico Piazza
2

Le problème avec PriorityQueue est qu'il est sauvegardé par un simple tableau, et la logique qui met les éléments dans l'ordre est effectuée 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 contourne ce problème en utilisant com.google.common.collect.TreeMultimap, mais je fournis un comparateur personnalisé pour les valeurs, enveloppé dans un Ordering, qui ne renvoie jamais 0.

ex. pour 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;
        }
    }
});

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

Martin Klosi
la source
1

Ce que vous voulez, c'est un arbre de recherche binaire. Il maintient un ordre trié tout en offrant un accès logarithmique pour les recherches, les suppressions et les insertions (sauf si vous avez un arbre dégénéré - alors il est linéaire). Il est assez facile à implémenter et vous pouvez même lui faire implémenter l'interface List, mais l'accès à l'index devient alors compliqué.

La deuxième approche consiste à avoir une ArrayList puis une implémentation de tri à bulles. Étant donné que vous insérez ou supprimez un élément à la fois, les temps d'accès pour les insertions et les suppressions sont linéaires. Les recherches sont logarithmiques et constantes d'accès à l'index (les heures peuvent être différentes pour LinkedList). Le seul code dont vous avez besoin est de 5, peut-être 6 lignes de tri à bulles.

Jakub Zaverka
la source
1

Vous pouvez utiliser Arraylist et Treemap, comme vous avez dit que vous vouliez également des valeurs répétées, vous ne pouvez pas utiliser TreeSet, bien qu'il soit également trié, mais vous devez définir un comparateur.


la source
1

Pour Set, vous pouvez utiliser TreeSet. TreeSet classe ses éléments sur la base d'un ordre naturel ou de tout ordre de tri passé au Comparable pour cet objet particulier. Pour la carte, utilisez TreeMap. TreeMap fournit le tri sur les clés. Pour ajouter un objet comme clé au TreeMap, cette classe doit implémenter une interface comparable qui à son tour oblige à implémenter la méthode compare to () qui contient la définition de l'ordre de tri. http://techmastertutorial.in/java-collection-impl.html

Avi Tyagi
la source
0

Utilisez la méthode sort () pour trier 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

Shashank Mungantiwar
la source
0

Utilisez TreeSetce qui donne les éléments dans l'ordre trié. OU utiliser Collection.sort()pour le tri externe avec Comparator().

Hari
la source
TreeSet n'autorise pas la duplication d'éléments. Parfois, c'est une fonctionnalité souhaitée, d'autres non. Considérant que l'OP a essayé les sets, je suppose que pour le non
usr-local-ΕΨΗΕΛΩΝ
Ne soyez pas méchant, indiquez
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
la source
0

avec Java 8 Comparator, si nous voulons trier la liste, voici les 10 villes les plus peuplées du monde et nous voulons les trier par nom, comme indiqué 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(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
la source
0

Trier une ArrayList selon des critères définis par l'utilisateur.

Classe de modèle

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

Classe de tri

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

Classe principale

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

Production

 Unsorted
 111 bbbb london
 131 aaaa nyc
 121 cccc jaipur

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