Quelqu'un peut-il optimiser la déclaration suivante dans SCALA:
// maybe large val someArray = Array(9, 1, 6, 2, 1, 9, 4, 5, 1, 6, 5, 0, 6) // output a sorted list which contains unique element from the array without 0 val newList=(someArray filter (_>0)).toList.distinct.sort((e1, e2) => (e1 > e2))
7 Réponses :
Sans benchmarking, je ne peux pas être sûr, mais j'imagine que ce qui suit est assez efficace:
val list = collection.SortedSet(someArray.filter(_>0) :_*).toList
+1 J'aime la concision, mais vous devez ajouter un filtre là aussi.
@LUIGIPLINGE Comment le faire dans la commande descendante?
@Tianyiliang Sortwith (_ <_)
Pour l'efficacité, en fonction de votre valeur de gros: Notez que cela utilise le tri qsort sur une matrice non incorrecte.
LISTE # Sortwith utilise cette même méthode sous les couvertures (Consulter SEQLILE source)
Je suis d'accord. Je suis assez sûr que le tri serait fait sur des références d'objet, pas les primitives comme dans ma version.
Je ne suis pas en mesure de mesurer, mais d'autres suggestions ...
Tri de la matrice en place Avant la conversion vers une liste pourrait bien être plus efficace et vous pouvez envisager de supprimer les DUP à partir de la liste triée manuellement, car ils seront regroupés. Le coût de l'élimination des 0 avant ou une fois le tri dépendra également de leur ratio aux autres entrées.
Je ne peux pas trier avant de convertir car la matrice sera utilisée pour une autre itération dans un grand programme, à moins que cela ne génère un nouveau tableau.
@Tianyiliang Dans ce cas, utilisez simplement tableau # Copier pour effectuer une copie du tableau d'abord. C'est une opération très rapide.
@LUIGIPLINGE Qu'en est-il de Array.clone? A-t-il la même performance que la copie de la matrice. Au fait, avez-vous une suggestion de problème 8173329.
@Itianyiliang je serais surpris si ça ne le faisait pas, mais je ne sais pas
L'une des choses qui m'a étonné du traitement de la vidéo est au moment où vous pouvez copier des tampons multi-mégaoctets avant que les choses ne ralentissent sensiblement.
+1 L'une des solutions les plus rapides est basée sur ces suggestions.
Que diriez-vous d'ajouter tout à un jeu de tri? Bien sûr, vous devriez Benchmark le code pour vérifier ce qui est plus rapide et, plus important encore, que C'est vraiment un point chaud.
Qu'est-ce que cela signifie: (0! =): _ * ?
@nedim in Scala, : est presque toujours le séparateur entre une valeur et un type (exceptions étant : , <: et > : sur les paramètres de type), donc filtre SOMARRAY (0! =) est une valeur, et _ * est un type. Le type _ * est utilisé pour indiquer à Scala de transmettre une séquence comme plusieurs paramètres sur une méthode avec un nombre variable d'arguments. Donc, SET (SEQ (1, 2, 3)) est un ensemble avec un élément de type SEQ [INT] et SET (SEQ (1, 2 , 3): _ *) est un ensemble avec trois éléments de type int . (0! =) est la méthode ! = appliqué sur l'objet 0 .
@ Daniel-C-Sobral Wow, je sais que Scala aime se vanter que c'est concis, mais cet extrait est vraiment quelque chose! Je comprends comment _? fonctionne maintenant (quel est le nom de ce type / construction?). Il semble similaire à ce que j'ai vu en python avec le paramètre (ONU) emballage, seulement qu'il est effectué par un type de coulée. Cool, j'ai raté ça de Python. Cependant, il me puzzle toujours comment (0! =) fonctionne sans le soulignement, c'est-à-dire
@nedim ça marche à peu près comme dans Java 8. Si vous écrivez x :: m sur java 8, vous vous référez à la méthode x sur l'objet m . Dans Scala, car il n'a pas de méthodes statiques pour tout désordre, vous utilisez uniquement . . Si j'écris quelquevar.equals , je parle de la méthode égale sur quelqueevar . C'est à peu près la même chose, sauf 0 est un littéral au lieu d'une variable, et ! = est un nom de méthode symbolique.
Je n'ai pas mesuré, mais je suis avec Duncan, trier en place, puis utilisez quelque chose comme: en théorie, cela devrait être assez efficace.
Merci, jed. Il semble que la meilleure version utilise Scala Style.
Les primitives de boxe vont vous donner une pénalité de 10 à 30 fois de performance. Par conséquent, si vous vraiment em> sont des performances limitées, vous allez vouloir travailler des tableaux primitifs bruts: def listDistinctInts(someArray: Array[Int]): List[Int] = {
if (someArray.length == 0 || someArray(someArray.length-1) <= 0) List[Int]()
else {
java.util.Arrays.sort(someArray)
var last = someArray(someArray.length-1)
var list = last :: Nil
var i = someArray.length-2
while (i >= 0) {
if (someArray(i) < last) {
last = someArray(i)
if (last <= 0) return list;
list = last :: list
}
i -= 1
}
list
}
}
Arrayindexoob en seconde fois: résultat (j) = sométray (i)
Je suppose que j'ai trouvé 2 erreurs: si (somerray (i) <= 0) plus dezero = i doit mettre fin à `+ = 1` au 1er, tandis que dans le second pendant un Dernier = SOMARRAY (I) est manquant. Dans ma référence personnelle contre la solution de JED avec jusqu'à 6 millions d'éléments, vous gagnez dans 9 cas, mais utilisez plus de mémoire, mais de participer à ma compétition, je devais transformer le résultat avec TOLIST à la liste à la fin. L'utilisation d'une liste depuis le début vous permet d'ici beaucoup (5% contre 10 secondes pour 8 m d'éléments dans le tableau).
@userunknown - merci! C'est pourquoi je ne devrais jamais essayer de taper plus de deux lignes de code sans le réplique pratique.
Mais vous savez SimplyScala et Ideone! :)
@userunknown - assez vrai. J'écris habituellement des choses en utilisant mes bibliothèques personnelles, puis les éliminer pour des exemples, mais pas dans ce cas, cela aurait donc fonctionné.
Cette ligne simple est l'un des codes les plus rapides jusqu'à présent: mais le gagnant clair jusqu'à présent - en raison de ma mesure - JED WESLEY-SMITH. Peut-être que si le code REX est corrigé, il a l'air différent. Disclaimer typique 1 + 2: Voici le sous-jacent Code de pare-balles et le code de béton pour produire le graphique ( gnuplot). Axe Y: Temps en secondes. Axe X: 100 000 à 1 000 000 éléments de matrice. Après avoir trouvé le problème avec le code REX, son code est aussi rapide que le code de JED, mais le La dernière opération est une transformation de son tableau vers une liste (pour remplir mon interface de référence). Utilisation d'un Un autre, peut-être intéressant, trouver est: Si je réorganise mon code dans l'ordre du filtre / tri / distinct (FSD) => (DSF, DFS, FSD, ...), toutes les 6 possibilités DON 't diffère de manière significative. 
Mise à jour:
var résultat = Liste [int] et résultat = SOMARRAY (i) :: résultat accélère son code, de sorte qu'il soit environ deux fois plus vite que le JED -Code.
+1 - Les repères sont formidables lorsque vous répondez aux questions de performance!
Merci pour votre travail. Cela explique tout. Suggère-t-il que Scala est plus disposé à gérer le style de programmation fonctionnel?
Si vous voulez voir une différence, vous devez avoir un nombre important de valeurs négatives ou zéro. S'ils sont, disons, la moitié des nombres totaux, puis filtrant ou distinct d'abord sera une victoire sur le tri. (Je pense que le filtre-d'abord sera le meilleur, mais je ne rappelle pas précisément la mise en œuvre de distincte, donc je ne suis pas positive.)
@Rexkerr: Tu as raison. Si ma fonction de génération crée n valorisez Room.Nextint (N / 10), mais avec environ 15% d'entre eux étant 0, les performances des UFS (Tri-filtre unique) et USF sont beaucoup mieux que suf / sfu. Oh, j'ai beaucoup trop de diagrammes maintenant, je ne peux pas schoser tous ici! :)