如何在Scala中优化理解和循环？
所以Scala应该和Java一样快。 我正在重新讨论我最初在Java中处理的Scala中的一些Project Euler问题。 具体问题5：“从1到20的所有数字均匀分布的最小正数是多less？”
这是我的Java解决scheme，需要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 } }
最后这是我的function编程的尝试，这需要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只是快了很多？
在这种情况下，问题是你从forexpression式中返回。 这反过来又被翻译成一个NonLocalReturnException的throw，它被封闭的方法所捕获。 优化器可以消除foreach，但还不能消除throw / catch。 扔/抓是昂贵的。 但是由于这样的嵌套返回在Scala程序中并不多见，所以优化器还没有解决这个问题。 有一些工作正在改进优化器，希望能尽快解决这个问题。
这个问题很可能是在方法中使用了一个理解的方式。 用while循环代替将消除与Java的性能差异。
与Java的for循环相反，Scala的理解实际上是高阶方法的语法糖; 在这种情况下，您正在调用Range对象上的foreach方法。 斯卡拉的是非常一般的，但有时会导致痛苦的performance。
您可能想要在Scala 2.9版中尝试使用-optimize标志。 观察到的性能可能取决于所使用的特定JVM，而JIT优化器具有足够的“预热”时间来识别和优化热点。
最近在邮件列表上的讨论表明，斯卡拉团队正在努力提高性能在简单的情况下：
- 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 ：
- 作为一个短期解决scheme， ScalaCL插件（alpha）将把简单的Scala循环转换为
while循环的等价物。 - 作为一个潜在的更长期的解决scheme，EPFL和斯坦福大学的团队正在合作开发一个项目，以实现“虚拟”Scala的运行时编译，以获得非常高的性能。 例如，多个惯用function循环可以在运行时融合到最佳的JVM字节码中，或者融合到另一个目标，如GPU。 该系统是可扩展的，允许用户定义的DSL和转换。 查看出版物和斯坦福课程笔记 。 Github上提供了初步的代码，在未来的几个月内将会发布一个版本。
作为后续，我尝试了-optimize标志，它将运行时间从103减less到76秒，但仍然比Java或while循环慢107倍。
然后我在看“function”版本：
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)) }
并试图弄清楚如何简洁地摆脱“虚假”。 我悲惨地失败了，想出了
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线解决schemebalooned到12线。 然而，这个版本运行时间为0.71秒 ，与原来的Java版本速度相同，比使用“forall”（40.2秒）的版本快56倍！ （请参阅下面的编辑为什么这比Java更快）
显然，我的下一步是将上面的代码翻译成Java，但是Java无法处理它，并在22000标记附近抛出一个StackOverflowError。
然后我抓了一下头，用一个更多的尾recursionreplace了“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的尾recursion赢得了一天的胜利，但我很惊讶，像“for”循环（和“forall”方法）这样简单的事情基本上被打破了，必须被不雅和冗长的“whiles”或尾recursion。 我正在尝试Scala的很多原因是因为语法简洁，但是如果我的代码运行速度要慢100倍，那就不好了！
编辑 :(删除）
编辑编辑 ：2.5s和0.7s的运行时间之间的前差异完全是由于是否使用32位或64位JVM。 命令行中的Scala使用由JAVA_HOME设置的任何值，而Java使用64位（如果可用的话）。 IDE有自己的设置。 这里的一些测量： Eclipse中的Scala执行时间
关于理解的答案是对的，但并不是全部。 你应该注意到，使用return isEvenlyDivisible不是免费的。 使用for内部的return，强制scala编译器生成非本地返回（即返回它的函数外）。
这是通过使用exception退出循环完成的。 同样的情况发生，如果你build立自己的控制抽象，例如：
def loop[T](times: Int, default: T)(body: ()=>T) : T = { var count = 0 var result: T = default while(count < times) { result = body() count += 1 } result } def foo() : Int= { loop(5, 0) { println("Hi") return 5 } } foo()
这只打印“嗨”一次。
请注意， foo中的return退出foo （这是您所期望的）。 由于括号expression式是一个函数文字，在loop的签名中可以看到，这会强制编译器生成非本地返回，也就是说， return强制退出foo ，而不仅仅是body 。
在Java（即JVM）中，实现这种行为的唯一方法是抛出exception。
回到现在是isEvenlyDivisible ：
def isEvenlyDivisible(a:Int, b:Int):Boolean = { for (i <- 2 to b) if (a % i != 0) return false return true }
if (a % i != 0) return false是一个具有if (a % i != 0) return false值的函数，所以每次返回时，运行时必须抛出并捕获exception，这会导致相当多的GC开销。
加快我发现的所有方法的一些方法：
原文： 41.3秒
def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
预先实例化范围，所以我们不会每次创build一个新的范围： 9.0秒
val r = (1 to 20) def isDivis(x:Int) = r forall {x % _ == 0}
转换为列表而不是范围： 4.8秒
val rl = (1 to 20).toList def isDivis(x:Int) = rl forall {x % _ == 0}
我尝试了一些其他的collections，但列表是最快的（虽然仍然是7倍，如果我们完全避免范围和高阶函数）。
虽然我是Scala的新手，但我猜测编译器可以轻松实现快速且显着的性能增益，只需在最外层的范围内自动replace方法中的Range文本（如上）。 或者更好的是，像Java中的string文字一样实习它们。
脚注 ：数组大约与Range相同，但有趣的是，采用新的方法（如下所示）可以使64位执行速度提高24％，在32位执行速度提高8％。 当我通过减less20到15的因子数来减小计算大小时，差异消失了，所以也许是垃圾收集效应。 无论是什么原因，在满负荷下长时间工作是非常重要的。
列表类似的皮条客也导致约10％的更好的performance。
val ra = (1 to 20).toArray def isDivis(x:Int) = ra forall2 {x % _ == 0} case class PimpedSeq[A](s: IndexedSeq[A]) { def forall2 (p: A => Boolean): Boolean = { var i = 0 while (i < s.length) { if (!p(s(i))) return false i += 1 } true } } implicit def arrayToPimpedSeq[A](in: Array[A]): PimpedSeq[A] = PimpedSeq(in)
我只是想对那些可能对Scala失去信心的人发表评论，这些问题出现在所有函数式语言的performance中。 如果你在Haskell中优化折叠，你经常需要将它重写为一个recursion的tail-call优化循环，否则你将遇到性能和内存问题。
我知道不幸的是，FP还没有被优化到我们不需要考虑这样的事情，但是这对于Scala来说并不是一个特别的问题。
已经讨论过特定于Scala的问题，但主要的问题是使用暴力algorithm并不是很酷。 考虑一下（比原来的Java代码快得多）：
def gcd(a: Int, b: Int): Int = { if (a == 0) b else gcd(b % a, a) } print (1 to 20 reduce ((a, b) => { a / gcd(a, b) * b }))
尝试在解决schemeScala中为Project Euler提供的单线程
给出的时间至less比你的更快，尽pipe远离while循环.. 🙂
