Как оптимизировать эту короткую факториальную функцию в scala? (Создание 50000 BigInts)

Тот факт, что ваш Scala-код создает 50 000 объектов BigInt, вряд ли имеет здесь большое значение. Более серьезной проблемой является алгоритм умножения — Python long использует умножение Карацубы, а BigInteger в Java (которое BigInt просто обертывает) не использует.

Самый простой обходной путь, вероятно, заключается в переключении на лучшую математическую библиотеку произвольной точности, например JScience:

import org.jscience.mathematics.number.LargeInteger

(1 to 50000).foldLeft(LargeInteger.ONE)(_ times _)

Это быстрее, чем решение Python на моей машине.

Обновление: я написал некоторый код для быстрого тестирования, используя Caliper в ответ на Ответ Луиджи Плинги, который дает следующие результаты на моей (четырехъядерной) машине:

              benchmark   ms linear runtime
         BigIntFoldLeft 4774 ==============================
             BigIntFold 4739 =============================
           BigIntReduce 4769 =============================
      BigIntFoldLeftPar 4642 =============================
          BigIntFoldPar  500 ===
        BigIntReducePar  499 ===
   LargeIntegerFoldLeft 3042 ===================
       LargeIntegerFold 3003 ==================
     LargeIntegerReduce 3018 ==================
LargeIntegerFoldLeftPar 3038 ===================
    LargeIntegerFoldPar  246 =
  LargeIntegerReducePar  260 =

Я не вижу разницы между reduce и fold, которую он видит, но мораль ясна: если вы можете использовать параллельные коллекции Scala 2.9, они дадут вам огромное улучшение, но переход на LargeInteger тоже помогает.

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

Скала:

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

Еще один трюк здесь может заключаться в том, чтобы попробовать и reduceLeft, и reduceRight, чтобы увидеть, что быстрее. В вашем примере я получаю гораздо более быстрое выполнение reduceRight:

scala> timed { (BigInt(1) to BigInt(50000)).reduceLeft(_ * _) }
Took: 4605 ms

scala> timed { (BigInt(1) to BigInt(50000)).reduceRight(_ * _) }
Took: 2004 ms

Та же разница между foldLeft и foldRight. Думаю, имеет значение, с какой стороны дерева вы начинаете уменьшать :)

Наиболее эффективным способом вычисления факториала в Scala является использование стратегии «разделяй и властвуй»:

def fact(n: Int): BigInt = rangeProduct(1, n)

private def rangeProduct(n1: Long, n2: Long): BigInt = n2 - n1 match {
  case 0 => BigInt(n1)
  case 1 => BigInt(n1 * n2)
  case 2 => BigInt(n1 * (n1 + 1)) * n2
  case 3 => BigInt(n1 * (n1 + 1)) * ((n2 - 1) * n2)
  case _ => 
    val nm = (n1 + n2) >> 1
    rangeProduct(n1, nm) * rangeProduct(nm + 1, n2)
}

Также для увеличения скорости используйте последнюю версию JDK и следующие параметры JVM:

-server -XX:+TieredCompilation

Ниже приведены результаты для процессора Intel(R) Core(TM) i7-2640M с частотой 2,80 ГГц (макс. 3,50 ГГц), ОЗУ 12 ГБ DDR3-1333, Windows 7 sp1, Oracle JDK 1.8.0_25-b18 64-разрядная версия:

(BigInt(1) to BigInt(100000)).product took: 3,806 ms with 26.4 % of CPU usage
(BigInt(1) to BigInt(100000)).reduce(_ * _) took: 3,728 ms with 25.4 % of CPU usage
(BigInt(1) to BigInt(100000)).reduceLeft(_ * _) took: 3,510 ms with 25.1 % of CPU usage
(BigInt(1) to BigInt(100000)).reduceRight(_ * _) took: 4,056 ms with 25.5 % of CPU usage
(BigInt(1) to BigInt(100000)).fold(BigInt(1))(_ * _) took: 3,697 ms with 25.5 % of CPU usage
(BigInt(1) to BigInt(100000)).par.product took: 406 ms with 66.3 % of CPU usage
(BigInt(1) to BigInt(100000)).par.reduce(_ * _) took: 296 ms with 71.1 % of CPU usage
(BigInt(1) to BigInt(100000)).par.reduceLeft(_ * _) took: 3,495 ms with 25.3 % of CPU usage
(BigInt(1) to BigInt(100000)).par.reduceRight(_ * _) took: 3,900 ms with 25.5 % of CPU usage
(BigInt(1) to BigInt(100000)).par.fold(BigInt(1))(_ * _) took: 327 ms with 56.1 % of CPU usage
fact(100000) took: 203 ms with 28.3 % of CPU usage

Кстати, чтобы повысить эффективность вычисления факториала для чисел, превышающих 20000, используйте после реализации алгоритма Шёнхаге-Штрассена или подождите пока он не будет объединен с JDK 9 и Scala не сможет его использовать