斯卡拉惯用编码风格只是编写低效代码的一个很酷的陷阱？
我感觉到，Scala社区对编写“简洁”，“酷”， “scala惯用” ，“单行”（如果可能）代码有一点点痴迷。 紧接着是Java /命令/丑陋代码的比较。
虽然这（有时）导致易于理解的代码，但也导致99％的开发人员的代码效率低下。 而这正是Java / C ++不容易被击败的地方。
考虑这个简单的问题： 给定一个整数列表，删除最大的元素。 订购不需要保存。
这是我的解决scheme版本（这可能不是最好的，但这是普通的非Rockstar开发人员所能做的）。
def removeMaxCool(xs: List[Int]) = { val maxIndex = xs.indexOf(xs.max); xs.take(maxIndex) ::: xs.drop(maxIndex+1) } 这是斯卡拉惯用，简洁，并使用一些不错的列表function。 这也是非常低效的。 它至less遍历三四次。
这是我完全不酷，类似Java的解决scheme。 这也是一个合理的Java开发人员（或斯卡拉新手）会写。
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惯用，非function，非简明，但它是非常有效的。 它只经历一次列表！
因此，如果99％的Java开发人员编写的代码效率比99％的Scala开发人员高，那么跨平台争夺更大的Scala是一个巨大的障碍。 有没有办法摆脱这个陷阱？
我正在寻求实际的build议，以避免这种“低效率的陷阱”，同时保持执行清晰和简洁。
澄清：这个问题来自一个真实的场景：我不得不写一个复杂的algorithm。 首先我写在Scala中，然后我“不得不”用Java重写它。 Java的实现是两倍的时间，并不那么清楚，但同时它是两倍的速度。 重写Scala代码是有效的可能需要一些时间和对scala内部效率的更深入的理解（对于比较图和折叠等）
让我们来讨论这个问题的一个谬误：
因此，如果99％的Java开发人员编写的代码效率比99％的Scala开发人员高，那么跨平台争夺更大的Scala是一个巨大的障碍。 有没有办法摆脱这个陷阱？
这是推定，绝对没有证据支持它。 如果是假的，这个问题是没有意义的。
是否有证据相反？ 那么让我们来考虑这个问题本身 – 它没有任何证据，但是表明事情并不那么清楚。
完全非Scala惯用，非function，非简明，但它是非常有效的。 它只经历一次列表！
在第一句中的四个要求中，前三个是真实的，而第四个如用户未知所示是错误的！ 为什么它是假的？ 因为，与第二句话相反，它不止一次地遍历列表。
代码调用以下方法：
res.append(max) res.append(x)
和
res.toList
我们先考虑一下。
-
append需要一个可变参数。 这意味着max和x首先被封装成某种types的序列（实际上是一个WrappedArray），然后作为parameter passing。 更好的方法是+=。 -
好的，
append调用++=，代表+=。 但是，首先，它调用ensureSize，这是第二个错误（+=调用也是 –++=只是优化多个元素）。 因为Array是一个固定大小的集合，这意味着在每次resize时，必须复制整个Array！
所以我们来考虑一下 resize时，Java首先通过在每个元素中存储0来清除内存，然后Scala将前一个数组的每个元素复制到新数组中。 由于每次大小加倍，这就会发生log（n）次，每次发生的元素数量都会增加。
举例来说，n = 16。这是四次，分别复制1,2,4和8个元素。 由于Java必须清除每个数组，并且每个元素都必须被读写，所以复制的每个元素代表一个元素的遍历。 添加我们所有的（n – 1）* 4，或者粗略地，遍历整个列表的4次。 如果你把读写作为一个单独的过程，正如人们经常错误地做的那样，那么它仍然是三次遍历。
通过初始化ArrayBuffer ，初始大小等于将被读取的列表，可以减less一个，因为我们将放弃一个元素。 为了获得这个大小，我们需要遍历一次，虽然。
现在我们来考虑一下toList 。 简而言之，它遍历整个列表来创build一个新列表。
所以，我们有1遍历的algorithm，3或4遍历resize，和1额外的遍历toList 。 这是4或5遍历。
原始algorithm有点难以分析，因为take ， drop和遍历可变数量的元素。 所有加在一起，然而，它相当于3遍历。 如果使用splitAt ，则会减less到2个遍历。 再有2次遍历得到最大值，我们得到5次遍历 – 与非function性非简明algorithm的数量相同！
所以，我们来考虑改进。
在命令式algorithm中，如果使用ListBuffer和+= ，那么所有的方法都是恒定时间的，从而将其减less为单次遍历。
在函数algorithm上，它可以被重写为：
val max = xs.max val (before, _ :: after) = xs span (max !=) before ::: after
这减less了三次遍历的最坏情况。 当然，还有其他的select，基于recursion或折叠，在一个遍历中解决它。
而且，最有趣的是，所有这些algorithm都是O(n) ，并且在最坏的情况下几乎招致（偶然）的唯一一个algorithm是当务之急（因为数组复制）。 另一方面，由于数据在内存中是连续的，所以命令的高速caching特性可能会更快。 然而，这与大哦或functionvs命令无关，而只是数据结构的select问题。
所以，如果我们真的去做基准testing，分析结果，考虑方法的性能，寻找优化方法，那么我们可以find更快速的方式来做到这一点，而不是在function上。
但是所有的这些工作都与一般的Java程序员代码比普通的Scala程序员代码相比要快很多 – 如果这个问题只是一个例子，那简直是错误的。 甚至对这个问题打个折扣，我们也没有看到证据certificate问题的根本前提是真实的。
编辑
首先，让我重申一下我的观点，因为我似乎并不清楚。 我的观点是，一般的Java程序员写的代码似乎更有效率，但事实上并非如此。 换句话说，传统的Java风格并没有给你带来性能 – 只有努力工作，不pipe是Java还是Scala。
接下来，我有一个基准和结果，包括几乎所有的解决scheme。 关于它的两个有趣的观点：
-
根据列表大小，对象的创build可能比列表的多次遍历具有更大的影响。 Adrian最初的function代码利用了这样一个事实：列表是持久的数据结构， 根本不复制最大元素的权利。 如果使用
Vector则左右两边大部分不会改变，这可能会导致更好的性能。 -
尽pipe用户不知道和范例有相似的recursion解决scheme，范式的方式更快。 原因是他避免了模式匹配。 模式匹配可能真的很慢。
基准代码在这里 ，结果在这里 。
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 }
这是一个recursion方法，只能迭代一次。 如果你需要performance，你必须考虑，否则，不。
您可以使用标准方式进行尾recursion：给出一个额外的参数，默认情况下为空列表，并在迭代时收集结果。 那当然是更长一点，但是如果你需要performance，你必须付出代价：
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循环一样快。 但是：您很less需要高速解决scheme，但是如果您经常需要这些解决scheme，则可以快速学习。
你知道你的collections有多大，在你的机器上用一秒钟的时间解决你的问题？
作为oneliner，类似丹尼尔C. Sobrals解决scheme：
((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
但这很难读，我没有衡量有效的performance。 正常模式是（x /：xs）（（a，b）=> / * something * /）。 在这里，x和a是List-so-far和max-so-far的对，它们解决了将所有内容放在一行代码中的问题，但是不易读。 但是，您可以通过这种方式在CodeGolf上获得声望，也许有人喜欢做一个性能测量。
而现在我们大吃一惊，有一些测量：
一个更新的计时方法，让垃圾收集不受阻碍，热点编译器预热，一个主要的，从这个线程的许多方法，一起在一个对象
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 = za 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
最初的解决scheme已经很快了。 splitAt是Daniel的一个修改，通常更快，但并不总是。
测量是在单核2Ghz Centrino上完成的，运行xUbuntu Linux，Scala-2.8和Sun-Java-1.6（桌面）。
对我来说这两个教训是：
- 总是衡量你的performance改善; 如果你不是每天都这样做的话，估计是很难的
- 编写function代码不仅有趣，有时结果更快
这是一个链接到我的基准代码，如果有人感兴趣。
首先，你提出的方法的行为是不一样的。 第一个保留元素sorting，而第二个不sorting。
其次，在所有可以被认定为“惯用”的可能解决scheme中，有些解决scheme比其他解决scheme更有效率。 保持非常接近你的例子，你可以例如使用tail-recursion来消除variables和手动状态pipe理：
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 ) }
这比你的第一个例子更清楚。
编写程序时效率最低的是担心错误的事情。 这通常是错误的担心。 为什么？
-
开发人员的时间一般比CPU时间贵得多 – 事实上，前者通常是缺乏的，后者是过剩的。
-
大多数代码不需要非常高效，因为它绝不会每秒多次在百万个项目数据集上运行。
-
大多数代码确实需要bug，而且代码less的地方就没有什么可以隐藏的。
实际上，你给出的例子function不是很强大。 这是你在做什么：
// 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。 如果你直接用汇编写的话，你可以更快！
但是，这个速度的代价是你得到了更多的错误，你花更多的时间去理解代码来debugging它，而且你对整个程序的function的了解比较less， – 这可能会导致其自身的性能问题。
所以我的回答很简单：如果您认为Scala编程的速度损失不值得它带来的收益，那么您应该用汇编语言编程。 如果你认为我是激进的，那么我反驳说，你只是select熟悉的“理想”交易。
我认为业绩不重要吗？ 一点也不！ 我认为Scala的主要优点之一就是利用dynamictypes语言中常见的静态types语言的性能！ 性能很重要，algorithm的复杂性非常重要，而且不变的成本也很重要。
但是，只要在性能和可读性和可维护性之间做出select ，后者是可取的。 当然，如果performance必须得到改善，那么没有select：你必须牺牲一些东西。 而且，如果在可读性/可维护性方面没有丢失 – 比如Scala vsdynamictypes语言，那么确保性能。
最后，为了获得函数式编程的性能，您必须知道函数式algorithm和数据结构。 当然，具有5 – 10年经验的99％的Java程序员在6个月的工作经验中将胜过99％的Scala程序员。 几十年前的命令式编程和面向对象编程也是如此，历史表明它并不重要。
编辑
作为一个方面说明，你的“快速”algorithm遭受严重的问题：你使用ArrayBuffer 。 该集合没有恒定的时间追加，并且具有线性时间toList 。 如果使用ListBuffer ，则会得到常量时间append 和 toList 。
作为参考， splitAt是在Scala标准库中的TraversableLike中如何定义splitAt ，
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，因为在性能问题上，可变性是一个合理的方法。 藏书库就是一个很好的例子。 特别是它如何隐藏function性界面背后的这种可变性。
在性能不重要的地方，比如一些应用程序代码，Scala库中的高阶函数可以提供很高的performance力和程序员效率。
出于好奇，我在Scala编译器（ scala.tools.nsc.typechecker.Typers.scala ）中select了一个任意的大文件，并计算了37个循环，11个循环，6个连接（ ++ ）和1个折叠（它恰好是一个foldRight ）。
那这个呢？
def removeMax(xs: List[Int]) = { val buf = xs.toBuffer buf -= (buf.max) }
更难看，但更快：
def removeMax(xs: List[Int]) = { var max = xs.head for ( x <- xs.tail ) yield { if (x > max) { val result = max; max = x; result} else x } }
尝试这个：
(myList.foldLeft((List[Int](), None: Option[Int]))) { case ((_, None), x) => (List(), Some(x)) case ((Nil, Some(m), x) => (List(Math.min(x, m)), Some(Math.max(x, m)) case ((l, Some(m), x) => (Math.min(x, m) :: l, Some(Math.max(x, m)) })._1
地道的，function性的，只穿越一次。 也许有点神秘，如果你不习惯function编程习语。
我们试着解释一下这里发生的事情。 我会尽量简化，缺乏一些严谨。
fold是一个List[A] （也就是包含A类元素的列表）上的一个操作，它将采用初始状态s0: S （即typesS一个实例）和一个函数f: (S, A) => S （也就是从列表中取当前状态和一个元素，并给出下一个状态，即根据下一个元素更新状态的函数）。
然后操作将迭代列表中的元素，使用每个元素根据给定的函数更新状态。 在Java中，它将是这样的：
interface Function<T, R> { R apply(T t); } class Pair<A, B> { ... } <State> State fold(List<A> list, State s0, Function<Pair<A, State>, State> f) { State s = s0; for (A a: list) { s = f.apply(new Pair<A, State>(a, s)); } return s; }
例如，如果要添加List[Int]所有元素，则状态将是部分和，必须将其初始化为0，并且由函数生成的新状态只会将当前状态添加到正在处理的当前元素：
myList.fold(0)((partialSum, element) => partialSum + element)
尝试写一个折叠乘以一个列表的元素，然后再find极端值（最大值，最小值）。
现在，上面提出的折叠比较复杂一点，因为状态是由创build的新列表以及迄今为止发现的最大元素组成的。 一旦你掌握了这些概念，那么更新状态的function或多或less是简单的。 它只是将当前最大值和当前元素之间的最小值放到新列表中，而另一个值则更新到当前最大值的更新状态。
比理解这一点（如果你没有FP背景）更复杂的是提出这个解决scheme。 但是，这只是向你展示它的存在，可以做到。 这只是一个完全不同的思维模式。
编辑：正如你所看到的，我build议的解决scheme中的第一个和第二个case用于设置折叠。 它相当于你在其他答案中看到的东西，当他们做xs.tail.fold((xs.head, ...)) {...} 。 请注意，直到现在使用xs.tail/xs.head提出的解决scheme不包括xs是List() ，并且会抛出一个exception。 上面的解决scheme将返回List() 。 由于您没有在空列表中指定函数的行为，两者都是有效的。
另一个竞争者。 这使用了一个ListBuffer，就像Daniel的第二个产品一样，但是共享原始列表的最大后尾，避免复制它。
def shareTail(xs: List[Int]): List[Int] = { var res = ListBuffer[Int]() var maxTail = xs var first = true; var x = xs while ( x != Nil ) { if (x.head > maxTail.head) { while (!(maxTail.head == x.head)) { res += maxTail.head maxTail = maxTail.tail } } x = x.tail } res.prependToList(maxTail.tail) }
