Я написал наивный тестовый слой для измерения производительности трех видов факториальной реализации: на основе петли, без хвостового рекурсивного и хвостового рекурсивного.Scala recursion vs loop: соображения производительности и времени выполнения
Удивительно мне худший производительным были те петли («в то время», как ожидается, будет более эффективным, поэтому я и при условии), которые стоят почти в два раза, чем хвост рекурсивной альтернативы.
ОТВЕТ: фиксируя выполнение цикла избежать * = оператор Wich опережать худший с BigInt из-за его внутренностей «петли» стал самым быстрым, как ожидалось
Другой «Вуду» поведение Я опытным было исключение StackOverflow , которое не было выбрано системно для одного и того же ввода в случае нерекурсивной реализации без хвоста. Я могу обойти StackOverlow путем постепенного вызова функции с большим и большим ценностей ... Я чувствую себя с ума :) Ответ: JVM требуется сходиться во время запуска, то поведение является когерентным и систематическое
Это код :
final object Factorial {
type Out = BigInt
def calculateByRecursion(n: Int): Out = {
require(n>0, "n must be positive")
n match {
case _ if n == 1 => return 1
case _ => return n * calculateByRecursion(n-1)
}
}
def calculateByForLoop(n: Int): Out = {
require(n>0, "n must be positive")
var accumulator: Out = 1
for (i <- 1 to n)
accumulator = i * accumulator
accumulator
}
def calculateByWhileLoop(n: Int): Out = {
require(n>0, "n must be positive")
var accumulator: Out = 1
var i = 1
while (i <= n) {
accumulator = i * accumulator
i += 1
}
accumulator
}
def calculateByTailRecursion(n: Int): Out = {
require(n>0, "n must be positive")
@tailrec def fac(n: Int, acc: Out): Out = n match {
case _ if n == 1 => acc
case _ => fac(n-1, n * acc)
}
fac(n, 1)
}
def calculateByTailRecursionUpward(n: Int): Out = {
require(n>0, "n must be positive")
@tailrec def fac(i: Int, acc: Out): Out = n match {
case _ if i == n => n * acc
case _ => fac(i+1, i * acc)
}
fac(1, 1)
}
def comparePerformance(n: Int) {
def showOutput[A](msg: String, data: (Long, A), showOutput:Boolean = false) =
showOutput match {
case true => printf("%s returned %s in %d ms\n", msg, data._2.toString, data._1)
case false => printf("%s in %d ms\n", msg, data._1)
}
def measure[A](f:()=>A): (Long, A) = {
val start = System.currentTimeMillis
val o = f()
(System.currentTimeMillis - start, o)
}
showOutput ("By for loop", measure(()=>calculateByForLoop(n)))
showOutput ("By while loop", measure(()=>calculateByWhileLoop(n)))
showOutput ("By non-tail recursion", measure(()=>calculateByRecursion(n)))
showOutput ("By tail recursion", measure(()=>calculateByTailRecursion(n)))
showOutput ("By tail recursion upward", measure(()=>calculateByTailRecursionUpward(n)))
}
}
ниже некоторые выходы из SBT консоли (до «во время» реализация):
scala> example.Factorial.comparePerformance(10000)
By loop in 3 ns
By non-tail recursion in >>>>> StackOverflow!!!!!… see later!!!
........
scala> example.Factorial.comparePerformance(1000)
By loop in 3 ms
By non-tail recursion in 1 ms
By tail recursion in 4 ms
scala> example.Factorial.comparePerformance(5000)
By loop in 105 ms
By non-tail recursion in 27 ms
By tail recursion in 34 ms
scala> example.Factorial.comparePerformance(10000)
By loop in 236 ms
By non-tail recursion in 106 ms >>>> Now works!!!
By tail recursion in 127 ms
scala> example.Factorial.comparePerformance(20000)
By loop in 977 ms
By non-tail recursion in 495 ms
By tail recursion in 564 ms
scala> example.Factorial.comparePerformance(30000)
By loop in 2285 ms
By non-tail recursion in 1183 ms
By tail recursion in 1281 ms
Ниже некоторые выходы из SBT консоли (После того, как «в то время» реализация):
scala> example.Factorial.comparePerformance(10000)
By for loop in 252 ms
By while loop in 246 ms
By non-tail recursion in 130 ms
By tail recursion in 136 ns
scala> example.Factorial.comparePerformance(20000)
By for loop in 984 ms
By while loop in 1091 ms
By non-tail recursion in 508 ms
By tail recursion in 560 ms
Ниже некоторые выходы из SBT консоли (после того, как «вверх» реализации хвостовой рекурсии) мир пришел назад здравый:
scala> example.Factorial.comparePerformance(10000)
By for loop in 259 ms
By while loop in 229 ms
By non-tail recursion in 114 ms
By tail recursion in 119 ms
By tail recursion upward in 105 ms
scala> example.Factorial.comparePerformance(20000)
By for loop in 1053 ms
By while loop in 957 ms
By non-tail recursion in 513 ms
By tail recursion in 565 ms
By tail recursion upward in 470 ms
ниже некоторые выходы из SBT консоли после закрепления BigInt умножения в «петле»: мир полностью са пе:
scala> example.Factorial.comparePerformance(20000)
By for loop in 498 ms
By while loop in 502 ms
By non-tail recursion in 521 ms
By tail recursion in 611 ms
By tail recursion upward in 503 ms
BigInt над головой и глупы реализация мною маскируется ожидаемое поведение.
Спасибо, ребята
PS .: В конце концов, я должен вновь титул этот пост к «А lernt урок по BigInts»
В чем вопрос? – Dan
«Циклы следует избегать». Это вводит в заблуждение, for-loops, как правило, намного медленнее, чем эквивалентные, в то время как петли в scala. Рекурсия хвоста обычно быстрее, чем нерегулярная рекурсия, я собираюсь выйти на конечность и сказать, что она медленнее из-за закрытия, которое вы создаете до запуска функции. –
Кто может помочь мне понять это поведение, указывая на авторитетную ссылку. –