performance - 在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)

接下来，在 upper中未使用 filterPrimes(尽管这对性能没有影响)。

第三，如果要真正使用纯函数样式，请不要使用 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)时，您实际上可以停止。