如何在scala中优化这个简短的阶乘函数？ (创建50000 BigInts)

发布时间：2020-12-16 09:22:40 所属栏目：安全来源：网络整理

导读：我已经比较scala版本 (BigInt(1) to BigInt(50000)).reduce(_ * _) 到python版本 reduce(lambda x,y: x*y,range(1,50000)) 事实证明,scala版本比python版本花费了大约10倍. 我猜,一个很大的区别是,python可以使用它的本机长类型,而不是为每个数字创建新的Big

我已经比较scala版本

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

到python版本

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

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

我猜,一个很大的区别是,python可以使用它的本机长类型,而不是为每个数字创建新的BigInt对象.但是在scala中有解决办法吗？

解决方法

事实上,您的Scala代码创建50,000个BigInt对象不太可能在这里有很大的不同.更大的问题是乘法算法- Python’s long使用 Karatsuba multiplication和Java的BigInteger(BigInt只是包装)没有.

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

import org.jscience.mathematics.number.LargeInteger

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

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

更新：我写了some quick benchmarking code使用Caliper响应Luigi Plingi’s answer,这给我的(四核)机器以下结果：

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 =

我看不出他所做的减少和折中的区别,但是道德是清楚的：如果你可以使用Scala 2.9的并行集合,它们会给你一个很大的改进,但是也可以改变LargeInteger.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!