performance - 为什么我的欧拉计划第 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

您可以先检查什么 慢。例如，您的素数计算非常非常慢。对于每个数字 n，您尝试将 n 除以从 5 到 sqrt(n) 的每个数字，跳过 2 和 3 的倍数。你不仅不会跳过你已经知道不是素数的数字，而且即使你解决了这个问题，这个算法的复杂度也是much worse。比传统的埃拉托色尼筛法。查看 Sieve 的一个 Scala 实现 here .

这并不是说您的其余代码也不是最理想的，但我会把它留给其他人。

编辑

确实，对 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)
  }