Scala: itérer une séquence tout en modifiant?

Question

Je suis en train de mettre en œuvre le Eratosthène de Sieve à Scala.

Je commence par l'initialisation d'une séquence de tous les nombres impairs plus 2:

// (end goal is to find all prime factors of bigNumber)
val largestPrime : Long = Math.ceil(Math.sqrt(bigNumber)).toLong
var nums : Seq[Long] = (3L to largestPrime by 2L).toSeq
nums +: 2L

nums contient Seq (2,3,5,7,9,11,13,15, ..., (largestPrime)). Puis, par la Sieve, je veux itérer sur chaque élément, et filtrer tous les multiples de cet élément de la Seq. Il ressemblerait à quelque chose comme ça, sauf que cette itère simplement sur chaque nombre impair:

for(i : Long <- 3L to largestPrime by 2L) {
    nums = nums.filter((j : Long) => j == i || j % i != 0)
}

Ainsi, au lieu, je voudrais utiliser quelque chose comme ceci:

for(i <- nums) {
    // filter
}

Mais bien sûr, ce simplement une copie de la séquence dans un itérateur et itère ensuite sur chaque valeur nums telle qu'elle était au début de la boucle (dans ce cas, il est exactement équivalent à l'exemple précédent). Je veux que ce, chaque itération, prenez la prochaine valeur de nums.

Comment est la meilleure façon de mettre en œuvre ce? Dois-je utiliser une variable d'index et une boucle while? Je ne sais pas comment obtenir un élément d'une séquence (à savoir comment obtenir x élément de la séquence, où x est l'indice). Ou est-il un moyen de faire plus fonctionnel cela?

---

Edit: Je viens de trouver la fonction scanLeft, je suis en train de saisir comment l'utiliser comme je le soupçonne qu'il pourrait être utile dans ce cas ...

Answer 1

Commençons avec ce que je considère être le plus gros problème ci-dessus. Vous avez ceci:

for (i <- mi) { mi = something else }

ne changera pas la mi qui est itéré. Ce mi restera le même tout au long. Il est peut-être que vous pouvez muter la valeur de mi, mais en changeant cela ne fonctionnera pas. Muter il peut ne pas non plus, par la manière.

Alors, comment voulez-vous le faire? Ne pas utiliser pour compréhensions - ou, au moins, pas de cette façon. Vous pouvez regarder ma propre version , qui le compare à une collection différente de celle d'être muté. Ou voici un one-liner:

(n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps))

Maintenant, revenons à ce que vous voulez à faire ... lorsque vous utilisez un pour-compréhension, vous appellent en fait la méthode foreach, map ou flatMap là-dessus, de sorte que vous auriez besoin d'un collection qui est capable de traiter une de ces méthodes et ne pas avoir des problèmes avec l'élément « suivant » passer d'une itération à l'autre. Comme je l'ai dit, je ne suis pas sûr de toute la collection Scala l'affaire. Vous seriez mieux d'utiliser une boucle de while et de garder une trace de choses vous-même si vous allez de cette façon. Par exemple:

def primes(n: Int) = {
    import scala.collection.mutable.LinkedList
    val primes = LinkedList(3 to n by 2: _*)
    var p = primes
    while (p.nonEmpty) {
        var scanner = p
        while (scanner.next.nonEmpty) {
            if (scanner.next.head % p.head == 0)
                scanner.next = scanner.next.next
            else
                scanner = scanner.next
        }
        p = p.next
    }
    primes
}

Notez que je garde un pointeur vers le début de la LinkedList, p de déplacement à travers chaque premier connu, et scanner de déplacement à travers tous les numéros restants pour couper les non-nombres premiers.

Answer 2

L'exemple dans la documentation sur scala.collection. immutable.Stream est d'un tamis:

object Main extends Application {

  def from(n: Int): Stream[Int] =
    Stream.cons(n, from(n + 1))

  def sieve(s: Stream[Int]): Stream[Int] =
    Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))

  def primes = sieve(from(2))

  primes take 10 print
}

Answer 3

Ni une bonne solution fonctionnelle, ni une solution qui révèle des trésors obscurs Bibliothèque Scala, mais il est plutôt facile construire vous-même iterator spécialisé.

class ModifyingIterator(var collection: Seq[Long]) extends Iterator[Long] {
  var current = collection.head
  def next = {
    current = collection.find(_ > current).get
    current
  }
  def hasNext = collection.exists(_ > current)
}

val mi = new ModifyingIterator(nums)

for (i <- mi) {
    mi.collection = mi.collection.filter((j : Long) => j == i || j % i != 0)
}
println(mi.collection)

ModifyingIterator conserve la trace de l'élément en cours et permet de réattribuer la collection qui est utilisé pour itérer. Le point suivant est toujours plus grand que l'élément en cours.

Bien sûr, on devrait employer probablement une meilleure structure de données qui ne garde pas trace du courant valeur mais gardez un pointeur vers le courant élément afin de se débarrasser de la recherche inutile chaque fois.

Answer 4

Il y a un article intéressant: http: //www.cs .hmc.edu / ~ Oneill / papiers / Sieve-JFP.pdf

J'ai essayé de traduire le code Haskell donné dans ce document à Scala, mais je ne l'ai pas testé les performances.

object primes {

    type SI = Stream[Int]

    def sieve:SI = {
        def wheel2357:SI = Stream(4,2,4,6,2,6,4,2,4,6,6,
            2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,
            6,4,2,4,6,2,6,4,2,4,2,10,2,10,2) append wheel2357
        def spin(s:SI, n:Int):SI = Stream.cons(n, spin(s.tail, n + s.head))

        case class It(value:Int, step:Int) {
            def next = new It(value + step, step)

            def atLeast(c:Int):It =
            if (value >= c) this
            else new It(value + step, step).atLeast(c)
        }

        implicit object ItOrdering extends Ordering[It] {
            def compare(thiz:It, that:It) = {
                val r = thiz.value - that.value
                if (r == 0) thiz.step - that.step else r
            }

        }

        import scala.collection.immutable.TreeSet

        def sieve(cand:SI, set:Set[It]):SI = {
            val c = cand.head
            val set1 = TreeSet[It]() ++ set.dropWhile(_.value < c) ++
               set.takeWhile(_.value < c).map(_.atLeast(c))
            if (set1.elements.next.value == c) {
                val set2 = TreeSet[It]() ++ set1.dropWhile(_.value == c) ++
                    set1.takeWhile(_.value == c).map(_.next)
                sieve(cand.tail, set2)
            } else {
                Stream.cons(c, sieve(cand.tail, set1 + It(c*c,2*c)))
            }
        }
        Stream(2,3,5,7,11) append sieve(spin(wheel2357,13),
                  new TreeSet[It] + It(121,22))
    }

    def main(args:Array[String]) {
        sieve.takeWhile(_ < 1000).foreach(println)
    }
}