Scala: eine Sequenz durchlaufen, während es zu ändern?

Question

Ich versuche, das Sieb des Eratosthenes in Scala zu implementieren.

Ich beginne mit einer Folge von allen ungeraden Zahlen Initialisierung 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

Jetzt nums enthält Seq (2,3,5,7,9,11,13,15, ..., (largestPrime)). Dann wird durch die Sieve, möchte ich jedes Element iterieren und filtern alle Vielfachen dieses Elements aus der Seq. Es wäre in etwa so aussehen, es sei denn dies einfach über jede ungerade Zahl iteriert:

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

Also statt, ich möchte etwas wie folgt verwenden:

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

Aber natürlich ist dies einfach kopiert die Sequenz in einen Iterator und dann jeden Wert in nums iteriert, wie es zu Beginn der for-Schleife war (so in diesem Fall ist es genau das entspricht das vorherige Beispiel). Ich will es, jede Iteration den nächsten Wert von nums greifen.

Wie ist der beste Weg, dies zu implementieren? Soll ich eine Indexvariable und eine while-Schleife verwenden? Ich bin mir nicht sicher, wie ein Element aus einer Sequenz zu erhalten (das heißt, wie Element x der Sequenz zu erhalten, wobei x der Index). Oder gibt es eine weitere funktionelle Art und Weise, dies zu tun?

---

Edit: Ich habe gerade die scanLeft Funktion, ich versuche zu verstehen, wie es zu benutzen, wie ich es vermute, der Einsatz in diesem Fall sein könnte ...

Answer 1

Lassen Sie uns beginnen mit dem, was ich halten über das größte Problem zu sein. Sie haben dies:

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

Das wird sich nicht ändern die mi die iteriert wird. Die mi wird überall gleich bleiben. Es könnte sein, dass Sie mutiert der Wert von mi, aber es ändert nicht funktionieren. Mutieren es kann nicht funktionieren, nebenbei gesagt.

So, wie Sie es tun? Sie müssen nicht für Comprehensions verwenden - oder zumindest nicht auf diese Weise. Sie können auf meine eigene Version sehen rel="nofollow">, die durch eine andere Sammlung iteriert als derjenige mutiert. Oder hier ist ein Einzeiler:

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

Nun, zurück zu dem, was Sie wollen zu tun ... wenn Sie ein für Verständnis verwenden, werden Sie tatsächlich die Methode foreach, map oder flatMap und forderte sie auf, so dass Sie ein bräuchten Sammlung, die der Umgang mit einer dieser Methoden fähig ist und keine Probleme mit dem „nächsten“ Element von einer Iteration zur nächsten Veränderung haben. Wie gesagt, ich bin nicht sicher, ob alle Scala Sammlung passen die Rechnung. Sie wären besser dran, eine while-Schleife und die Dinge selbst zu verfolgen, wenn Sie diesen Weg gehen. Zum Beispiel:

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
}

Beachten Sie, dass ich einen Zeiger auf den Anfang des LinkedList halten, bewegt p durch jede bekannte Primzahl, und bewegt scanner durch die restlichen Zahlen, die die Nicht-Primzahlen zu schneiden.

Answer 2

Das Beispiel in der Dokumentation auf scala.collection. immutable.Stream ist ein Siebes:

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

Weder eine gute funktionelle Lösung noch eine Lösung, die obskure Scala Bibliothek Schätze enthüllt, aber es ist ziemlich einfach, den Aufbau eines spezialisierte Iterator selbst.

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 verfolgt die aktuelle Position und ermöglicht die Sammlung für die Neuzuweisung, die für das Iterieren verwendet wird. Der nächste Punkt ist immer größer als das aktuelle Element.

Natürlich sollte man wohl eine bessere Datenstruktur verwenden, die nicht den Überblick über die aktuell halten sind Wert , sondern hält einen Zeiger auf den aktuellen Artikel , um loszuwerden die nutzlosen Suche jedes Mal.

Answer 4

Es gibt ein interessantes Papier: http: //www.cs .hmc.edu / ~ oneill / papers / Sieve-JFP.pdf

Ich habe versucht, die Haskell Code in diesem Papier zu Scala gegeben zu übersetzen, aber ich habe die Leistung nicht testen.

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)
    }
}