J'ai une liste non traitée et je veux savoir si tous les articles de ce système sont uniques. essentiellement, je vérifie si un ensemble contenant tous les éléments de la liste a la même taille (puisqu'un élément apparaissant deux fois dans la liste d'origine n'apparaîtra qu'une fois dans L'ensemble), mais je ne suis pas sûr de savoir si c'est la solution idéale pour ce problème. P> EDIT: B>
J'ai comparé les 3 solutions les plus populaires, Les résultats: p> Les résultats avec des objets plus grands (cordes de 1kb à 5 ko): P>
Mon approche naïve serait l == l.distinct code>, l.size == l.distinct.Size code> et solution basée sur hashset d'Alexey.
Chaque fonction a été exécutée 1000 fois avec une liste unique de 10 éléments, une liste unique d'articles 10000 et des mêmes listes avec un élément figurant au troisième trimestre copié au milieu de la liste. Avant chaque exécution, chaque fonction a été appelée 1000 fois pour réchauffer le JIT, l'ensemble de la référence a été exécuté 5 fois avant que les temps ne soient pris avec System.Currenttimemillis.
La machine était une RAM C2D P8400 (2,26 GHz) avec 3 Go de RAM, la version Java était le serveur VM OpenJDK 64bit (1.6.0.20). Les java args étaient -xmx1536m -xms512m p> l.size==l.distinct.size MutableList(4, 5566, 7, 6506)
l==l.distinct MutableList(4, 5926, 3, 6075)
Alexey's HashSet MutableList(2, 2341, 3, 784)
3 Réponses :
Je voudrais simplement utiliser distinct code> méthode:
ajouter strong>: standard implémentation distincte code> (de scala.collection.seqlike code>) utilise un hashset mutable, pour trouver des éléments en double: p> def distinct: Repr = {
val b = newBuilder
val seen = mutable.HashSet[A]()
for (x <- this) {
if (!seen(x)) {
b += x
seen += x
}
}
b.result
}
+1 pour distinct, mais ne serait pas l.distinct.size == l.Size BE O (1) au lieu de O (n) pour la comparaison?
Non, puisque list.size est lui-même O (n). Voir Lampsvn.epfl.ch/trac/scala/browser/scala/tags/r_2_8_0_final/ src / ... Pour vérifier que la taille doit être calculée en itérant sur la liste.
Vous avez raison, mais liste.Size peut être mis en œuvre comme O (1) alors qu'il n'est pas impraticable à la comparaison.
Voici la solution purement fonctionnelle la plus rapide que je puisse penser:
def isUniqueList(l: List[T]) = l.toSet.size == l.size
Vous pouvez modifier le si (S.Contains (h)) FAUX else ISuniquelist1 (t, S + H) TO: ! (S (H) ||! Isuniquelist (T, S + h))
Mais alors ce n'est plus récursif de la queue ... j'appliquerais au moins les règles de Morgan et la transformerait en ! S (h) && isuniqueliste (t, s + h) , qui est.
Il n'y a rien de mal à utiliser une structure de données immuable dans le deuxième exemple car la fonction dans son ensemble est toujours transparente de manière transparente.
Une méthode plus efficace serait d'essayer de trouver une dupe; Cela reviendrait plus rapidement si on a été trouvé:
Voulez-vous une solution la plus performante ou la plus simple?
Idéalement, mais si la solution la plus simple est significativement (3-4X) plus lente, j'aurais besoin du plus performant.
Cela dépend fortement de la liste. Par exemple. Si deux éléments au début d'une liste assez longue sont les mêmes, ma solution sera bien supérieure à 3 à 4 fois plus rapide.
Que signifient les numéros? Peux-tu élaborer?
@ JUS12: 10 articles uniques, 10000 articles uniques, une liste non unique (1234767890) avec 10 articles et un avec 10000 articles.
Je voulais dire cela signifie-t-il du temps en millisecondes, ou du temps moyen de toutes les manches, etc.?
Si je me souviens bien, ce sont les temps combinés pour 1000 courses en millisecondes, mais cela devrait être hors de propos.