scala - Scala 惯用的编码风格只是编写低效代码的一个很酷的陷阱吗？

Question

我感觉 Scala 社区对写“简洁”、“酷”的东西有点痴迷， "scala 惯用语" , "one-liner"- 如果可能的话 - 代码。紧接着是与 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 内部效率的更深入理解(对于 vs. map vs. fold 等)

Answer 1

让我们讨论一下问题中的一个谬误:

So, if 99% of Java developers write more efficient code than 99% of Scala developers, this is a huge obstacle to cross for greater Scala adoption. Is there a way out of this trap?

这是假设，绝对没有证据支持。如果为假，则问题没有实际意义。

有相反的证据吗？好吧，让我们考虑一下问题本身——它不能证明任何事情，但表明事情并不那么清楚。

Totally non-Scala idiomatic, non-functional, non-concise, but it's very efficient. It traverses the list only once!

在第一句中的四个声明中，前三个是正确的，第四个是正确的，如 user unknown 所示。 ，是假的!为什么它是假的？因为，与第二句所述相反，它不止一次遍历列表。

代码对其调用以下方法:

res.append(max)
res.append(x)

和

res.toList

我们先考虑 append .

append采用可变参数。这意味着 max和 x首先封装成某种类型的序列(实际上是 WrappedArray )，然后作为参数传递。更好的方法是 += .

好的，append电话++= , 委托(delegate)给 += .但是，首先，它调用 ensureSize ，这是第二个错误( += 也调用了它——++= 只是针对多个元素优化了它)。因为一个 Array是一个固定大小的集合，这意味着在每次调整大小时，整个 Array必须复制!

所以让我们考虑一下。当您调整大小时，Java 首先通过在每个元素中存储 0 来清除内存，然后 Scala 将前一个数组的每个元素复制到新数组中。由于大小每次都翻倍，这会发生 log(n) 次，每次发生时复制的元素数量都会增加。

以 n = 16 为例。它这样做了四次，分别复制了 1、2、4 和 8 个元素。由于Java必须清除这些数组中的每一个，并且必须读取和写入每个元素，因此复制的每个元素代表对元素的4次遍历。将我们所有的 (n - 1) * 4 相加，或者粗略地说，完整列表的 4 次遍历。如果你把读写算作一次遍历，就像人们经常错误地做的那样，那么它仍然是三遍遍历。

可以通过初始化 ArrayBuffer 来改进这一点。初始大小等于将要读取的列表减去一，因为我们将丢弃一个元素。不过，为了获得这个大小，我们需要遍历列表一次。

现在让我们考虑 toList .简单来说，就是遍历整个链表来创建一个新链表。

因此，我们有 1 次算法遍历，3 或 4 次调整大小遍历，以及 toList 的 1 次额外遍历。 .那是 4 或 5 次遍历。

原算法有点难分析，因为 take , drop和 :::遍历可变数量的元素。然而，将所有这些加在一起，它相当于 3 次遍历。如 splitAt被使用，它将减少到 2 次遍历。再进行 2 次遍历以获得最大值，我们得到 5 次遍历——与非功能性、非简洁算法相同的数量!

所以，让我们考虑改进。

在命令式算法上，如果使用 ListBuffer和 += ，那么所有方法都是恒定时间的，这将其减少为一次遍历。

在函数算法上，它可以重写为:

val max = xs.max
val (before, _ :: after) = xs span (max !=)
before ::: after

这将它减少到三个遍历的最坏情况。当然，还有基于递归或折叠的其他替代方案，可以在一次遍历中解决它。

而且，最有趣的是，所有这些算法都是 O(n) ，而唯一一个几乎(意外地)导致最坏复杂性的是命令式的(因为数组复制)。另一方面，命令式的缓存特性可能会使其更快，因为数据在内存中是连续的。然而，这与 big-Oh 或函数式 vs 命令式无关，这只是选择的数据结构的问题。

因此，如果我们真的在进行基准测试、分析结果、考虑方法的性能并研究优化方法的过程中遇到麻烦，那么我们可以找到比函数式方式更快的方法来以命令式方式执行此操作。

但是所有这些努力与说普通 Java 程序员代码将比普通 Scala 程序员代码更快的说法大不相同——如果问题是一个例子，那完全是错误的。即使不考虑这个问题，我们也没有看到任何证据表明这个问题的基本前提是正确的。

编辑

首先，让我重申我的观点，因为我似乎不清楚。我的观点是，普通 Java 程序员编写的代码似乎更有效率，但实际上并非如此。或者，换句话说，传统的 Java 风格不会让您获得性能——只有努力工作才能做到，无论是 Java 还是 Scala。

接下来，我也有一个基准和结果，包括几乎所有建议的解决方案。关于它的两个有趣的点:

根据列表大小，对象的创建可能比列表的多次遍历产生更大的影响。 Adrian 的原始功能代码利用了列表是持久数据结构这一事实，根本不复制最大元素右侧的元素。如果 Vector取而代之，左右两边基本保持不变，这可能会带来更好的性能。

尽管用户未知和范式具有相似的递归解决方案，但范式的速度要快得多。原因是他避免了模式匹配。模式匹配可能真的很慢。

基准代码为 here ，结果为 here .