如何在scala中优化这个短因子函数？(创造50000 BigInts)

Question

我已经比较了scala版本

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

到python版本

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

事实证明,scala版本比python版本长了大约10倍.

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

Answer 1

您的Scala代码创建50,000个BigInt对象的事实不太可能在这里产生很大的不同.一个更大的问题是乘法算法 - Pythonlong使用Karatsuba乘法而Java BigInteger(BigInt仅包装)则不然.

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

import org.jscience.mathematics.number.LargeInteger

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

这比我机器上的Python解决方案更快.

更新:为了回应Luigi Plingi的回答,我使用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帮助.

Answer 2

我机器上的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)
  }