Codility DisappearingPairs问题两种O(n)解法性能差异及运行耗时差异的疑问

我最近解决了Codility上的DisappearingPairs训练任务，写了两种时间复杂度都是O(n)的解法，但奇怪的是第一种解法过不了性能测试，第二种却可以，我想弄清楚背后的原因。

两种解法实现 #

Solution 1 #

function solution(S) {
    const chars = [...S];
    let i = 1;

    while (i < chars.length) {
        while (i > 0 && i < chars.length && chars[i - 1] === chars[i]) {
            chars.splice(i - 1, 2);
            i--;
        }
        i++;
    }

    return chars.join('');
}

Solution 2 #

function solution(S) {
    const result = [];

    for (const ch of S) {
        const {length} = result;
        if (length === 0 || ch !== result[length - 1])  {
            result.push(ch);
        } else {
            result.splice(length - 1, 1);
        }
    }

    return result.join('');
}

性能测试与排查 #

为了找到第一种解法性能拉胯的原因，我在代码里加入了一个模拟官方性能测试的用例——生成一个长度为50000、全是字符'C'的字符串，同时添加计时代码追踪各个步骤的耗时：

function solution(S) {
    console.time('repeat')
    if (S === 'C') {
        S = S.repeat(50000);
    }
    console.timeEnd('repeat')
    // Implement your solution here
    console.time('restOperator')
    const chars = [...S];
    let i = 1;
    console.timeEnd('restOperator')

    console.time('while')
    while (i < chars.length) {
        while (i > 0 && i < chars.length && chars[i - 1] === chars[i]) {
            chars.splice(i - 1, 2);
            i--;
        }
        i++;
    }
    console.timeEnd('while')

    console.time('join')
    const result = chars.join('');
    console.timeEnd('join')
    return result;
}

运行后得到的耗时数据（每次运行有小幅波动）：

repeat: 0.066ms
restOperator: 1.564ms
while: 3.668s
join: 0.005ms

从结果能明显看到，while循环是绝对的耗时瓶颈。我进一步拆解测试了splice操作的耗时，发现它就是拖慢速度的核心，而且还发现一个诡异的现象：我创建了一个预先填充好的dummy数组（同样是50000个'C'），执行相同的splice操作时，dummy数组的splice速度居然比原数组快很多。

测试对比的代码片段：

const dummy = Array(50000).fill('C');
while (i < chars.length) {
        console.time('innerWhile');

        while (i > 0 && i < chars.length && chars[i - 1] === chars[i]) {
            console.time('splice');
            chars.splice(i - 1, 2);
            console.timeEnd('splice');
        
            console.time('spliceDummy');
            dummy.splice(i - 1, 2);
            console.timeEnd('spliceDummy');
            
            i--;
        }
        i++;

        console.timeEnd('innerWhile');
    }

截断的输出结果：

repeat: 0.066ms
restOperator: 0.391ms
splice: 0.417ms
spliceDummy: 0.012ms
innerWhile: 0.527ms
splice: 0.38ms
spliceDummy: 0.012ms
innerWhile: 0.47ms
splice: 0.386ms
spliceDummy: 0.012ms
innerWhile: 0.478ms
// 后续重复的耗时数据省略

另外还有一个让我困惑的点：我在本地浏览器控制台运行同样的代码，整个函数只花了大约65毫秒，但在Codility平台上却慢到离谱。

测试结果截图 #

通过的测试情况：

失败的性能测试情况：

我现在的核心疑问：

• 为什么第一种解法明明标注是O(n)时间复杂度，却过不了Codility的性能测试？
• 为什么相同的splice操作在dummy数组上的执行速度远快于原数组？
• 为什么本地浏览器和Codility平台的运行耗时差异会这么大？

备注：内容来源于stack exchange，提问作者aba