2

我试图使用 scala 2.8 解决 Project Euler 问题 7

我实施的第一个解决方案大约需要 8 秒

def problem_7:Int = {
    var num = 17;
    var primes = new ArrayBuffer[Int]();
    primes += 2
    primes += 3
    primes += 5
    primes += 7
    primes += 11
    primes += 13

    while (primes.size < 10001){

        if (isPrime(num, primes)) primes += num
        if (isPrime(num+2, primes)) primes += num+2

        num += 6
    }
    return primes.last;
}

def isPrime(num:Int, primes:ArrayBuffer[Int]):Boolean = {
    // if n == 2 return false;
    // if n == 3 return false;
    var r = Math.sqrt(num)  
    for (i <- primes){
        if(i <= r ){
            if (num % i == 0) return false;
        }
    }
    return true;
}

后来我尝试了同样的问题，但没有在数组缓冲区中存储素数。这需要 0.118 秒。

def problem_7_alt:Int = {
    var limit = 10001;
    var count = 6;
    var num:Int = 17;

    while(count < limit){

        if (isPrime2(num)) count += 1;
        if (isPrime2(num+2)) count += 1;

        num += 6;
    }
    return num;
}

def isPrime2(n:Int):Boolean = {
    // if n == 2 return false;
    // if n == 3 return false;

    var r = Math.sqrt(n)
    var f = 5;
    while (f <= r){
        if (n % f == 0) {
            return false;
        } else if (n % (f+2) == 0) {
            return false;
        }
            f += 6;
    }
    return true;
}

我尝试在 Scala 中使用各种可变数组/列表实现，但无法使解决方案更快。我不认为将 Int 存储在大小为 10001 的数组中会使程序变慢。有没有更好的方法在 scala 中使用列表/数组？

4

4 回答 4

5

这里的问题ArrayBuffer是参数化的，所以它真正存储的是对Object. 任何对 anInt的引用都会根据需要自动装箱和拆箱，这使得它非常慢。Scala 2.7 非常慢，它使用 Java 原语来执行此操作，而且执行速度非常慢。Scala 2.8 采用了另一种方法，使其更快。但是任何装箱/拆箱都会减慢您的速度。此外，您首先ArrayBuffer在堆中查找，然后再次查找java.lang.Integer包含Int-- 两个内存访问，这使得它比您的其他解决方案慢得多。

当 Scala 集合变得专业化时，它应该会快很多。是否足以击败您的第二个版本，我不知道。

现在，你可以做的就是使用它来解决这个问题Array。因为 JavaArray没有被删除，所以您可以避免装箱/拆箱。

此外，当您使用 for-comprehensions 时，您的代码有效地存储在为每个元素调用的方法中。因此，您还进行了许多方法调用，这是速度较慢的另一个原因。唉，有人为 Scala 编写了一个插件，它优化了至少一种用于理解的情况以避免这种情况。

于 2010-03-12T00:21:44.947 回答
2

使用 Array 应该可以使用正确的算法在大约零秒内工作。例如，这在我的系统上大约需要 7 毫秒：

class Primes(bufsize: Int) {
  var n = 1
  val pbuf = new Array[Int](bufsize max 1)
  pbuf(0) = 2
  def isPrime(num: Int): Boolean = {
    var i = 0
    while (i < n && pbuf(i)*pbuf(i) <= num) {
      if (num % pbuf(i) == 0) return false
      i += 1
    }
    if (pbuf(i)*pbuf(i) < num) {
      i = pbuf(i)
      while (i*i <= num) {
        if (num % i == 0) return false
        i += 2
      }
    }
    return true;
  }
  def fillBuf {
    var i = 3
    n = 1
    while (n < bufsize) {
      if (isPrime(i)) { pbuf(n) = i; n += 1 }
      i += 2
    }
  }
  def lastPrime = { if (n<bufsize) fillBuf ; pbuf(pbuf.length-1) }
}
object Primes {
  def timedGet(num: Int) = {
    val t0 = System.nanoTime
    val p = (new Primes(num)).lastPrime
    val t1 = System.nanoTime
    (p , (t1-t0)*1e-9)
  }
}

结果（第二次通话；第一次有一些开销）：

scala> Primes.timedGet(10001)
res1: (Int, Double) = (104743,0.00683394)
于 2010-03-12T03:18:17.497 回答
1

这是一个递归解决方案（使用第一个解决方案中的 isPrime 函数）。喜欢不变性（即尽量不使用 s）似乎是一种很好的 Scala 风格，var所以我在这里做了（实际上没有vars 或vals！）。我这里没有安装 Scala，所以不知道这是否真的更快！

def problem_7:Int = { 
  def isPrime_(n: Int) = (n % 6 == 1 || n % 6 == 5) && isPrime(n)
  def process(n: Int, acc: List[Int]): Int = {
    if (acc.size == 10001) acc.head
    else process(n+1, if isPrime_(n) n :: acc else acc) 
  }
  process(1, Nil)
}
于 2010-03-11T22:11:40.137 回答
1

我认为你必须跳出框框思考:)

因为问题是可控的，所以您可以使用埃拉托色尼筛法非常有效地解决它。

于 2010-03-11T20:02:48.930 回答