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

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已将字符串切片优化为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变量不执行任何操作时，优化程序会将切片甚至整个循环作为死代码消除。如果您要进行基准测试，请在实际的实际数据上进行基准测试。