1

现在，我正在尝试学习 Scala 。我从小处着手，编写一些简单的算法。当我想通过查找所有低于某个阈值的素数来实现 Sieve 算法时，我遇到了一些问题。

我的实现是：

import scala.math

object Sieve {

    // Returns all prime numbers until maxNum
    def getPrimes(maxNum : Int) = {
        def sieve(list: List[Int], stop : Int) : List[Int] = {
            list match {
                case Nil => Nil
                case h :: list if h <= stop => h :: sieve(list.filterNot(_ % h == 0), stop)
                case _ => list
            }
        }
        val stop : Int = math.sqrt(maxNum).toInt
        sieve((2 to maxNum).toList, stop)
    }

    def main(args: Array[String]) = {
        val ap = printf("%d ", (_:Int)); 

        // works
        getPrimes(1000).foreach(ap(_))

        // works 
        getPrimes(100000).foreach(ap(_))

        // out of memory
        getPrimes(1000000).foreach(ap(_))

    }
}

不幸的是，当我想计算所有小于 1000000 (100 万) 的素数时，它失败了。我收到 OutOfMemory 。

您对如何优化代码有任何想法，或者我如何以更优雅的方式实现此算法。

PS：我在 Haskell 中做过非常相似的事情，我没有遇到任何问题。

4

5 回答 5

4

有问题的代码不是尾递归的，因此 Scala 无法优化递归。此外，Haskell 默认情况下是非严格的，因此您几乎无法将其与 Scala 进行比较。例如，Haskell 受益于foldRight. Scala 受益于foldLeft.

Sieve of Eratosthenes 有许多 Scala 实现，包括 Stack Overflow 中的一些。例如：

(n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps))
于 2011-01-04T17:54:22.820 回答
4

我会选择无限流。使用惰性数据结构可以像在 Haskell 中一样编写代码。它自动读取比您编写的代码更具“声明性”。

import Stream._

val primes = 2 #:: sieve(3)

def sieve(n: Int) : Stream[Int] =
      if (primes.takeWhile(p => p*p <= n).exists(n % _ == 0)) sieve(n + 2)
      else n #:: sieve(n + 2)

def getPrimes(maxNum : Int) = primes.takeWhile(_ < maxNum)

显然，这不是最高效的方法。阅读The Genuine Sieve of Eratosthenes以获得一个很好的解释（它是 Haskell，但不是太难）。对于真正的大范围，您应该考虑阿特金筛。

于 2011-01-04T19:43:51.800 回答
2

以下答案比使用 Set 的“单线”答案快大约 100 倍（并且结果不需要按升序排序），并且比使用数组的其他答案更具有功能形式，尽管它使用一个可变的 BitSet 作为筛选数组：

object SoE {
  def makeSoE_Primes(top: Int): Iterator[Int] = {
    val topndx = (top - 3) / 2
    val nonprms = new scala.collection.mutable.BitSet(topndx + 1)
    def cullp(i: Int) = {
      import scala.annotation.tailrec; val p = i + i + 3
      @tailrec def cull(c: Int): Unit = if (c <= topndx) { nonprms += c; cull(c + p) }
      cull((p * p - 3) >>> 1)
    }
    (0 to (Math.sqrt(top).toInt - 3) >>> 1).filterNot { nonprms }.foreach { cullp }
    Iterator.single(2) ++ (0 to topndx).filterNot { nonprms }.map { i: Int => i + i + 3 }
  }
}

可以通过以下代码进行测试：

object Main extends App {
  import SoE._
  val top_num = 10000000
  val strt = System.nanoTime()
  val count = makeSoE_Primes(top_num).size
  val end = System.nanoTime()
  println(s"Successfully completed without errors. [total ${(end - strt) / 1000000} ms]")
  println(f"Found $count primes up to $top_num" + ".")
  println("Using one large mutable1 BitSet and functional code.")
}

上述结果如下：

Successfully completed without errors. [total 294 ms]
Found 664579 primes up to 10000000.
Using one large mutable BitSet and functional code.

即使是很小的筛选范围也会有大约 40 毫秒的开销，并且随着 BitSet 的大小超出不同的 CPU 缓存，随着范围的增加，会有各种非线性响应。

于 2014-12-07T10:06:23.540 回答
1

看起来 List 在空间方面不是很有效。您可以通过执行以下操作来获取内存不足异常

1 to 2000000 toList
于 2011-01-04T18:00:00.100 回答
1

我“作弊”并使用了一个可变数组。一点也不觉得脏。 

  def primesSmallerThan(n: Int): List[Int] = {
    val nonprimes = Array.tabulate(n + 1)(i => i == 0 || i == 1)
    val primes = new collection.mutable.ListBuffer[Int]
    for (x <- nonprimes.indices if !nonprimes(x)) {
      primes += x
      for (y <- x * x until nonprimes.length by x if (x * x) > 0) {
        nonprimes(y) = true
      }
    }
    primes.toList
  }
于 2011-01-04T22:15:02.137 回答