Python на моей машине:
def func():
start= time.clock()
reduce(lambda x,y: x*y, range(1,50000))
end= time.clock()
t = (end-start) * 1000
print t
дает 1219 ms
Scala:
def timed[T](f: => T) = {
val t0 = System.currentTimeMillis
val r = f
val t1 = System.currentTimeMillis
println("Took: "+(t1 - t0)+" ms")
r
}
timed { (BigInt(1) to BigInt(50000)).reduce(_ * _) }
4251 ms
timed { (BigInt(1) to BigInt(50000)).fold(BigInt(1))(_ * _) }
4224 ms
timed { (BigInt(1) to BigInt(50000)).par.reduce(_ * _) }
2083 ms
timed { (BigInt(1) to BigInt(50000)).par.fold(BigInt(1))(_ * _) }
689 ms
// using org.jscience.mathematics.number.LargeInteger from Travis's answer
timed { val a = (1 to 50000).foldLeft(LargeInteger.ONE)(_ times _) }
3327 ms
timed { val a = (1 to 50000).map(LargeInteger.valueOf(_)).par.fold(
LargeInteger.ONE)(_ times _) }
361 ms
Эти 689 мс и 361 мс были после нескольких прогонов прогона. Они оба начинали примерно с 1000 мс, но, похоже, разогревались в разной степени. Похоже, что параллельные коллекции прогреваются значительно больше, чем непараллельные: непараллельные операции значительно не сократились с первых запусков.
.par (имеется в виду, использовать параллельные коллекции), казалось, ускорил fold больше, чем reduce. У меня только 2 ядра, но большее количество ядер должно увеличить производительность.
Итак, экспериментально, способ оптимизировать эту функцию -
а) Используйте fold вместо reduce
б) Использовать параллельные коллекции
обновление:
Вдохновленный наблюдением о том, что разбиение вычислений на более мелкие куски ускоряет процесс, мне удалось заставить его следовать за 215 ms на моей машине, что на 40% лучше стандартного распараллеленного алгоритма. (При использовании BigInt это занимает 615 мс.) Кроме того, он не использует параллельные коллекции, но каким-то образом использует 90% ЦП (в отличие от BigInt).
import org.jscience.mathematics.number.LargeInteger
def fact(n: Int) = {
def loop(seq: Seq[LargeInteger]): LargeInteger = seq.length match {
case 0 => throw new IllegalArgumentException
case 1 => seq.head
case _ => loop {
val (a, b) = seq.splitAt(seq.length / 2)
a.zipAll(b, LargeInteger.ONE, LargeInteger.ONE).map(i => i._1 times i._2)
}
}
loop((1 to n).map(LargeInteger.valueOf(_)).toIndexedSeq)
}