Adr*_*ian 54 performance scala
我觉得Scala社区对编写"简洁","酷","scala惯用","单行" - 如果可能的代码有一点点的痴迷.接下来是对Java /命令/丑陋代码的比较.
虽然这(有时)导致易于理解的代码,但它也导致99%的开发人员的代码效率低下.这就是Java/C++不容易被击败的地方.
考虑这个简单的问题:给定一个整数列表,删除最大的元素.订购不需要保留.
这是我的解决方案版本(它可能不是最好的,但它是普通的非摇滚明星开发者会做的).
def removeMaxCool(xs: List[Int]) = {
val maxIndex = xs.indexOf(xs.max);
xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}
这是Scala惯用,简洁,并使用一些很好的列表功能.这也是非常低效的.它遍历列表至少3或4次.
这是我完全不那么类似Java的解决方案.这也是一个合理的Java开发人员(或Scala新手)会写的.
def removeMaxFast(xs: List[Int]) = {
var res = ArrayBuffer[Int]()
var max = xs.head
var first = true;
for (x <- xs) {
if (first) {
first = false;
} else {
if (x > max) {
res.append(max)
max = x
} else {
res.append(x)
}
}
}
res.toList
}
完全非Scala惯用,非功能性,非简洁,但它非常有效.它只遍历列表一次!
因此,如果99%的Java开发人员编写的代码比99%的Scala开发人员更有效,那么这对于更好的Scala采用来说是一个巨大的障碍.有没有办法摆脱这个陷阱？
我正在寻找实用的建议,以避免这种"效率低下的陷阱",同时保持实施清晰简洁.
澄清:这个问题来自现实生活场景:我必须编写一个复杂的算法.首先我在Scala中编写它,然后我"必须"用Java重写它.Java实现的时间是原来的两倍,并不是很清楚,但同时它的速度是原来的两倍.重写Scala代码以提高效率可能需要一些时间并且对scala内部效率有更深入的理解(对于映射与折叠等)
Dan*_*ral 93
让我们讨论一下这个问题的谬误:
因此,如果99%的Java开发人员编写的代码比99%的Scala开发人员更有效,那么这对于更好的Scala采用来说是一个巨大的障碍.有没有办法摆脱这个陷阱？
这是假定的,绝对没有证据支持它.如果不对,这个问题没有实际意义.
有相反的证据吗？好吧,让我们考虑问题本身 - 它没有证明什么,但表明事情并不那么清楚.
完全非Scala惯用,非功能性,非简洁,但它非常有效.它只遍历列表一次!
在第一句中的四个声明中,前三个是真的,而第四个,如用户未知所示,是错误的!为什么它是假的？因为,与第二句所述相反,它不止一次地遍历列表.
代码调用以下方法:
res.append(max)
res.append(x)
和
res.toList
我们先考虑一下append.
append采用vararg参数.这意味着max与x被第一封装到某种类型的序列(一个WrappedArray,实际上),然后作为参数传递.一种更好的方法+=.
好的,代表的append电话.但是,首先,它调用,这是第二个错误(调用也是 - 只是为多个元素优化).因为a 是固定大小的集合,这意味着,在每次调整大小时,必须复制整个!++=+=ensureSize+=++=ArrayArray
所以让我们考虑一下.调整大小时,Java首先通过在每个元素中存储0来清除内存,然后Scala将前一个数组的每个元素复制到新数组.由于每次大小翻倍,这会发生log(n)次,每次发生时复制的元素数量都会增加.
例如,n = 16.它执行此操作四次,分别复制1,2,4和8个元素.由于Java必须清除这些数组中的每一个,并且必须读取和写入每个元素,因此复制的每个元素表示元素的4次遍历.添加所有我们有(n - 1)*4,或大致4个完整列表的遍历.如果你把读写算作一次通过,就像人们经常做错一样,那么它仍然是三次遍历.
通过初始化ArrayBuffer初始大小等于将要读取的列表减去1,可以改进这一点,因为我们将丢弃一个元素.为了获得这个大小,我们需要遍历列表一次.
现在让我们考虑一下toList.简而言之,它遍历整个列表以创建新列表.
因此,我们有1次遍历算法,3次或4次遍历调整大小,1次额外遍历toList.这是4或5次遍历.
原算法是有点难以分析,因为take,drop和:::遍历可变数目的元素.然而,将它们全部加在一起,它相当于3次遍历.如果splitAt使用,它将减少到2次遍历.通过另外两次遍历来获得最大值,我们得到5次遍历 - 与非功能性,非简洁算法相同的数量!
所以,让我们考虑改进.
在命令式算法中,如果使用ListBuffer和+=,则所有方法都是常量时间,这会将其减少为单次遍历.
在功能算法上,它可以重写为:
val max = xs.max
val (before, _ :: after) = xs span (max !=)
before ::: after
这减少了三次遍历的最坏情况.当然,还有其他基于递归或折叠的替代方案,可以在一次遍历中解决它.
并且,最有趣的是,所有这些算法都是O(n),并且在最复杂的情况下几乎(偶然)发生的唯一算法是必需的(由于阵列复制).另一方面,命令式缓存的缓存特性可能会使其更快,因为数据在内存中是连续的.然而,这与大哦或功能与命令无关,而且只是所选数据结构的问题.
因此,如果我们实际上遇到基准测试,分析结果,考虑方法的性能以及寻找优化方法的麻烦,那么我们可以找到更快的方式来执行此操作,而不是以功能方式.
但是所有这些努力与说普通的Java程序员代码将比普通的Scala程序员代码更快有很大的不同 - 如果问题是一个例子,那就是假的.甚至打折这个问题,我们也没有看到证据证明这个问题的基本前提是正确的.
编辑
首先,让我重申一下我的观点,因为我似乎并不清楚.我的观点是普通Java程序员编写的代码似乎更有效,但实际上并非如此.或者换句话说,传统的Java风格并没有为您带来性能 - 只有艰苦的工作才能实现,无论是Java还是Scala.
接下来,我有一个基准测试和结果,包括几乎所有建议的解决方案.关于它的两个有趣的观点:
根据列表大小,对象的创建可能比列表的多次遍历产生更大的影响.Adrian的原始功能代码利用了列表是持久数据结构这一事实,即根本不复制最大元素的元素.如果使用a Vector代替,左右两侧将基本保持不变,这可能会导致更好的性能.
尽管用户未知和范例具有类似的递归解决方案,但范式更快.原因是他避免了模式匹配.模式匹配可能非常慢.
use*_*own 25
def removeOneMax (xs: List [Int]) : List [Int] = xs match {
case x :: Nil => Nil
case a :: b :: xs => if (a < b) a :: removeOneMax (b :: xs) else b :: removeOneMax (a :: xs)
case Nil => Nil
}
这是一个递归方法,只迭代一次.如果你需要表现,你必须考虑它,如果不是,不是.
您可以使用标准方式对其进行尾递归:给出一个额外的参数carry,默认情况下为空List,并在迭代时收集结果.那当然是有点长,但如果你需要表现,你必须付钱:
import annotation.tailrec
@tailrec
def removeOneMax (xs: List [Int], carry: List [Int] = List.empty) : List [Int] = xs match {
case a :: b :: xs => if (a < b) removeOneMax (b :: xs, a :: carry) else removeOneMax (a :: xs, b :: carry)
case x :: Nil => carry
case Nil => Nil
}
我不知道机会是什么,后来的编译器会改进较慢的map调用,就像while循环一样快.但是:您很少需要高速解决方案,但如果您经常需要它们,您将快速学习它们.
您知道您的收藏有多大,在您的机器上使用一秒钟的解决方案吗？
作为oneliner,类似于Daniel C. Sobrals解决方案:
((Nil : List[Int], xs(0)) /: xs.tail) ((p, x)=> if (p._2 > x) (x :: p._1, p._2) else ((p._2 :: p._1), x))._1
但这很难读,我没有衡量有效表现.正常模式是(x /:xs)((a,b)=>/*某事*/).这里,x和a是List-so-far和max-so-far的对,它解决了将所有内容整合到一行代码中的问题,但不是很易读.但是,您可以通过这种方式获得CodeGolf的声誉,也许有人喜欢进行性能测量.
一个更新的计时方法,用于获取垃圾收集,并使热点编译器预热,一个主要的,以及来自此线程的许多方法,一起在一个名为的Object中
object PerfRemMax {
def timed (name: String, xs: List [Int]) (f: List [Int] => List [Int]) = {
val a = System.currentTimeMillis
val res = f (xs)
val z = System.currentTimeMillis
val delta = z-a
println (name + ": " + (delta / 1000.0))
res
}
def main (args: Array [String]) : Unit = {
val n = args(0).toInt
val funs : List [(String, List[Int] => List[Int])] = List (
"indexOf/take-drop" -> adrian1 _,
"arraybuf" -> adrian2 _, /* out of memory */
"paradigmatic1" -> pm1 _, /**/
"paradigmatic2" -> pm2 _,
// "match" -> uu1 _, /*oom*/
"tailrec match" -> uu2 _,
"foldLeft" -> uu3 _,
"buf-=buf.max" -> soc1 _,
"for/yield" -> soc2 _,
"splitAt" -> daniel1,
"ListBuffer" -> daniel2
)
val r = util.Random
val xs = (for (x <- 1 to n) yield r.nextInt (n)).toList
// With 1 Mio. as param, it starts with 100 000, 200k, 300k, ... 1Mio. cases.
// a) warmup
// b) look, where the process gets linear to size
funs.foreach (f => {
(1 to 10) foreach (i => {
timed (f._1, xs.take (n/10 * i)) (f._2)
compat.Platform.collectGarbage
});
println ()
})
}
我重命名了所有方法,并且必须稍微修改uu2,以适应公共方法声明(List [Int] => List [Int]).
从长期结果来看,我只提供1M调用的输出:
scala -Dserver PerfRemMax 2000000
indexOf/take-drop: 0.882
arraybuf: 1.681
paradigmatic1: 0.55
paradigmatic2: 1.13
tailrec match: 0.812
foldLeft: 1.054
buf-=buf.max: 1.185
for/yield: 0.725
splitAt: 1.127
ListBuffer: 0.61
这些数字不是完全稳定的,具体取决于样本大小,并且随着运行的不同而有所不同.例如,对于100k到1M的运行,以100k为步长,splitAt的时间如下:
splitAt: 0.109
splitAt: 0.118
splitAt: 0.129
splitAt: 0.139
splitAt: 0.157
splitAt: 0.166
splitAt: 0.749
splitAt: 0.752
splitAt: 1.444
splitAt: 1.127
最初的解决方案已经非常快了.splitAt是Daniel的修改,通常更快,但并非总是如此.
测量是在单核2Ghz Centrino上进行的,运行xUbuntu Linux,Scala-2.8和Sun-Java-1.6(桌面).
给我的两个教训是:
par*_*tic 23
首先,您提出的方法的行为是不一样的.第一个保持元素排序,而第二个保持元素排序.
其次,在所有可能被称为"惯用"的解决方案中,有些解决方案比其他解决方案更有效.与示例非常接近,您可以使用尾递归来消除变量和手动状态管理:
def removeMax1( xs: List[Int] ) = {
def rec( max: Int, rest: List[Int], result: List[Int]): List[Int] = {
if( rest.isEmpty ) result
else if( rest.head > max ) rec( rest.head, rest.tail, max :: result)
else rec( max, rest.tail, rest.head :: result )
}
rec( xs.head, xs.tail, List() )
}
或折叠列表:
def removeMax2( xs: List[Int] ) = {
val result = xs.tail.foldLeft( xs.head -> List[Int]() ) {
(acc,x) =>
val (max,res) = acc
if( x > max ) x -> ( max :: res )
else max -> ( x :: res )
}
result._2
}
如果你想保留原始的插入顺序,你可以(以两次通过为代价,而不是一次)不费力地写下这样的东西:
def removeMax3( xs: List[Int] ) = {
val max = xs.max
xs.filterNot( _ == max )
}
这比你的第一个例子更清楚.
Chu*_*uck 18
编写程序时最大的低效率是担心错误的事情.这通常是担心的错误.为什么？
开发人员的时间通常比CPU时间贵得多 - 事实上,前者通常缺乏,后者有剩余.
大多数代码不需要非常高效,因为它永远不会每秒多次在百万项数据集上运行.
大多数代码确实需要免费提供,而较少的代码可以减少隐藏错误的空间.
Dan*_*ral 10
实际上,你给出的例子不是很实用.这是你在做什么:
// Given a list of Int
def removeMaxCool(xs: List[Int]): List[Int] = {
// Find the index of the biggest Int
val maxIndex = xs.indexOf(xs.max);
// Then take the ints before and after it, and then concatenate then
xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}
请注意,它并不坏,但是当你描述你想要的东西时,你知道功能代码何时处于最佳状态,而不是你想要它.作为未成年人的批评,如果你使用splitAt的,而不是take和drop你可以稍微改善它.
另一种方法是:
def removeMaxCool(xs: List[Int]): List[Int] = {
// the result is the folding of the tail over the head
// and an empty list
xs.tail.foldLeft(xs.head -> List[Int]()) {
// Where the accumulated list is increased by the
// lesser of the current element and the accumulated
// element, and the accumulated element is the maximum between them
case ((max, ys), x) =>
if (x > max) (x, max :: ys)
else (max, x :: ys)
// and of which we return only the accumulated list
}._2
}
现在,让我们讨论一下主要问题.这段代码比Java小吗？当然!Java代码是否比C等效代码慢？你可以打赌,JIT或没有JIT.如果你直接在汇编程序中编写它,你可以让它更快!
但是这种速度的代价是你得到了更多的错误,你花了更多的时间来理解代码来调试它,而你对整个程序正在做的事情的了解程度较低,而不是一小段代码正在做什么 - - 这可能会导致其自身的性能问题.
所以我的回答很简单:如果你认为Scala编程的速度损失不值得它带来的收益,你应该用汇编程序编程.如果你认为我是激进的,那么我反驳你只是选择了熟悉的"理想"权衡.
我认为表现无关紧要吗？一点也不!我认为Scala的主要优点之一是利用静态类型语言的性能来利用动态类型语言中经常出现的增益!性能很重要,算法复杂性很重要,而且固定成本也很重要.
但是,只要在性能和可读性与可维护性之间做出选择,后者就更为可取.当然,如果必须提高性能,那么就没有选择:你必须牺牲一些东西.如果可读性/可维护性没有丢失 - 例如Scala与动态类型语言 - 确定,那就去追求性能.
最后,要从功能编程中获得性能,您必须了解功能算法和数据结构.当然,99%的具有5到10年经验的Java程序员将在具有6个月经验的情况下击败99%的Scala程序员.几十年前,命令式编程与面向对象编程的情况也是如此,历史表明它并不重要.
编辑
作为旁注,你的"快速"算法遇到了严重的问题:你使用ArrayBuffer.该集合没有恒定的时间附加,并且具有线性时间toList.如果您使用的ListBuffer不是,你会得到一定的时间追加和 toList.
作为参考,这里是如何在Scala标准库splitAt中的TraversableLike中定义的,
def splitAt(n: Int): (Repr, Repr) = {
val l, r = newBuilder
l.sizeHintBounded(n, this)
if (n >= 0) r.sizeHint(this, -n)
var i = 0
for (x <- this) {
(if (i < n) l else r) += x
i += 1
}
(l.result, r.result)
}
它与Java程序员可能提出的示例代码没有什么不同.
我喜欢Scala,因为在性能很重要的地方,可变性是一种合理的方式.馆藏图书馆是一个很好的例子; 特别是它如何隐藏功能界面背后的这种可变性.
在性能不那么重要的地方,例如某些应用程序代码,Scala库中的高阶函数可以提供出色的表达能力和程序员效率.
出于好奇,我在Scala编译器中选择了一个任意大文件(scala.tools.nsc.typechecker.Typers.scala)并计算了类似37 for循环,11 while循环,6个concatenations(++)和1折(它发生了)成为a foldRight).