项目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;
}

后来我尝试了同样的问题而没有在数据缓冲区中存储素数.这需要.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.对a的任何引用都会Int根据需要自动装箱和取消装箱,这使得它非常慢.使用Scala 2.7的速度非常慢,它使用Java原语来做到这一点,这非常缓慢.Scala 2.8采用了另一种方法,使其更快.但任何拳击/拆箱都会让你失望.此外,您首先ArrayBuffer在堆中查找,然后再次查找java.lang.Integer包含Int- 两个内存访问,这使得它比其他解决方案慢.

当Scala集合变得专业化时,它应该更快.我不知道是否应该足以击败你的第二个版本.

现在,你可以采取的措施是改为使用Array.因为Java Array没有被删除,所以你可以避免装箱/拆箱.

此外,当您使用for-comprehensions时,您的代码将有效地存储在为每个元素调用的方法中.所以你也在进行很多方法调用,这是另一个原因,这是另一个原因.唉,有人为Scala编写了一个插件,该插件优化了至少一个for-comprehension案例以避免这种情况.