14

我已经比较了 scala 版本

(BigInt(1) to BigInt(50000)).reduce(_ * _)

到python版本

reduce(lambda x,y: x*y, range(1,50000))

事实证明，scala 版本比 python 版本花费了大约 10 倍的时间。

我猜，一个很大的区别是 python 可以使用它的原生 long 类型，而不是为每个数字创建新的 BigInt 对象。但是scala中有解决方法吗？

4

4 回答 4

16

您的 Scala 代码创建 50,000 个对象这一事实BigInt不太可能在这里产生太大影响。更大的问题是乘法算法——<a href="http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup" rel="nofollow noreferrer">Pythonlong使用Karatsuba 乘法而Java BigInteger（BigInt只是包装）没有。

最简单的解决方法可能是切换到更好的任意精度数学库，例如JScience的：

import org.jscience.mathematics.number.LargeInteger

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

这比我机器上的 Python 解决方案要快。

更新：我已经使用Caliper编写了一些快速基准测试代码以响应Luigi Plingi 的回答，这在我的（四核）机器上给出了以下结果：

              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也有帮助。

于 2011-10-23T01:53:43.670 回答
9

我机器上的 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 个核心，但更多的核心应该会带来更大的性能提升。

所以，实验上，优化这个函数的方法是

a) 使用fold而不是reduce

b) 使用并行集合

更新： 受到将计算分解成更小的块可以加快速度的观察结果的启发，我设法让他跟随215 ms在我的机器上运行，这比标准并行算法提高了 40%。（使用 BigInt，需要 615 毫秒。）此外，它不使用并行集合，但不知何故使用了 90% 的 CPU（与 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)
  }
于 2011-10-23T02:19:09.310 回答
1

这里的另一个技巧可能是尝试两者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。猜猜你从树的哪一边开始减少很重要:)

于 2011-10-24T11:28:21.427 回答
0

在 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 CPU @ 2.80GHz（最大 3.50GHz）、RAM 12Gb 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

顺便说一句，在实施 Schönhage-Strassen 算法后提高大于 20000 的数字的阶乘计算效率，或者等到它将被合并到 JDK 9 并且 Scala 将能够使用它

于 2014-12-26T15:35:12.790 回答