为什么你在浪费时间让你的代码变得 performant

Source: Dev.to

数据

// Note to really senior developers: I'm aware that Double is not an
// appropriate data type for prices, but I'm using it for the sake of simplicity.
case class Product(name: String, price: Double)

val products = List(
  Product("Apple",  50),
  Product("Banana", 21),
  Product("Orange", 70)
)

函数式版本

def applyDiscount(discount: Double)(product: Product) =
  product.price * (1 - discount)

def priceGreaterThan(limit: Double)(price: Double) =
  price > limit

def calculateTotalPrice(firstPrice: Double, secondPrice: Double) =
  firstPrice + secondPrice

val totalPrice = products
  .map(applyDiscount(0.1))          // apply 10 % discount
  .filter(priceGreaterThan(20))     // keep only prices > 20
  .reduce(calculateTotalPrice)      // sum the remaining prices

过程式版本

var totalPrice = 0.0
for product  20 then
    totalPrice += discountedPrice

原始辩论

原帖作者（忽略 Hic sunt dracones 注释）询问哪种写法更好，看起来更倾向于函数式版本，因为它的可读性和表达意图的风格更佳。

不出所料，讨论很快转向了 性能。一些资深开发者声称函数式代码的时间复杂度是 O(3 n)，而命令式代码是 O(n)。

注意： “O(3 n) 并不存在。就这么定了。”

他们的推理是：函数式管道会遍历集合三次（一次用于 map，一次用于 filter，一次用于 reduce），而命令式版本只循环一次。

为什么 “O(3 n)” 是一种误述

Big‑O 符号描述的是当输入规模 → ∞ 时的渐近增长。
所有线性函数——n/150、n、3 n、12 500 000 n——都是 Θ(n)，即它们属于同一复杂度类。在讨论 Big‑O 时，常数因子（3、12 500 000 等）会被忽略。

一个简单的性能模型

假设每个元素需要进行三次操作，耗时分别为 a、b 和 c。
对元素进行解引用的耗时为 d。

其中 ℓ = a + b + c。

两种运行时间的比值为

[ \frac{3d + ℓ}{d + ℓ} ]

只有当 ℓ = 0（即循环内部没有任何工作）时，三遍版本才会慢三倍。
如果循环内部的工作量是解引用成本的一个数量级（ℓ = 10 d），则比值为 13/11 ≈ 1.18 → 约 18 % 的性能下降，而不是 300 % 的下降。

可读性 vs. 性能

函数式版本中的柯里化函数通过清晰传达意图提升了可读性。
如果你更倾向于更简洁的函数式管道，可以将柯里化的辅助函数替换为匿名函数（或方法引用），并使用 sum 代替 reduce：

val totalPrice = products
  .map(_.price * 0.9)   // apply discount
  .filter(_ > 20)       // keep only prices > 20
  .sum                  // total

空间复杂度

使用朴素的函数式管道时，每个转换都会创建一个中间集合：

1. map → 大小为 n 的集合
2. filter → 大小 ≤ n 的集合
3. sum 消耗过滤后的集合

因此，朴素方法使用 O(n) 的额外空间（中间集合）。
在实际中，许多 Scala 集合（例如 view、Iterator）可以融合这些操作，避免生成中间集合，从而实现 O(1) 的额外空间。

结论

• 时间复杂度： 两个版本都是 Θ(n)。常数因子差异通常很小。
• 空间使用： 朴素的函数式管道会分配中间集合，但融合/流式版本消除了这些开销。
• 可读性： 函数式代码可以更具声明性和表达力，尤其是使用命名良好的辅助函数时。

这两种风格各有用武之地；请选择最符合项目性能约束和可读性目标的那一种。

Source: …

Scala 集合中的惰性求值

在任何情况下，除非我们进行某种嵌套转换，否则我们将得到一个空间随输入大小线性增长的解决方案，并且可以说会因管道中的步骤数量而进一步恶化。

一旦达到这一步，我只会在函数式代码中加入一次方法调用来最终解决问题：

val totalPrice = products.view
  .map(_.price * 0.9)
  .filter(_ > 20)
  .sum

你看到那个 .view 方法了吗？这就是 Scala 在集合中切换到 惰性求值 的方式，使用 Views。

与严格求值——所有转换都被立即应用，产生新结构——不同，惰性求值会把计算推迟到真正需要时才执行。

• map 和 filter 返回另一个 View（包装底层视图并记住计算值所需的闭包），而不 执行任何实际操作。
• 当我们最终调用 sum，它需要访问元素以产生输出时，真实的计算才会发生。

得益于惰性求值，我们只遍历原始输入一次，且不创建任何中间结构，使得这段函数式代码在效果上等同于我们在开头看到的单循环命令式代码。

权衡

惰性求值并非没有代价：

• 它会创建中间的 view 结构。
• 它会创建并存储中间闭包。

对于小规模输入，这些开销可能比简单地多次“循环”并创建中间集合更昂贵。

语言和评估策略

• Haskell – 默认惰性（非严格）。
• Scala – 默认严格，但提供机制（如 .view）来切换为惰性评估。

资历、代码长度与优化

正如我在本文开头所说，资历往往似乎是：

• 正比于你掌握的语言特性数量。
• 反比于你生成的代码长度。

它似乎也与您进行微观优化的能力有关——把 O(n) 的解法变成 O(3n)（再开玩笑了）。

在商业环境中真正重要的是什么？

有价值的开发者是能够 降低软件产品的总体拥有成本——也就是为公司省钱的人。

我们应该把精力放在哪里？

根据行业数据（引自 O’Reilly 的作者）：

• 60 % 的软件生命周期成本来自 维护。
• 在维护中，60 % 的成本与 用户生成的增强需求（需求变更）有关。
• 17 % 的维护成本源于 缺陷修复。

因此，维护成本远高于运营成本（运行软件所需的基础设施）。除非你是 Google——在那里性能提升会影响数百万台机器——否则你应该优先考虑：

1. 可维护性
2. 无缺陷的代码

这意味着 停止为微不足道的性能提升进行微观优化，而是专注于编写能够讲述美好故事的代码——让其他开发者以及未来的自己都愿意阅读和演进。函数式编程在这方面往往有优势，但那是另一个话题。

“永远把代码写成后面维护它的人会是一个知道你住址的暴力精神病患者。”
— Martin Golding（文中引用）