为什么我的Project Euler Problem 12的算法如此缓慢？

Question

我已经在Scala中为PE P12创建了解决方案，但速度非常慢。有人可以告诉我为什么吗？如何优化这个？ calculateDevisors（） - 幼稚的方法和calculateNumberOfDivisors（） - 除数函数具有相同的速度：/

import annotation.tailrec 

def isPrime(number: Int): Boolean = { 
    if (number < 2 || (number != 2 && number % 2 == 0) || (number != 3 && number % 3 == 0)) 
    false 
    else { 
    val sqrtOfNumber = math.sqrt(number) toInt 

    @tailrec def isPrimeInternal(divisor: Int, increment: Int): Boolean = { 
     if (divisor > sqrtOfNumber) 
     true 
     else if (number % divisor == 0) 
     false 
     else 
     isPrimeInternal(divisor + increment, 6 - increment) 
    } 

    isPrimeInternal(5, 2) 
    } 
} 

def generatePrimeNumbers(count: Int): List[Int] = { 
    @tailrec def generatePrimeNumbersInternal(number: Int = 3, index: Int = 0, 
              primeNumbers: List[Int] = List(2)): List[Int] = { 
    if (index == count) 
     primeNumbers 
    else if (isPrime(number)) 
     generatePrimeNumbersInternal(number + 2, index + 1, primeNumbers :+ number) 
    else 
     generatePrimeNumbersInternal(number + 2, index, primeNumbers) 
    } 

    generatePrimeNumbersInternal(); 
} 

val primes = Stream.cons(2, Stream.from(3, 2) filter {isPrime(_)}) 

def calculateDivisors(number: Int) = { 
    for { 
    divisor &lt;- 1 to number 
    if (number % divisor == 0) 
    } yield divisor 
} 

@inline def decomposeToPrimeNumbers(number: Int) = { 
    val sqrtOfNumber = math.sqrt(number).toInt 

    @tailrec def decomposeToPrimeNumbersInternal(number: Int, primeNumberIndex: Int = 0, 
               factors: List[Int] = List.empty[Int]): List[Int] = { 
    val primeNumber = primes(primeNumberIndex) 

    if (primeNumberIndex > sqrtOfNumber) 
     factors 
    else if (number % primeNumber == 0) 
     decomposeToPrimeNumbersInternal(number/primeNumber, primeNumberIndex, factors :+ primeNumber) 
    else 
     decomposeToPrimeNumbersInternal(number, primeNumberIndex + 1, factors) 
    } 

    decomposeToPrimeNumbersInternal(number) groupBy {n => n} map {case (n: Int, l: List[Int]) => (n, l size)} 
} 

@inline def calculateNumberOfDivisors(number: Int) = { 
    decomposeToPrimeNumbers(number) map {case (primeNumber, exponent) => exponent + 1} product 
} 

@tailrec def calculate(number: Int = 12300): Int = { 
    val triangleNumber = ((number * number) + number)/2 
    val startTime = System.currentTimeMillis() 
    val numberOfDivisors = calculateNumberOfDivisors(triangleNumber) 
    val elapsedTime = System.currentTimeMillis() - startTime 

    printf("%d: V: %d D: %d T: %dms\n", number, triangleNumber, numberOfDivisors, elapsedTime) 

    if (numberOfDivisors > 500) 
    triangleNumber 
    else 
    calculate(number + 1) 
} 

println(calculate()) 

Answer 1

calculateDivisors可以通过仅检查除数最多数量的平方根得到极大改善。每次在sqrt下找到一个除数时，您也会在上面找到一个除数。

def calculateDivisors(n: Int) = { 
    var res = 1 
    val intSqrt = Math.sqrt(n).toInt 
    for (i <- 2 until intSqrt) { 
     if (n % i == 0) { 
      res += 2 
     } 
    } 
    if (n == intSqrt * intSqrt) { 
     res += 1 
    } 
    res 
} 

Answer 2

比较慢....？你怎么知道这是Scala的问题，而不是你的算法？

无可否认，快速读取代码表明您可能会重复计算素数和其他值。 isPrimeInternal作为可能的情况跳出来，这可能是一个问题。

Answer 3

您的代码不可编译，某些部分丢失，所以我在这里猜测。经常伤害表演的一些事情是在收藏中发生拳击/拆箱。我注意到的另一件事是，你把你的素数作为一个Stream来处理 - 这是一件好事 - 但是不要在你的isPrime函数中利用这个函数，它使用原始2,3轮（1和5 mod 6）代替。我可能是错的，但试图通过

def isPrime(number: Int): Boolean = { 
    val sq = math.sqrt(number + 0.5).toInt 
    ! primes.takeWhile(_ <= sq).exists(p => number % p == 0) 
} 

Answer 4

来取代它你可以先检查什么是缓慢的。例如，你的主要计算非常非常缓慢。对于每个号码n，您尝试划分n，每个号码从5到sqrt(n)，跳过2和3的倍数。不仅不会跳过您已知的不是素数的数字，但即使您修复此问题，复杂性这个算法比传统的Eratosthenes Sieve的much worse。查看Sieve here的一个Scala实现。

这并不是说你的代码的其余部分并不是最优的，但我会为其他人留下。

编辑

实际上，索引访问Stream是可怕的。这是一个重写，与Stream一起使用，而不是将所有内容都转换为Array。另外，请注意第一个if之前的注释，以查看代码中可能存在的错误。

@tailrec def decomposeToPrimeNumbersInternal(number: Int, primes: Stream[Int], 
               factors: List[Int] = List.empty[Int]): List[Int] = { 
    val primeNumber = primes.head 

    // Comparing primeNumberIndex with sqrtOfNumber didn't make any sense 
    if (primeNumber > sqrtOfNumber) 
     factors 
    else if (number % primeNumber == 0) 
     decomposeToPrimeNumbersInternal(number/primeNumber, primes, factors :+ primeNumber) 
    else 
     decomposeToPrimeNumbersInternal(number, primes.tail, factors) 
    } 

Answer 5

我的斯卡拉算法，计算给定数量的除数。它在 项目欧拉问题12.

DEF countDivisors（：BigInt有numberToFindDivisor）：溶液工作得很好INT = {

def countWithAcc(numberToFindDivisor: BigInt, currentCandidate: Int, currentCountOfDivisors: Int,limit: BigInt): Int = { 

    if (currentCandidate >= limit) currentCountOfDivisors 

    else { 

    if (numberToFindDivisor % currentCandidate == 0) 

     countWithAcc(numberToFindDivisor, currentCandidate + 1, currentCountOfDivisors + 2, numberToFindDivisor/currentCandidate) 

    else 

     countWithAcc(numberToFindDivisor, currentCandidate + 1, currentCountOfDivisors, limit) 

    } 

} 

countWithAcc(numberToFindDivisor, 1, 0, numberToFindDivisor + 1) 

}