如何在Scala中优化此短阶乘函数? (创建50000个BigInts) [英] How to optimize this short factorial function in scala? (Creating 50000 BigInts)

问题描述

我已经整理了scala版本

I've compaired the scala version

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

到python版本

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

事实证明，scala版本花费的时间比python版本长约10倍.

and it turns out, that the scala version took about 10 times longer than the python version.

我猜，一个很大的不同是python可以使用其本机长型而不是为每个数字创建新的BigInt对象.但是scala中有解决方法吗?

I'm guessing, a big difference is that python can use its native long type instead of creating new BigInt-objects for each number. But is there a workaround in scala?

推荐答案

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

The fact that your Scala code creates 50,000 BigInt objects is unlikely to be making much of a difference here. A bigger issue is the multiplication algorithm—Python's long uses Karatsuba multiplication and Java's BigInteger (which BigInt just wraps) doesn't.

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

The easiest workaround is probably to switch to a better arbitrary precision math library, like JScience's:

import org.jscience.mathematics.number.LargeInteger

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

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

This is faster than the Python solution on my machine.

更新:我已经使用一些快速基准测试代码 /code.google.com/p/caliper/"rel =" nofollow noreferrer>卡尺，以响应

Update: I've written some quick benchmarking code using Caliper in response to Luigi Plingi's answer, which gives the following results on my (quad core) machine:

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

I don't see the difference between reduce and fold that he does, but the moral is clear: if you can use Scala 2.9's parallel collections, they'll give you a huge improvement, but switching to LargeInteger helps as well.

这篇关于如何在Scala中优化此短阶乘函数? (创建50000个BigInts)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！