Collection triée en Java

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.

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

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

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

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.

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

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.

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 .

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

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

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.

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

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.

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.

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.

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

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

Utilisez TreeSetce qui donne les éléments dans l'ordre trié. OU utiliser Collection.sort()pour le tri externe avec 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);    
}

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

    }

}

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