arrays - Project Euler 7 Scala 问题

Question

我正在尝试使用 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 中使用列表/数组？

Answer 1

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

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

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

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