Scala：在修改序列时迭代序列？

发布时间：2020-12-16 18:10:35 所属栏目：安全来源：网络整理

导读：我正在尝试在 Scala中实现 Sieve of Eratosthenes. 我首先初始化所有奇数加2的序列： // (end goal is to find all prime factors of bigNumber)val largestPrime : Long = Math.ceil(Math.sqrt(bigNumber)).toLongvar nums : Seq[Long] = (3L to largestPri

我正在尝试在 Scala中实现 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函数,我正在尝试掌握如何使用它,因为我怀疑它可能在这种情况下使用…

解决方法

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

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移动到每个已知素数,并移动扫描器通过所有剩余数字以剪切非素数.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!