为什么我的算法项目欧拉问题12这么慢？

本文介绍了为什么我的算法项目欧拉问题12这么慢？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我已经创造了在斯卡拉PE P12解决方案，但非常非常缓慢。可有人能告诉我为什么吗？如何优化呢？ calculateDevisors（） - 幼稚的做法和calculateNumberOfDivisors（） - 除数函数具有相同的速度：/

进口annotation.tailrec 高清isPrime（编号：智力）：布尔= {   如果（数2 ||（数= 2及！＆安培;！号％2 == 0）||（号码= 3和;＆安培;号码％3 == 0））     假   其他 {     VAL sqrtOfNumber =的Math.sqrt（数）toInt     @tailrec高清isPrimeInternal（除数：智力，增量为：int）：布尔= {       如果（除数＆GT; sqrtOfNumber）         真正       否则，如果（编号％除数== 0）         假       其他         isPrimeInternal（除数+增量，6 - 增量）     }     isPrimeInternal（5，2）   } } 高清generatePrimeNumbers（计数：智力）：列表[INT] = {   @tailrec高清generatePrimeNumbersInternal（编号：INT = 3，指数：= 0，                                             primeNumbers：列表[INT] =名单（2））：列表[INT] = {     如果（指数==计数）       质数     否则如果（isPrime（数））       generatePrimeNumbersInternal（数+ 2，指数+ 1，primeNumbers：+数字）     其他       generatePrimeNumbersInternal（号码+ 2，索引，primeNumbers）   }   generatePrimeNumbersInternal（）; } VAL素数= Stream.cons（2，Stream.from（3，2）过滤{isPrime（_）}） 高清calculateDivisors（编号：智力）= {   对于 {     除数和放大器; LT; - 1号     如果（编号％除数== 0）   }产量除数 } @inline高清decomposeToPrimeNumbers（编号：智力）= {   VAL sqrtOfNumber =的Math.sqrt（数）.toInt   @tailrec高清decomposeToPrimeNumbersInternal（编号：诠释，primeNumberIndex：= 0，                                                因素：列表[INT] = List.empty [INT]）：列表[INT] = {     VAL primeNumber =素数（primeNumberIndex）     如果（primeNumberIndex＆GT; sqrtOfNumber）       因素     否则，如果（编号％primeNumber == 0）       decomposeToPrimeNumbersInternal（数字/ primeNumber，primeNumberIndex，因素：+ primeNumber）     其他       decomposeToPrimeNumbersInternal（号码，primeNumberIndex + 1，因子）   }   decomposeToPrimeNumbersInternal（数字）GROUPBY {N =＆GT;当n} {地图（N：诠释，L：列表[INT]）=＆GT; （N，L尺寸）} } @inline高清calculateNumberOfDivisors（编号：智力）= {   decomposeToPrimeNumbers（数字）地图{案（primeNumber，指数）=＆GT;指数+1}产物 } @tailrec高清计算（编号：INT = 12300）：INT = {   VAL triangleNumber =（（*号数）+号码）/ 2   VAL的startTime = System.currentTimeMillis的（）   VAL numberOfDivisors = calculateNumberOfDivisors（triangleNumber）   VAL elapsedTime = System.currentTimeMillis的（） - startTime时   的printf（％D：V：％D D：％D T：％DMS的\ n，数，triangleNumber，numberOfDivisors，elapsedTime）   如果（numberOfDivisors＆GT; 500）     triangleNumber   其他     计算方法（数+ 1） } 的println（计算（））

解决方案

您可以首先检查的什么的速度很慢。您的首要计算，举例来说，是非常，非常缓慢。对于每个编号 N ，试图从5分 N 每个每个数字为开方（N），跳过了2和3的倍数，不仅不要跳过你已经知道是不是素数的数字，但即使你解决这个问题，在这个算法的复杂度的更糟糕比埃拉托色尼传统筛。见1斯卡拉实现筛 rel="nofollow">。

这是不是说，您的code，其余是不是最理想的为好，但我会留给他人。

修改

事实上，索引访问流是可怕的。这里是不是将一切阵列与流作品改写。此外，之前的第一个如果在您的code一个可能的错误注意上述表示的。

@tailrec高清decomposeToPrimeNumbersInternal（编号：诠释，素数：流[INT]，                                                因素：列表[INT] = List.empty [INT]）：列表[INT] = {     VAL primeNumber = primes.head     //与sqrtOfNumber比较primeNumberIndex没有任何意义     如果（primeNumber＆GT; sqrtOfNumber）       因素     否则，如果（编号％primeNumber == 0）       decomposeToPrimeNumbersInternal（数字/ primeNumber，素数，因素：+ primeNumber）     其他       decomposeToPrimeNumbersInternal（号码，primes.tail，因子）   }

I have created solution for PE P12 in Scala but is very very slow. Can somebody can tell me why? How to optimize this? calculateDevisors() - naive approach and calculateNumberOfDivisors() - divisor function has the same speed :/

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())

解决方案

You could first check what is slow. Your prime calculation, for instance, is very, very slow. For each number n, you try to divide n by each each number from 5 to sqrt(n), skipping multiples of 2 and 3. Not only you do not skip numbers you already know are not primes, but even if you fix this, the complexity of this algorithm is much worse than the traditional Sieve of Eratosthenes. See one Scala implementation for the Sieve here.

That is not to say that the rest of your code isn't suboptimal as well, but I'll leave that for others.

EDIT

Indeed, indexed access to Stream is terrible. Here's a rewrite that works with Stream, instead of converting everything to Array. Also, note the remark before the first if for a possible bug in your code.

@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) }