Почему мой алгоритм для Project Euler Problem 12 такой медленный?

Question

Я создал решение для PE P12 в Scala, но очень и очень медленно. Может кто-нибудь может сказать мне, почему? Как это оптимизировать? CalculateDevisors () - наивный подход,

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. Не только вы не пропускаете числа, которые, как вы уже знаете, не являются простыми числами, но даже если вы исправить это, сложность этого алгоритма намного хуже , чем традиционное сито Эратосфена. Смотрите одну реализацию Scala для Sieve здесь .

Это не означает, что остальная часть вашего кода также не является оптимальной, но я оставлю это для других.

EDIT

Действительно, индексированный доступ к 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 2

Медленнее по сравнению с ....?Откуда вы знаете, что это проблема со Scala, а не с вашим алгоритмом?

По общему признанию, быстрое чтение кода предполагает, что вы можете пересчитывать простые и другие значения снова и снова.isPrimeInternal выскакивает как возможный случай, когда это может быть проблемой.

Answer 3

Мой алгоритм скала, который вычисляет делители заданного числа. Работало нормально в решении Проект Эйлера Задача 12.

def countDivisors (numberToFindDivisor: BigInt): 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)

}

Answer 4

Ваш код не компилируется, некоторые части отсутствуют, поэтому я думаю, здесь. Что-то, что часто ухудшает производительность - это бокс / распаковка, происходящие в коллекциях. Еще одна вещь, которую я заметил, это то, что вы строите свои простые числа как поток - что хорошо - но не пользуетесь этим в своей функции isPrime, которая использует примитивное колесо 2,3 (1 и 5 мод 6) вместо. Я могу ошибаться, но попробуйте заменить его на

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

Answer 5

CalculateDivisors может быть значительно улучшен, проверяя только делители до квадратного корня из числа.Каждый раз, когда вы найдете делитель ниже площади, вы также найдете один выше.

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
}