如何在Scala中优化for-understanding和循环?

问题

所以Scala应该和Java一样快。我正在重新审视我最初用Java解决的Scala中的一些问题577635634。具体问题5:"从1到20的所有数字均可被整除的最小正数是多少?"

这是我的Java解决方案,在我的机器上完成需要0.7秒:

public class P005_evenly_divisible implements Runnable{
    final int t = 20;

    public void run() {
        int i = 10;
        while(!isEvenlyDivisible(i, t)){
            i += 2;
        }
        System.out.println(i);
    }

    boolean isEvenlyDivisible(int a, int b){
        for (int i = 2; i <= b; i++) {
            if (a % i != 0) 
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        new P005_evenly_divisible().run();
    }
}

这是我对Scala的"直接翻译",需要103秒(147倍!)

object P005_JavaStyle {
    val t:Int = 20;
    def run {
        var i = 10
        while(!isEvenlyDivisible(i,t))
            i += 2
        println(i)
    }
    def isEvenlyDivisible(a:Int, b:Int):Boolean = {
        for (i <- 2 to b)
            if (a % i != 0)
                return false
        return true
    }
    def main(args : Array[String]) {
        run
    }
}

最后这是我对函数式编程的尝试,需要39秒(55倍)

object P005 extends App{
    def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
    def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
    println (find (2))
}

在Windows 7 64位上使用Scala 2.9.0.1。如何提高性能?难道我做错了什么?或者Java速度更快?


#1 热门回答(109 赞)

在这种特殊情况下的问题是你从for-expression中返回。反过来,它被转换为NonLocalReturnException的抛出,这是在封闭方法中捕获的。优化器可以消除foreach但是还不能消除throw / catch。投掷/捕获是昂贵的。但由于这种嵌套返回在Scala程序中很少见,因此优化器还没有解决这种情况。有一些工作正在改进优化器,希望很快能解决这个问题。


#2 热门回答(80 赞)

问题很可能是在方法isEvenlyDivisible中使用afor。用等效的whileloop替换for应该可以消除与Java的性能差异。

与Java的8949709428loops相反,Scala的for理解实际上是高阶方法的语法糖;在这种情况下,你在aRangeobject上调用foreach方法。 Scala'sfor非常普遍,但有时会导致痛苦的表现。

你可能想在Scala 2.9版中尝试-optimizeflag。观察到的性能可能取决于所使用的特定JVM,并且JIT优化器具有足够的"预热"时间来识别和优化热点。

最近在邮件列表上的讨论表明,Scala团队正致力于在简单的情况下改进for性能:

  • http://groups.google.com/group/scala-user/browse_thread/thread/86adb44d72ef4498
  • http://groups.google.com/group/scala-language/browse_thread/thread/94740a10205dddd2

以下是错误跟踪器中的问题:https://issues.scala-lang.org/browse/SI-4633

更新5/28

  • 作为一个短期解决方案,ScalaCL插件(alpha)将简单的Scala循环转换为等效的while循环。
  • 作为潜在的长期解决方案,来自EPFL和斯坦福大学的团队正在合作开展一个项目,以实现非常高性能的"虚拟"Scala的运行时编译。例如,多个惯用功能循环可以在运行时融合到最佳JVM字节码中,或者融合到另一个目标(例如GPU)。该系统是可扩展的,允许用户定义的DSL和转换。查看出版物和斯坦福大学课程笔记。初步代码可在Github上获得,预计将在未来几个月发布。

#3 热门回答(31 赞)

作为后续,我尝试了-optimize标志,它将运行时间从103秒减少到76秒,但这仍然比Java或while循环慢107倍。

然后我看着"功能"版本:

object P005 extends App{
  def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
  def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
  println (find (2))
}

并试图弄清楚如何以简洁的方式摆脱"forall"。我悲惨地失败了,想出来了

object P005_V2 extends App {
  def isDivis(x:Int):Boolean = {
    var i = 1
    while(i <= 20) {
      if (x % i != 0) return false
      i += 1
    }
    return true
  }
  def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
  println (find (2))
}

我的狡猾的5线解决方案已经气流到12行。但是,这个版本运行在0.71秒,速度与原始Java版本相同,比使用"forall"(40.2秒)的版本快56倍! (请参阅下面的编辑,了解为什么这比Java快)

显然,我的下一步是将上面的内容转换回Java,但Java无法处理它并抛出一个带有n的StackOverflowError大约22000个标记。

然后我抓了一下头,用更多的尾递归替换了"while",这节省了几行,运行速度一样快,但让我们面对它,更难以阅读:

object P005_V3 extends App {
  def isDivis(x:Int, i:Int):Boolean = 
    if(i > 20) true
    else if(x % i != 0) false
    else isDivis(x, i+1)

  def find(n:Int):Int = if (isDivis(n, 2)) n else find (n+2)
  println (find (2))
}

所以Scala的尾部递归赢得了胜利,但令我惊讶的是,像"for"循环(和"forall"方法)这样简单的东西基本上被破坏了,必须被不优雅和冗长的"whiles"或尾递归所取代。 。我尝试使用Scala的原因很多,原因在于简洁的语法,但如果我的代码运行速度慢100倍,那就不好了!

编辑:(已删除)

编辑编辑:运行时间在2.5秒和0.7秒之间的前一个差异完全是由于是否使用了32位或64位JVM。命令行中的Scala使用JAVA_HOME设置的任何内容,而Java则使用64位(如果可用)。 IDE有自己的设置。这里的一些测量:Scala execution times in Eclipse