Left-Pad 的算法复杂度

如果您是一名程序员，那么您很有可能会注意到几周前的 node.js 左板惨败，它暂时破坏了大部分 npm 生态系统。本博客对此没有任何意见。然而，在随后的混乱中，有几个人观察到左垫看起来是二次的，这绝对是这个博客的关注点。如果我们查看代码，我们会看到主循环如下所示： 在大多数语言的字符串实现中，这肯定是二次的——+ 在每次迭代时复制整个字符串（大小为 O(len)），并且此循环运行 O (len) 次。然而，我碰巧知道现代 JS 实现有一整套复杂的字符串优化，包括类似绳索的数据结构。这是一个循证驱动的博客，所以我决定深入研究。我发现的东西既迷人又奇怪，老实说还无法解释。但让我们从简单的事情开始。我在 rhino 中运行了一个基准测试，我认为它是 javascript 实现，我可以轻松访问最不可能拥有超级高级字符串优化的 javascript 实现。我们可以清楚地看到明显的二次曲线：但是现在让我们尝试一些更复杂的东西，它也恰好是我的主要浏览器：Chrome。在 Chrome 中运行 left-pad 基准测试会产生以下结果：

有一些异常行为，尤其是在小尺寸的情况下，但它为通过我运行测试的 1MB 限制线性输出提供了一个令人信服的理由！ （我正在运行 Chrome 版本 50.0.2661.57 beta（64 位）；您的结果可能因 Chrome 版本而异！）事实上，Chrome 开发人员工具将让我们看到 Chrome 用来使这些连接高效的绳索结构！如果我们在 Chrome 控制台中使用 leftpad('hi', 100000, 'x') 然后进行堆快照，我们可以看到该字符串是一个“连接字符串”，由大量链接在一起的块组成：（缺点从该屏幕截图中还可以看出，此优化的最大优势在于我们的 100kb 字符串现在消耗了 4MB 的 RAM……）继续，我们还可以尝试 Safari，这是另一种具有令人难以置信的复杂 Javascript 引擎的现代浏览器。在 Safari 中，我们看到了这种奇怪的行为：有点难以确定，但数据似乎符合两个线性拟合，在 350k 左右有一个切入点。这种模式可以在多次实验中重现，但我没有解释。我还决定尝试使用 node，因为这毕竟是 NPM 主要针对的实际运行时。 node 运行与 Chrome 相同的 v8 引擎，因此我们预计会有类似的行为，但版本偏差、配置或谁知道可能导致分歧的原因。事实上，我们看到：

在这一点上，我已经没有精力做短文了，但是如果有人可以跟进并解释正在发生的事情，我会非常好奇。事实证明，这次冒险是我在此博客中经常阐述的原则的另一个出色演示：Quadraticbehavior（或者，在这种情况下，缺乏！）通常会导致在不同抽象层运行的代码段之间的复杂交互。在这种情况下，远距离动作拯救了我们：现代 Javascript 虚拟机在其复杂性中能够将看起来非常二次的代码优化为线性链表！但原则仍然存在，如果我们不深入了解我们关心的特定底层 Javascript VM，我们实际上完全不可能分析 left-pad 的性能（或者，在我的情况下，诉诸蛮力实验！）。