字符串切片的算法复杂度是多少？ （实用，真实世界）

Question

现代 v8 Javascript，String.prototype.slice 的算法复杂度是多少？

明确地说，我正在寻找真实世界的实用数据或经验法则。

快速测试

我试图通过 运行最近 Chrome 中的两个快速测试来获得粗略估计。测试 1 将长度为 N 的字符串切成两半。测试 2 对字符串中的每个索引长度 N 的字符串进行切片（因此 N 次）。令人困惑的是，两者都 运行 在 O(N) 时间内。怎么回事？

测试 1

let input = '';
let string = ' '.repeat(20000000);
for (let i = 0; i < 50; i++) {
    input += string;
    console.time(i);
    const y = input.slice(i / 2);
    console.timeEnd(i);
}

测试 2

let input = '';
let string = ' '.repeat(20000000);
for (let i = 0; i < 50; i++) {
    input += string;
    console.time(i);
    for (let j = 0; j < i; j++) {
        const y = input.slice(j);
    }
    console.timeEnd(i);
}

Chrome 版本：Chrome 版本 63.0.3239.84（正式版）（64 位）

Answer 1

是的，V8 有 optimised string slicing to O(1)。这当然在很大程度上取决于所有字符串发生的其他情况，它们可能需要稍后复制。

上述link的相关实现是：

// The Sliced String class describes strings that are substrings of another
// sequential string.  The motivation is to save time and memory when creating
// a substring.  A Sliced String is described as a pointer to the parent,
// the offset from the start of the parent string and the length.  Using
// a Sliced String therefore requires unpacking of the parent string and
// adding the offset to the start address.  A substring of a Sliced String
// are not nested since the double indirection is simplified when creating
// such a substring.
// Currently missing features are:
//  - handling externalized parent strings
//  - external strings as parent
//  - truncating sliced string to enable otherwise unneeded parent to be GC'ed.
class SlicedString: public String {
  // ...
};

---

还要注意您的快速测试结果。由于您未对 y 变量执行任何操作，因此切片甚至整个循环都可能被优化器作为死代码消除。如果您正在做基准测试，请在实际的真实世界数据上进行。