4

我正在尝试在 Scala中实现Eratosthenes 筛。

我首先初始化所有奇数加 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包含 Seq( 2,3,5,7,9,11,13,15,...,(largestPrime) )。然后，通过筛子，我想遍历每个元素，并从 Seq 中过滤该元素的所有倍数。它看起来像这样，除了这只是迭代每个奇数：

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

所以相反，我想使用这样的东西：

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

但是，当然，这只是将序列复制到一个迭代器中，然后像 for 循环开始时那样迭代每个值nums（因此在这种情况下，它与前面的示例完全相同）。我希望它每次迭代都能从nums.

实现这一点的最佳方法是什么？我应该使用索引变量和while循环吗？我不确定如何从序列中获取元素（即如何获取序列的元素 x，其中 x 是索引）。或者有没有更实用的方法来做到这一点？

编辑：我刚刚找到了这个scanLeft功能，我正在尝试掌握如何使用它，因为我怀疑它可能在这种情况下有用......

4

4 回答 4

4

让我们从我认为上面最大的问题开始。你有这个：

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

这不会改变mi正在迭代的内容。这mi将始终保持不变。可能是你可以改变的值mi，但改变它是行不通的。顺便说一句，突变它也可能不起作用。

你是怎么做到的？你不使用理解 - 或者，至少不是这样。您可以在此处查看我自己的版本，它迭代的集合与被变异的集合不同。或者这里是一个单行：

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

现在，回到你想要做的事情......当你使用理解时，你实际上是在调用方法foreach，map或者flatMap在它上面，所以你需要一个能够处理这些方法之一并且没有“下一个”元素从一个迭代变为下一个迭代的麻烦。正如我所说，我不确定 Scala 的任何系列是否符合要求。如果你这样做，你最好使用while循环并自己跟踪事情。例如：

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
}

请注意，我保留了一个指向 开头的指针LinkedList，p遍历每个已知的素数，并scanner遍历所有剩余的数字以切割非素数。

于 2010-12-24T01:35:02.097 回答
2

scala.collection.immutable.Stream文档中的示例是一个筛子：

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
}
于 2010-12-23T23:30:26.513 回答
0

有一篇有趣的论文：http ://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

我试图将那篇论文中给出的 Haskell 代码翻译成 Scala，但我没有测试性能。

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)
    }
}
于 2010-12-24T11:03:47.120 回答
0

既不是一个好的功能解决方案，也不是一个揭示晦涩难懂的 Scala 库宝藏的解决方案，但自己构建一个专门的迭代器相当容易。

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跟踪当前项目并允许重新分配用于迭代的集合。下一项总是大于当前项。

当然，人们可能应该使用一种更好的数据结构，它不跟踪当前值，而是保留指向当前项目的指针，以便每次都摆脱无用的搜索。

于 2010-12-23T23:14:26.973 回答