javascript - 字符串切片的算法复杂度是多少？ (实用，真实世界)

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) .这当然在很大程度上取决于所有字符串发生的其他情况，它们可能需要稍后进行复制。

上述链接的相关实现是:

// 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 变量执行任何操作，因此切片甚至整个循环都可能被优化器作为死代码消除。如果您要进行基准测试，请根据实际的现实世界数据进行。