J'essaie de mettre en œuvre le tamis des eratosthènes à l'aide de listes et de filtres plutôt que des tableaux et des boucles. Je ne sais pas pourquoi ce qui suit est considérablement pire qu'un équivalent impératif. 1 million devraient absolument voler mais ma machine serra à une halte.
val max = 1000000
def filterPrimes(upper: Int, seed: Int = 2, sieve: List[Int] = List()): List[Int] =
sieve.map(x => if (x % seed == 0 && x > seed) 0 else x).filter(_ > 0)
var filtered: List[Int] = (2 to max).toList
for (i <- 2 to max / 2) filtered = filterPrimes(max, i, filtered)
filtered.foreach(println(_))
5 Réponses :
Les listes sont immuables et chaque appel à Allez avec votre premier instinct (ce que vous appelez probablement "l'équivalent impératif") que je devine utilise un tableau (édité pour préciser que j'ai compris que la création de plusieurs listes était inutile.) FilterPrime crée une nouvelle liste. Vous créez beaucoup de listes, ce qui est, à la manière, inutile.
Si vous souhaitez voir un moyen fonctionnel de faire le tamis, consultez Le tamis authentique des eratosthènes .
+1 C'est une grande lecture et débunde le "tamis de golf" si souvent lancé.
Il y a quelques problèmes potentiels, bien que je ne voie pas vraiment un seul "pistolet à fumer" ... Quoi qu'il en soit, voici ce que j'ai. Premièrement:
iteration 0: 2 3 4 5 6 7 8 9 ...
index: ^
iteration 1: 2 3 5 7 9 ...
index: ^
iteration 2: 2 3 5 7 ...
index: ^
Je pense qu'il est prudent de dire que pour (i <- 2 à max / 2) est le "pistolet à fumer", pour deux raisons que vous avez décrites: "Il essaie de filtrer des multiples de 4 après avoir déjà eu filtré tous les multiples de 2 [etc] "" et "Je pense que vous pouvez réellement arrêter quand vous obtenez le SQRT (max)"
Bien sûr, mais je suppose que @deltanovember fait la même chose dans sa version impérative qu'il comparait la performance contre. Je ne sais pas, peut-être que c'est une mauvaise hypothèse :)
Je ferais quelques modifications.
filtres code> pour tous les numéros em> entre 2 code> et max / 2 code>, le " Technique de tamis réelle nécessite que vous effectuez uniquement filtreprimimes code> pour tous les primes em> entre 2 code> et sqrt (max) code>. li>
- Il semble également étrange que vous utilisiez un var et une boucle. Pour le faire la manière «fonctionnelle», j'utiliserais une fonction récursive à la place. LI>
- au lieu d'exécuter
filtrePRimes code> sur la liste complète, vous pouvez collecter les primes au fur et à mesure. Pas besoin de jeter ceux à travers le filtre encore et encore. Li>
- Il est plutôt étrange de
cartographique code>, puis Filtre code> comme vous le faites, car la carte marque simplement des drapeaux quels éléments à filtrer, vous pouvez accomplir la même chose en utilisant uniquement le filtre. li>
ul> Voici ma première tentative de ces modifications: p> xxx pré> Cependant, cela reflète mon biais de haskell et a une énorme défaute: elle prendra une énorme défaute: Une énorme quantité d'espace de pile, en raison de l'appel récursif y :: Go (...) code> dans la fonction Go code> Fonction. En cours d'exécution tamis (1000000) code> a abouti à un "OutofMemoryError" pour moi. P> Essayons une astuce FP commune: récursion de la queue avec des accumulateurs. P>
def mutationSieve (max: Int) = {
var arr: Array[Option[Int]] =
(2 to max).map (x => Some (x)).toArray
var i = 0
var seed = (arr (i)).get
while (seed * seed < max) {
for (j: Int <- (i + seed) to (max - 2) by seed) {
arr (j) = None
}
i += 1
while (arr (i).isEmpty) {
i += 1
}
seed = (arr (i)).get
}
arr.flatten
}
+1 Benchmarking pour l'OP et une analyse agréable. Maintenant C'est une réponse utile.
Je parie que vous pouvez faire votre version impérative beaucoup plus rapide en utilisant soit une matrice primitive, soit un bitset.
Je suppose que aller (2 :: (3 à max par 2) .tolist, nil) améliorerait la vitesse un peu pour 2 des solutions.
@userunknown Ajouté FromeSome Droit avant Mutationieve . En outre, l'utilisation de la technique «roue» (décrite dans le papier académique Ken liée à) améliorerait encore plus la vitesse. Si j'étais plus un scala buff, j'aurais essayé d'utiliser des ruisseaux et des roues.
@ziggystar à l'aide d'un bitset, j'ai pu obtenir environ une vitesse de 3x. version Bitset sur ideone.com , version de tableau d'option sur ideone.com . Je ne peux pas imaginer une version impérative de cette même technique étant plus rapide qu'un bitset, en supposant que les bits d'affaires mutables de Scala soient bien implémentés.
@Dan Burton Bien Factor Theck Three n'est pas si mauvais, n'est-ce pas?
@ziggystar Un speed-up 3x est définitivement une bonne chose; Cela place le code de liste à ~ 18x plus lent que le code Bitset. J'ai été agréablement surpris à la fois à la vitesse et à la clarté du code Bitset; Je m'attendais à ce qu'elle soit beaucoup plus méchante. Merci pour la pointe d'utiliser Bitset :) Je n'en avais pas entendu parler avant.
@Danburton: Je me suis permis de modifier un peu votre code, après avoir compris de omeome :) a) au lieu de goûter, vous appelez obtenez pour une option qui est une option pour Bien sur. Et b) arr.map (! _.Impty) .Fromsome est devenu juste arr.flatten .
Ceci est un tamis rapide, mettant en œuvre des notes de mergeconflict et certaines des notes du papier, mentionnée par Ken Wayne Vanderl: comparer le graphique:
L'axe vertical montre des secondes, l'horizontale est de 100 000 à 1 000 000 nombres premiers.
L'algorithme Deltanovember est déjà amélioré pour fonctionner à Math.SQRT (max) uniquement et le filtrage, suggéré par Alexey Romanov dans le commentaire. De Dan Burton, j'ai pris le deuxième algorithme et le dernier avec une petite modification, adapté à mon interface (liste, pas de tableau) et au tamis Bitset, qu'il ne lié que dans un commentaire, mais lequel est le plus rapide.
Graphique fantaisie :) très cool. Important de noter comment deltanovember augmente plus rapidement que les autres, car, si je ne me trompe pas sa boucle principale est effectuée o (n) fois où la "boucle principale" où la "boucle principale" des autres est effectué O (n / journal (n)) fois. journal (n) est une petite différence, mais une différence néanmoins. fratome était juste un petit hack pour extraire le A d'une option (A] , destiné à être utilisé uniquement lorsque vous êtes déjà sûr que est certains (x) et non aucun . J'ai ajouté le code à ma réponse ci-dessus.
Merci, j'ai fait le graphique avec Gnuplot et mon propre cadre de microbenchmark, disponible ici: gist.github.com/1152783 < / a>, qui crée l'entrée de gnuplot. Pour des échantillons plus gros (5 m), j'ai répété le test sans approche de Deltanoveubers et obtenu un résultat similaire - votre mutation reçue. Je n'ai pas lu le papier avec la roue - peut-être que je devrais, mais cela semble difficile à comprendre.
Je remplacerais
sieve.map (x => si (x% graine == 0 && x> graine) 0 autre x) .Filter (_> 0) avecsieve.filter ( x => x% graine! = 0 || x == graines) .Même Dan Burton et l'utilisateur Inconnu n'ont pas souligné que votre code ici n'est pas un tamis d'Eratosthènes (SOE), mais plutôt une division d'essai principale Timeve (TDPS), car elle ne suit pas l'algorithme d'ératosthènes de l'utilisation des ajouts à la celles Les composites premiers comme dans leurs solutions les plus impératives les plus impératives (elles utilisent mutabilité de l'index Var dans les boucles d'abattage interne; on pourrait réécrire leur code pour utiliser des formes de boucle fonctionnelles ne nécessitant aucune mutabilité, à l'exception de la matrie ou du contenu des bitset à peu ou pas de coût à la vitesse. ). Il s'agit de TDPS parce que vérifie les facteurs de chaque numéro d'essai par la division.