Scala:在修改序列时迭代它？

Question

我正在尝试实现 Sieve of 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) )。然后，通过 Sieve，我想遍历每个元素，并从 Seq 中过滤该元素的所有倍数。它看起来像这样，除了它简单地迭代每个奇数:

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

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

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

但是当然，这只是将序列复制到迭代器中，然后迭代 nums 中的每个值。因为它在 for 循环的开头(所以在这种情况下，它完全等同于前面的例子)。我希望它每次迭代都从 nums 中获取下一个值.

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

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

Answer 1

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

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

这不会改变 mi正在迭代中。那个 mi将始终保持不变。可能你可以改变 mi 的值，但改变它不起作用。顺便说一下，变异它也可能不起作用。

你是怎么做到的？你不用于理解——或者，至少，不是这样。你可以看看我自己的版本 here ，它遍历与被变异的集合不同的集合。或者这里是一个单线:

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

现在，回到你想要做的事情……当你使用 for-comprehension 时，你实际上是在调用方法 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通过所有剩余的数字来削减非质数。