Scala性能-筛子 [英] Scala performance - Sieve

问题描述

现在，我正在尝试学习Scala.我从小开始，写了一些简单的算法.当我想通过发现所有低于特定阈值的所有质数来实现Sieve算法时，遇到了一些问题.

Right now, I am trying to learn Scala . I've started small, writing some simple algorithms . I've encountered some problems when I wanted to implement the Sieve algorithm from finding all all prime numbers lower than a certain threshold .

我的实现是:

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.

Unfortunately it fails when I want to computer all the prime numbers smaller than 1000000 (1 million) . I am receiving OutOfMemory .

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

Do you have any idea on how to optimize the code, or how can I implement this algorithm in a more elegant fashion .

PS:我在Haskell中做了非常相似的事情，在那里我没有遇到任何问题.

PS: I've done something very similar in Haskell, and there I didn't encountered any issues .

推荐答案

我将使用无限流.使用惰性数据结构可以像在Haskell中一样进行编码.它会自动读取比您编写的代码更声明性"的代码.

I would go with an infinite Stream. Using a lazy data structure allows to code pretty much like in Haskell. It reads automatically more "declarative" than the code you wrote.

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)

显然，这不是最有效的方法.阅读真正的Eratosthenes筛子(它是Haskell，但不太困难).对于真正的大范围，您应该考虑阿特金筛子.

Obviously, this isn't the most performant approach. Read The Genuine Sieve of Eratosthenes for a good explanation (it's Haskell, but not too difficult). For real big ranges you should consider the Sieve of Atkin.

这篇关于Scala性能-筛子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！