如何在Scala中优化for-understanding和循环？-Java 学习之路

问题

所以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

原文链接

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

问题

#1 热门回答(109 赞)

#2 热门回答(80 赞)

#3 热门回答(31 赞)

相关问题