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é Map
et Set
, mais ce n'était pas ce que je cherchais.
la source
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é Map
et 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 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 de tas, alors que l'insertion dans un tri ArrayList
sera O (n) (c'est-à-dire, en utilisant la recherche binaire et le déplacement).
Cependant, contrairement à a List
, PriorityQueue
ne 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
la source
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é.
la source
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.la source
List
ajoute toujours à la fin.Vous voulez que les SortedSet mises en œuvre, à savoir TreeSet .
la source
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.
la source
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 .
la source
Ce que j'ai fait, c'est implémenter List ayant une instance interne avec toutes les méthodes déléguées.
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.
Si vous souhaitez autoriser des éléments répétés, implémentez simplement addOrdered à la place (ou les deux).
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".
... 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.
la source
List
contrat. Il serait peut-être préférable de ne mettre en œuvre queCollection
. Et siContactList
est trié, alorscontains()
peut être implémenté en utilisantbinarySearch
ainsi pour être plus efficace.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
la source
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.
la source
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
Trier avec LambdaJ
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
la source
-(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:
De cette façon, j'obtiens les valeurs dans l'ordre lorsque j'appelle .toArray (), et j'ai également des doublons.
la source
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.
la source
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
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
la source
Utilisez la méthode sort () pour trier la liste comme ci-dessous:
Pour référence, voir le lien: http://tutorials.jenkov.com/java-collections/sorting.html
la source
Utilisez
TreeSet
ce qui donne les éléments dans l'ordre trié. OU utiliserCollection.sort()
pour le tri externe avecComparator()
.la source
la source
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.
la source
Trier une ArrayList selon des critères définis par l'utilisateur.
Classe de modèle
Classe de tri
Classe principale
Production
la source