Pourquoi n'y a-t-il pas de SortedList en Java?

503

En Java, il y a les interfaces SortedSetet SortedMap. Les deux appartiennent au framework Java Collections et fournissent un moyen trié d'accéder aux éléments.

Cependant, à ma connaissance, il n'y SortedListen a pas en Java. Vous pouvez utiliser java.util.Collections.sort()pour trier une liste.

Une idée pourquoi il est conçu comme ça?

Jijoy
la source
6
alors quel est votre résultat attendu lors de l'insertion d'un élément au milieu de la liste?
bestsss
4
@bestsss Il serait tout à fait possible d'avoir une classe SortedList qui n'implémente pas l'interface java.util.List. Lisez la question pour savoir pourquoi aucune structure de données ne prend en charge la fonctionnalité demandée. Ne vous laissez pas distraire par des détails insignifiants tels que la dénomination.
Alderath
@Alderath, la structure habituelle est un arbre (rouge / noir, avl ou btree) avec des liens supplémentaires prev / next pour prendre en charge la commande. J'utilise une structure similaire rouge / noir avec des liens prev / next. C'est une utilisation assez niche, cependant. L'arbre peut être parcouru à la fois dans l'ordre et dans l'ordre d'insertion, a O (logn) find / contains mais get (int) est O (n). Étant donné son applicabilité de niche, je suppose que les développeurs ont laissé le soin d'en implémenter un s'ils en avaient besoin.
bestsss
3
Ne répondant pas à la question «pourquoi», mais la solution de contournement la plus simple pour TreeSet consiste à utiliser un comparateur qui ne renvoie jamais zéro, par exemple, int diff = this.score - that.score; return (diff == 0) ? 1 : diff; car il s'agit d'un hack malodorant, je fournirais cela comme argument constructeur anonyme plutôt que d'avoir n'importe quel implémenter Comparable.
earcam

Réponses:

682

Les itérateurs de liste garantissent avant tout que vous obtenez les éléments de la liste dans l'ordre interne de la liste (aka. Ordre d'insertion ). Plus précisément, c'est dans l'ordre dans lequel vous avez inséré les éléments ou dans la façon dont vous avez manipulé la liste. Le tri peut être considéré comme une manipulation de la structure des données, et il existe plusieurs façons de trier la liste.

Je vais ordonner les chemins dans l'ordre d' utilité tel que je le vois personnellement:

1. Pensez à utiliser Setou Bagcollections à la place

REMARQUE: je mets cette option en haut parce que c'est ce que vous voulez normalement faire de toute façon.

Un ensemble trié trie automatiquement la collection à l'insertion , ce qui signifie qu'il effectue le tri pendant que vous ajoutez des éléments dans la collection. Cela signifie également que vous n'avez pas besoin de le trier manuellement.

De plus, si vous êtes sûr de ne pas avoir à vous soucier (ou d'avoir) des éléments en double, vous pouvez utiliser le à la TreeSet<T>place. Il implémente SortedSetet NavigableSetinterface et fonctionne comme vous l'attendriez probablement d'une liste:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Si vous ne voulez pas l'ordre naturel, vous pouvez utiliser le paramètre constructeur qui prend a Comparator<T>.

Alternativement, vous pouvez utiliser des multisets (également appelés sacs ) , c'est-à-dire Setqui autorisent les éléments en double, et il existe des implémentations tierces. Plus particulièrement à partir des bibliothèques de Guava, il y en a un TreeMultiset, qui fonctionne beaucoup comme le TreeSet.

2. Triez votre liste avec Collections.sort()

Comme mentionné ci-dessus, le tri de Lists est une manipulation de la structure des données. Donc, pour les situations où vous avez besoin d'une "source de vérité" qui sera triée de différentes manières, puis la trier manuellement est la voie à suivre.

Vous pouvez trier votre liste avec la java.util.Collections.sort()méthode. Voici un exemple de code expliquant comment:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Utiliser des comparateurs

Un avantage évident est que vous pouvez l'utiliser Comparatordans la sortméthode. Java fournit également quelques implémentations pour le Comparatortel que le Collatorqui est utile pour les chaînes de tri sensibles aux paramètres régionaux. Voici un exemple:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Tri dans des environnements simultanés

Notez cependant que l'utilisation de la sortméthode n'est pas conviviale dans les environnements simultanés, car l'instance de collection sera manipulée, et vous devriez plutôt envisager d'utiliser des collections immuables. C'est quelque chose que Guava fournit dans la Orderingclasse et c'est un simple doublure:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Enveloppez votre liste avec java.util.PriorityQueue

Bien qu'il n'y ait pas de liste triée en Java, il existe cependant une file d'attente triée qui fonctionnerait probablement aussi bien pour vous. C'est la java.util.PriorityQueueclasse.

Nico Haase a lié dans les commentaires une question connexe qui répond également à cela.

Dans une collection triée, vous ne voulez probablement pas manipuler la structure de données interne, c'est pourquoi PriorityQueue n'implémente pas l'interface List (car cela vous donnerait un accès direct à ses éléments).

Avertissement sur l' PriorityQueueitérateur

La PriorityQueueclasse implémente les interfaces Iterable<E>et Collection<E>afin qu'elle puisse être itérée comme d'habitude. Cependant, l'itérateur n'est pas garanti de renvoyer les éléments dans l'ordre trié. Au lieu de cela (comme le souligne Alderath dans les commentaires), vous devez mettre poll()la file d'attente jusqu'à ce qu'elle soit vide.

Notez que vous pouvez convertir une liste en file d'attente prioritaire via le constructeur qui prend n'importe quelle collection :

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Écrivez votre propre SortedListclasse

REMARQUE: vous ne devriez pas avoir à le faire.

Vous pouvez écrire votre propre classe List qui trie chaque fois que vous ajoutez un nouvel élément. Cela peut être assez lourd à calculer en fonction de votre implémentation et est inutile , sauf si vous voulez le faire comme un exercice, pour deux raisons principales:

  1. Il rompt le contrat de l' List<E>interface car les addméthodes doivent garantir que l'élément résidera dans l'index spécifié par l'utilisateur.
  2. Pourquoi réinventer la roue? Vous devez utiliser le TreeSet ou les Multisets à la place, comme indiqué au premier point ci-dessus.

Cependant, si vous voulez le faire comme un exercice, voici un exemple de code pour vous aider à démarrer, il utilise la AbstractListclasse abstraite:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Notez que si vous n'avez pas remplacé les méthodes dont vous avez besoin, les implémentations par défaut de AbstractListjetteront UnsupportedOperationExceptions.

Spoike
la source
12
+1. Imo, c'est plus constructif que la réponse la plus votée. Il est cependant livré avec deux inconvénients mineurs. PriorityQueue ne prend pas en charge l'accès aléatoire. Vous ne pouvez pas faire un aperçu (elementIndex). Vous ne pouvez donc pas faire par exemple Integer maxVal = prioQueue.peek(prioQueue.size() - 1);. Deuxièmement, si vous avez l'intention d'utiliser le PriorityQueue simplement comme une liste triée, cela semblera moins intuitif à voir PriorityQueuedans le code qu'il ne l'aurait été SortedListsi une telle structure de données avait existé.
Alderath
12
Et, après avoir examiné l'autre question que quelqu'un a liée dans les commentaires, un autre gros inconvénient est que l'itérateur de PriorityQueue n'est pas garanti de renvoyer les éléments dans un ordre spécifique. Donc, à moins que j'oublie quelque chose, la seule façon, par exemple, d'imprimer tous les objets dans PriorityQueue afin de poll () répéter la file d'attente jusqu'à ce qu'elle soit vide. Pour moi, cela semble à la limite du redémarrage. Pour imprimer deux fois les objets d'une PriorityQueue, vous devez d'abord copier la PriorityQueue, puis interroger () tous les objets de la PriorityQueue d'origine, puis pol () l tous les objets de la copie.
Alderath
1
Hmm ... on dirait que tu as raison Alderath. Vous ne pouvez pas utiliser l'itérateur de PriorityQueue pour obtenir les éléments dans l'ordre attendu. On dirait que je dois modifier ma réponse.
Spoike
7
La file d'attente prioritaire n'est qu'un tas, vous ne pouvez accéder qu'au sommet, imo cela n'appartient pas à la réponse de la question.
bestsss
1
Il convient également de noter que Collections.sort()vous permet même de définir la fonction de comparaison utilisée pour trier, en utilisant un Comparatorobjet.
Mike 'Pomax' Kamermans
71

Parce que le concept d'une Liste est incompatible avec le concept d'une collection triée automatiquement. Le point d'une liste est qu'après l'appel list.add(7, elem), un appel à list.get(7)retournera elem. Avec une liste triée automatiquement, l'élément pourrait se retrouver dans une position arbitraire.

Michael Borgwardt
la source
Le concept de la liste implique qu'il y a un certain ordre et que l' list.get(n)opération sera déterministe, ce qui signifie qu'elle retournera toujours le même élément en position ntant que la liste n'est pas modifiée. Je ne suis pas d'accord que le "concept de liste" exige que ce soit l'ordre d'insertion. Oui, l' Listinterface propose une list.add(index, element)méthode qui n'a pas de sens pour une collection triée, mais elle est facultative selon les documents.
matt-pielat il y a
26

Étant donné que toutes les listes sont déjà "triées" par l'ordre dans lequel les articles ont été ajoutés (ordre FIFO), vous pouvez les "recentrer" avec un autre ordre, y compris l'ordre naturel des éléments, à l'aide de java.util.Collections.sort().

ÉDITER:

Les listes, car les structures de données sont basées sur ce qui est intéressant, c'est l'ordre dans lequel les éléments ont été insérés.

Les ensembles n'ont pas cette information.

Si vous souhaitez commander en ajoutant du temps, utilisez List. Si vous souhaitez commander selon d'autres critères, utilisez SortedSet.

SJuan76
la source
22
L'ensemble ne permet pas les doublons
bestsss
10
Je ne pense pas que ce soit une très bonne réponse. Bien sûr, les listes de l'API Java ont un ordre spécifique déterminé par quand / comment les éléments ont été insérés. Cependant, l'existence de listes ordonnées d'une manière qui dépend de la méthode / du temps d'insertion n'empêche pas d'avoir d'autres structures de données dans lesquelles l'ordre est déterminé d'une autre manière (par exemple par un comparateur). Fondamentalement, l'OP demande pourquoi il n'y a pas une structure de données équivalente à un SortedSet à l'exception que la structure de données devrait permettre plusieurs occurrences d'éléments qui sont égaux.
Alderath
5
Donc, ma question de suivi serait: " Pourquoi n'y a-t-il pas de structure de données qui fonctionne comme un SortedSet, mais qui peut contenir plusieurs éléments égaux? " (Et s'il vous plaît ne répondez pas " parce que les ensembles ne peuvent contenir qu'un seul élément ")
Alderath
@Alderath: Voir stackoverflow.com/questions/416266/sorted-collection-in-java . En bref: utilisez TreeMultiset de Guava
Janus Troelsen
4
Les listes NE SONT PAS "triées", même si vous mettez le "trié" entre guillemets. Ils sont commandés.
Koray Tugay
21

Set et Map sont une structure de données non linéaire. La liste est une structure de données linéaire.

entrez la description de l'image ici


La structure de données d'arborescence SortedSetet les SortedMapinterfaces implémentent TreeSetet TreeMaputilisent respectivement l' algorithme d'implémentation d' arbre rouge-noir utilisé. Ainsi, il s'assure qu'il n'y a pas d'articles en double (ou de clés en cas de Map).

  • List maintient déjà une collection ordonnée et une structure de données basée sur un index, les arbres ne sont pas des structures de données basées sur un index.
  • Tree par définition, ne peut pas contenir de doublons.
  • En Listnous pouvons avoir des doublons, donc il n'y en a pas TreeList(c'est-à-dire non SortedList).
  • La liste conserve les éléments dans l'ordre d'insertion. Donc, si nous voulons trier la liste, nous devons utiliser java.util.Collections.sort(). Il trie la liste spécifiée par ordre croissant, selon l'ordre naturel de ses éléments.
Premraj
la source
14

JavaFX SortedList

Bien que cela ait pris un certain temps, Java 8 a un tri List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Comme vous pouvez le voir dans les javadocs, il fait partie des collections JavaFX , destiné à fournir une vue triée sur une ObservableList.

Mise à jour: Notez qu'avec Java 11, la boîte à outils JavaFX s'est déplacée en dehors du JDK et est maintenant une bibliothèque distincte. JavaFX 11 est disponible en tant que SDK téléchargeable ou depuis MavenCentral. Voir https://openjfx.io

swpalmer
la source
2
Malheureusement, cette SortedList ne fonctionne pas comme une liste habituelle - par exemple, elle n'a pas de constructeur par défaut (vous devez la construire en utilisant une ObservableList, quoi que cela signifie ...)
Erel Segal-Halevi
La SortedList de JavaFX est clairement destinée à l'utilisation de composants GUI et en raison de la surcharge PAS adaptée pour avoir simplement une liste d'objets triés. Cela signifierait également de référencer l'ensemble du module FX même si l'interface graphique n'est pas utilisée dans le projet.
COBRA.cH
1
@ COBRA.cH Oui, c'est vrai. Une liste triée plus performante pourrait probablement être une enveloppe mince autour d'un TreeMap, où un entier est utilisé pour compter les doublons de la clé. Vous pouvez également utiliser un TreeSet avec un comparateur qui ne renvoie jamais 0.
swpalmer
Pourquoi les votes négatifs? La question commence par un présupposé qu'il n'y a pas de liste triée dans les bibliothèques JDK. Cette réponse corrige cette hypothèse. Que vous aimiez ou n'aimiez pas la mise en œuvre de cette liste triée particulière n'est pas une raison pour voter contre. Cette réponse ne recommande pas la classe, souligne simplement son existence.
Basil Bourque
10

Pour tous les nouveaux arrivants, depuis avril 2015, Android dispose désormais d'une classe SortedList dans la bibliothèque de support, conçue spécifiquement pour fonctionner avec RecyclerView. Voici le blog à ce sujet.

Amagi82
la source
1
Il convient de noter qu'au moment de ce commentaire, Androids SortedList ne prend pas en charge la fonctionnalité onItemMoved () avec RecyclerView. Écrire ma propre SortedList qui est moins efficace est ce que je devais faire pour contourner les limitations.
Matthew
4

Un autre point est la complexité temporelle des opérations d'insertion. Pour une insertion de liste, on attend une complexité de O (1). Mais cela ne pouvait pas être garanti avec une liste triée.

Et le point le plus important est que les listes n'assument rien de leurs éléments. Par exemple, vous pouvez créer des listes de choses qui n'implémentent pas equalsou compare.

Ingo
la source
vous pouvez avoir une liste sans O (logn) insert / delete / find / contains mais pas avec get (int).
bestsss
3
Le dernier point n'est pas vraiment une bonne explication. Vous pouvez créer SortedSetdes choses qui ne sont pas implémentées Comparable. Voir ce constructeur TreeSet .
Alderath
1
@Alderath - peut-être que ma formulation était trop faible. Pourtant, l'observation soutient que les éléments des ensembles et des clés des arbres doivent être comparables au moins pour l'égalité, alors que les éléments de liste n'ont pas besoin. Que la relation d'ordre / égalité pour les ensembles et les arbres soit implémentée dans un comparateur ou ailleurs est sans importance - mais vous en avez besoin.
Ingo
Les listes ne garantissent pas l' insertion de O (1) , elles garantissent l' accès à O (1) . bigocheatsheet.com
Matt Quigley
1
@Betlista vous avez raison! Je ne peux pas mettre à jour mon commentaire, mais l' Listinterface Java ne garantit aucune spécification de performance sur ses méthodes.
Matt Quigley
3

Pensez-y comme ceci: l' Listinterface a des méthodes comme add(int index, E element),set(int index, E element) . Le contrat est qu'une fois que vous avez ajouté un élément à la position X, vous le trouverez là, sauf si vous ajoutez ou supprimez des éléments avant lui.

Si une implémentation de liste stockait des éléments dans un ordre différent de celui basé sur l'index, les méthodes de liste ci-dessus n'auraient aucun sens.

Costi Ciudatu
la source
2

La première ligne de l'API List indique qu'il s'agit d'une collection ordonnée (également appelée séquence). Si vous triez la liste, vous ne pouvez pas maintenir l'ordre, il n'y a donc pas de TreeList en Java.
Comme le dit l'API, Java List s'est inspiré de Sequence et affiche les propriétés de la séquence http://en.wikipedia.org/wiki/Sequence_(mathematics )

Cela ne signifie pas que vous ne pouvez pas trier la liste, mais Java strict à sa définition et ne fournit pas de versions triées des listes par défaut.

Syam
la source
2

Dans le cas où vous cherchez un moyen de trier les éléments, mais aussi d'être en mesure d'y accéder par index de manière efficace, vous pouvez faire ce qui suit:

  1. Utilisez une liste d'accès aléatoire pour le stockage (par exemple ArrayList)
  2. Assurez-vous qu'il est toujours trié

Ensuite, pour ajouter ou supprimer un élément, vous pouvez utiliser Collections.binarySearchpour obtenir l'index d'insertion / suppression. Étant donné que votre liste implémente l'accès aléatoire, vous pouvez modifier efficacement la liste avec l'index déterminé.

Exemple:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}
Marcono1234
la source
1

Pensez à utiliser une arborescence indexée . Il s'agit d'un TreeSet JDK amélioré qui permet d'accéder à l'élément par index et de rechercher l'index d'un élément sans itération ni listes sous-jacentes cachées qui sauvegardent l'arborescence. L'algorithme est basé sur la mise à jour des poids des nœuds changeants à chaque fois qu'il y a un changement.

Vitaly Sazanovich
la source