Collection triée en Java

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é (un peu hors de l'ordre avec les autres Sorted* interfaces) " java.util.PriorityQueue ". Il peut trier soit Comparable<?> s ou en utilisant un Comparator .

la différence avec un List trié 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 tas, tandis que l'insertion dans un ArrayList trié sera O (n) (i.e., en utilisant la recherche binaire et le déplacement).

cependant, contrairement à un List , PriorityQueue ne supporte pas l'accès indexé ( get(5) ), la seule façon d'accéder aux articles dans un tas est de les sortir, un par un (d'où le nom PriorityQueue ).

TreeMap et TreeSet vous donneront une itération sur le contenu dans l'ordre trié. Ou vous pourriez utiliser un ArrayList et utiliser des Collections.sort() pour le tri. Tous ces cours sont en java.jusqu'à 151910920"

si vous voulez maintenir une liste triée que vous allez modifier fréquemment (c.-à-d. une structure qui, en plus d'être triée, permet des doublons et dont les éléments peuvent être référencés efficacement par index), puis utiliser un ArrayList mais quand vous avez besoin d'insérer un élément, toujours utiliser Collections.binarySearch () pour déterminer l'indice auquel vous ajoutez un élément donné. Cette dernière méthode vous indique l'index dont vous avez besoin pour insérer à garder votre liste dans l'ordre de tri.

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

un problème avec la mise en œuvre de List qui maintient l'ordre trié est la promesse faite dans les JavaDocs de la méthode add() .

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

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

voir Collections#sort(java.util.Liste) et TreeSet pour plus d'info.

vous voulez le SortedSet implémentations, à savoir TreeSet .

si vous voulez simplement trier une liste, utilisez n'importe quelle sorte 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 mettre en œuvre une liste 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 mis en place une nouvelle méthode" putOrdered " qui insère dans la bonne position si l'élément n'existe pas ou remplacer 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 voulez permettre des éléments répétés, il suffit d'implémenter 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 inserts vous pouvez également lancer et l'exception d'opération non supportée 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 de ListIterator parce qu'ils pourraient modifier votre liste interne. Dans ce cas, vous pouvez renvoyer une copie de la liste interne ou encore lancer une exception.

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

TreeSet ne fonctionnerait pas parce qu'ils ne permettent pas les doublons plus ils ne fournissent pas la méthode pour récupérer l'élément à la position spécifique. PriorityQueue ne fonctionnerait pas parce qu'il ne permet pas de récupérer des éléments à un poste spécifique qui est une exigence de base pour une liste. Je pense que vous avez besoin d'implémenter votre propre algorithme pour maintenir une liste triée en Java avec O(logn) insert time, à moins que vous n'ayez pas besoin de doublons. Peut-être qu'une solution pourrait être d'utiliser une bande de TreeMap où la clé est une sous-classe de l'élément qui supplante la méthode equals de sorte que les doublons soient autorisés.

Utilisant 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 /

voici un exemple:

Tri 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 d'impact de beauté dans la performance (une moyenne de 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()));

la manière la plus efficace de mettre en œuvre une liste triée comme vous le souhaitez serait d'implémenter une liste déroulante indexable comme ici: Wikipedia: liste déroulante Indexable . Cela permettrait d'avoir des insertions/suppressions en O(log(n)) et permettrait d'avoir un accès indexé dans le même temps. Et cela permettrait aussi les doublons.

Skiplist est une structure de données assez intéressante et, je dirais, sous-estimée. Malheureusement il n'y a pas de liste indexée implémentation dans la bibliothèque Java base, mais vous pouvez utiliser l'une des implémentations open source ou l'implémenter vous-même. Il y a des implémentations régulières de Skiplist comme et

le problème avec PriorityQueue est qu'il est soutenu par un tableau simple, et la logique qui obtient les éléments dans l'ordre est faite par la" queue[2*n+1] and queue[2*(n+1)] " thingie. Cela fonctionne bien si vous tirez juste de la tête, mais rend inutile si vous essayez d'appeler le .toArray à un moment donné.

je contourne ce problème en utilisant com.Google.commun.recueillir.TreeMultimap, mais je fournis un comparateur personnalisé pour les valeurs, enveloppé dans une commande, que 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 en ordre quand j'appelle .toArray(), et aussi avoir des doublons.

ce que vous voulez est un arbre de recherche binaire. Il maintient l'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 à mettre en œuvre et vous pouvez même le faire mettre en œuvre l'interface de liste, mais alors l'index-accès devient compliqué.

deuxième approche est d'avoir un ArrayList puis une mise en œuvre de tri de bulles. Parce que vous insérez ou retirez un élément à un temps, les temps d'accès pour les insertions et les retraits sont linéaires. Les recherches sont logarithmique et index constante d'accès (les temps peuvent varier pour LinkedList). Le seul code dont vous avez besoin est 5, peut-être 6 lignes de type bulle.

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

utiliser la méthode sort () pour trier la liste comme suit:

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

utiliser TreeSet qui donne les éléments dans l'ordre trié. Ou utilisez 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 alors voici les 10 villes les plus peuplées dans le monde et nous voulons Trier par nom, comme rapporté par le temps. Osaka, Japon. ... Mexico, Mexico. ... Beijing, Chine. ... São Paulo, Brésil. ... Mumbai, En Inde. ... Shanghai, China. ... Delhi, En 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);

    }

}