如何优化 Scala 中的理解和循环?

2022-08-31 08:24:35

所以Scala应该和Java一样快。我正在重新审视Scala中的一些欧拉项目问题,这些问题最初是在Java中解决的。具体问题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上使用Scala 2.9.0.1 64位。如何提高性能?我做错了什么吗?还是Java只是快得多?


答案 1

此特定情况下的问题是,您从 for 表达式中返回。这反过来又被转换为NonLocalReturnException的抛出,该异常在封闭方法中被捕获。优化器可以消除前方,但不能消除投掷/捕获。投掷/接球很昂贵。但是由于这种嵌套返回在 Scala 程序中很少见,因此优化程序尚未解决这种情况。正在进行改进优化器的工作,希望能很快解决此问题。


答案 2

问题很可能是在方法中使用理解。用等效的循环替换应该会消除与 Java 的性能差异。forisEvenlyDivisibleforwhile

与Java的循环相反,Scala的理解实际上是高阶方法的句法糖;在本例中,您将对对象调用该方法。Scala非常普遍,但有时会导致痛苦的表现。forforforeachRangefor

您可能想在 Scala 2.9 版中试用该标志。观察到的性能可能取决于正在使用的特定 JVM,并且 JIT 优化器具有足够的“预热”时间来识别和优化热点。-optimize

最近在邮件列表上的讨论表明,Scala团队正在努力提高简单情况下的性能:for

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

5/28年更新

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

推荐