在Scala中，为什么我的Sieve算法运行得这么慢？

Question

我正在尝试使用列表和过滤器而不是数组和循环来实现Eratosthenes的筛子。我不确定为什么下面的代码比命令式代码的性能差得多。一百万绝对可以飞，但我的机器却停了下来。

  val max = 1000000
  def filterPrimes(upper: Int, seed: Int = 2, sieve: List[Int] = List()): List[Int] =
    sieve.map(x => if (x % seed == 0 && x > seed) 0 else x).filter(_ > 0)

  var filtered: List[Int] = (2 to max).toList
  for (i <- 2 to max / 2) filtered = filterPrimes(max, i, filtered)
  filtered.foreach(println(_))

Answer 1

有一些潜在的问题，尽管我并没有真正看到一个“确凿的证据”……不管怎样，这就是我得到的。首先：

sieve.map(x => if (x % seed == 0 && x > seed) 0 else x).filter(_ > 0)

可以更简洁地写成：

sieve.filter(x => x <= seed || x % seed != 0)

接下来，filterPrimes中没有使用upper (不过这应该不会对性能产生影响)。

第三，如果您想真正使用纯函数风格，请不要使用var和for循环，而是将filterPrimes转换为尾递归函数。如果你这样做，编译器可能足够聪明，可以优化掉副本(尽管我不会屏住呼吸)。

最后，可能也是最重要的一点是，您的for循环正在浪费大量的时间来过滤掉必须已经过滤的值。例如，在过滤了所有2的倍数之后，它会尝试过滤4的倍数。如果你想有效地使用这个筛子算法，你需要从列表中剩余的元素中选择你的种子。

换句话说，在列表中保留一个索引，并从索引中确定种子，如下所示：

iteration 0: 2 3 4 5 6 7 8 9 ...
      index: ^

iteration 1: 2 3 5 7 9 ...
      index:   ^

iteration 2: 2 3 5 7 ...
      index:     ^

这避免了重复的工作。而且，你不需要一直迭代，直到你到达max，我认为当你通过sqrt(max)时，你实际上可以停止。

Answer 2

如果你想看到一种函数式的筛分方式，请查看The Genuine Sieve of Eratosthenes。

Answer 3

这是一个快速筛子，实现了mergeconflict的提示和Ken Wayne VanderL提到的论文中的一些提示：

def createPrimes (MAX: Int) : Array[Boolean] = {
  val pri = (false :: false :: true :: List.range (3, MAX + 1).map (_ % 2 != 0)).toArray
  for (i <- List.range (3, MAX)
    if (pri (i))) {
      var j = 2 * i;
      while (j < MAX) {
        if (pri (j))
          pri (j) = false;
        j += i;
      }
    }
  pri
}
val MAX = 1000*1000
(1 to MAX).filter (createPrimes (MAX))

比较图：

纵轴表示秒，水平轴表示从100000到1000000个素数。Delta11月份算法已经得到了改进，只运行到math.sqrt(最大)，以及Alexey Romanov在评论中建议的过滤。我采用了Dan Burton的第二个算法和最后一个算法，做了一些小的修改，以适应我的接口(列表，而不是数组)和bitSet筛子，他只在评论中链接到它，但哪个是最快的。