Un moyen rapide de trouver des valeurs uniques dans la liste
Donné une liste de KeyValuePairs, où chaque paire possède un getValue()
méthode, ce serait le moyen le plus rapide pour obtenir un List
(ou Set
) de Valeurs uniques?
Tous les dessous de produire de résultat acceptable. u1
semble être la plus rapide au cours d'une taille de la liste (environ 1000-2000 KVP)
Pouvons-nous faire mieux (plus rapide)?
private static Set<String> u1(List<_KVPair> pairs) {
Set<String> undefined = new HashSet<String>();
for (_KVPair pair : pairs) {
undefined.add(pair.getValue());
}
if (undefined.size() == 1) {
return new HashSet<String>();
}
return undefined;
}
private static List<String> u2(List<_KVPair> pairs) {
List<String> undefined = new ArrayList<String>();
for (_KVPair pair : pairs) {
if (!undefined.contains(pair.getValue())) {
undefined.add(pair.getValue());
}
}
return undefined;
}
private static List<String> u3(List<_KVPair> pairs) {
List<String> undefined = new LinkedList<String>();
Iterator<_KVPair> it = pairs.iterator();
while (it.hasNext()) {
String value = it.next().getValue();
if (!undefined.contains(value)) {
undefined.add(value);
}
}
return undefined;
}
À environ 3600 paires, 'u3' gagne. À environ 1500 paires, 'u1' gagne
Ce qui se passe quand vous l'essayer? Qui a le temps le plus bas de la complexité?
Il semble que la première est la plus rapide.
.. et il a le temps le plus bas de la complexité, O(N) vs O(N^2)
Je voudrais assurez-vous que vous exécutez les tests pour au moins 2 à 5 secondes, sinon vous obtiendrez des résultats qui ne sont pas reproduire-mesure.
Un ensemble est une collection qui ne contient que des valeurs uniques. Généralement, le moyen le plus rapide pour trouver les valeurs uniques d'une grande collection de valeurs est d'ajouter toutes les valeurs d'un ensemble, à l'origine de tous les doublons à disparaître depuis la méthode add pour le définir simplement les ignorer l'entrée si celle-ci existe déjà dans le jeu.
Il semble que la première est la plus rapide.
.. et il a le temps le plus bas de la complexité, O(N) vs O(N^2)
Je voudrais assurez-vous que vous exécutez les tests pour au moins 2 à 5 secondes, sinon vous obtiendrez des résultats qui ne sont pas reproduire-mesure.
Un ensemble est une collection qui ne contient que des valeurs uniques. Généralement, le moyen le plus rapide pour trouver les valeurs uniques d'une grande collection de valeurs est d'ajouter toutes les valeurs d'un ensemble, à l'origine de tous les doublons à disparaître depuis la méthode add pour le définir simplement les ignorer l'entrée si celle-ci existe déjà dans le jeu.
OriginalL'auteur JAM | 2012-09-25
Vous devez vous connecter pour publier un commentaire.
Première option devrait être plus rapide. Vous pourriez peut-être le rendre encore plus rapide par le dimensionnement de l'ensemble avant de l'utiliser. En règle générale, si vous vous attendez à un petit nombre de doublons:
Notez que j'ai utilisé 1 pour le facteur de charge pour éviter tout redimensionnement.
Par curiosité, j'ai couru un test (code ci-dessous) - les résultats sont (après compilation):
Test 1 (note: ne prend que quelques minutes à réchauffer)
Test 2
Ce type de logique:
List#contains
va courir assez vite qu'un duplicata sera trouvée plus rapidement et le coût de l'allocation d'un grand jeu + l'algorithme de hachage sont pénaliserComment voulez-vous exécuter vos tests? Combien de fois avez-vous exécuter? Combien de doublons? Aussi pour 3000 valeurs, la méthode sera probablement exécuté dans quelques millisecondes de sorte que la précision de l'horloge qui pourrait fausser certains résultats.
u1 crée juste un jeu, il ne retirez pas elemetns qui ont été dupliqués dans la liste d'origine. Supprime juste la duplication.
il semble que vous pourriez être l'évaluation de votre code de mal. Vous devez exécuter les méthodes de test des dizaines ou des centaines de fois pour éviter la mesure de toute "warm-up" des coûts. Voir stackoverflow.com/questions/504103/...
assurez-vous également KVPair implémente equals() et hashCode()
OriginalL'auteur assylias
Vous serez en mesure d'accélérer la
u1
par la modification de la première ligne:Que sinon, l'ensemble en interne ont pour redimensionner un lot que vous ajoutez des valeurs.
Bon point, bien que son intérêt est de mon bien-être de la façon dont de nombreuses unique de valeurs dans la liste...
Et bien... C'est toujours un compromis... Si vous avez un million de paires clé-valeur avec seulement une poignée de valeurs uniques, cette solution serait gaspiller de l'espace. Depuis l'occasionnel besoins de la mémoire tampon redimensionne seulement ajouter de la méthode de l'amortissement constant d'exécution de la méthode add, tampon redimensionne ne doit pas être trop grand d'un problème. Toutefois, si l'opération est extrêmement critique pour les performances, je suis d'accord que guesstimating capacité requise est probablement une bonne idée (tant que l'estimation est basée sur une hypothèse raisonnable sur les attendus des entrées).
peut-être que le doublement de la taille permettrait d'éviter de ressasser à tous mais certainement la mémoire des déchets.
pourquoi il semble une mauvaise idée? Si vous savez que le jeu ne doit contenir de N éléments, je ne pense pas que vous avez vraiment besoin de dépenser de l'espace sur veillant à ce qu'il peut assurer que le N+1) ème élément efficacement
OriginalL'auteur beny23
Mise à jour: voir modifier en dessous de
Il est inutile de parcourir la liste si vous pouviez juste faire
La pire option est u2 et u3, où vous êtes l'ajout d'éléments dans la première liste à une deuxième liste et appeler
List.contains(item)
à chaque itération de la boucle. Cette opération approchesO(n^2)
-List.contains(item)
besoins de comparer l'élément potentiellement l'ensemble de la liste. Éviter les algorithmes où vous avez besoin d'itérer sur une liste et appeler une opération qui a également itère sur la liste.Si vous voulez des objets uniques, utiliser un
Set
. Si vous avez besoin de ces éléments dans l'ordre de tri, utilisez unTreeSet
, sinon 99% du temps, vous voulez unHashSet
.modifier: j'ai raté que vous voulez obtenir un ensemble de
pair.getValue()
; mais le conseil est le même, peu importe l'utilisation d'un Ensemble, ne pas utiliser deList.contains()
dans une boucle.Vous vous rendez compte que la liste des paires ne contient pas d'objets String, non?
Je suis seulement intéressé par les différentes valeurs de la paire, pas paires eux-mêmes. Les touches peuvent ainsi être identique ou différent, n'a pas d'importance.
ajout d'une édition, mais les conseils reste le même - l'utilisation d'un Ensemble. Ajouter un tas d'éléments à un Ensemble dans une boucle rapport à la construction de l'ensemble avec
new HashSet(collection)
a la même complexité.Généralement, la valeur de hachage d'une valeur de clé paire serait la valeur de hachage de la clé, la solution proposée serait de générer un ensemble avec des clés uniques, mais pas nécessairement des valeurs uniques.
OriginalL'auteur matt b
Je crois que l'option 1 est la plus rapide et la plus propre. Il est difficile à battre hachage en termes de vérifier si la valeur contient déjà là.
Liste en fonction de la solution n'est pas à l'échelle comme dit dans la réponse précédente
OriginalL'auteur Konstantin Pribluda
Une autre méthode pourrait être
Sort list
puis dans une boucle, vous pouvez éliminer les doublons en gardant la référence du dernier élément ajouté si la référence est égal de ne pas ajouter à la nouvelle liste d'autres sages ajouterEnsuite, vous aurez à mettre en œuvre une liste personnalisée qui contient également hashmap et de mettre en œuvre la méthode qui permettra d'éviter les doublons par juste retour d'éléments de chaque seau.
OriginalL'auteur Amit Deshpande
Aucune des réponses données à supprimer les doublons du résultat final, ils ont juste supprimer la duplication. Donc, si une chaîne est présente deux fois, il sera toujours présente dans le résultat final, mais juste une fois. Si ce n'est pas nécessaire, et bien oui, j'ai juste perdu cinq minutes ...
exactement mon point de vue, le code n'est pas de "trouver des valeurs uniques dans la liste". Il fait tout simplement un ensemble d'éléments uniques.
Je suis d'accord, mais il ressemble à ce que l'op veut, c'est un ensemble d'éléments uniques. Ce n'est certes pas clair.
Je suppose que c'est une question de mauvais et ambiguë exigences/spécifications. Soit, vous pouvez interpréter la question "d'obtenir une liste de toutes les valeurs de la liste d'origine qu'une seule fois dans la liste d'origine" ou vous pouvez l'interpréter comme "obtenir une liste de toutes les valeurs qui se produisent dans la liste d'origine, et de veiller à ce que chaque valeur se produit qu'une seule fois dans cette liste de sortie". Il est difficile de savoir si l'unique se réfère uniquement à la sortie ou à l'entrée.
Mais ce n'était pas la façon dont la question a été formulée. La question était: "...ce serait le moyen le plus rapide pour obtenir une Liste (ou un Ensemble) de Valeurs uniques?". Strictement parlant, j'irais même jusqu'à soutenir que
return Arrays.asList(1, 2);
pourrait être une réponse à la question, parce que c'est une liste de valeurs uniques. La question d'origine n'a même pas de mentionner que les valeurs uniques de faire partie de la liste originale des paires clé-valeur (cette contrainte est qu'implicitement sous-entendu). Par conséquent, comme je l'ai dit, manque de spécifications...OriginalL'auteur NimChimpsky