javascript - 字符串的 indexOf 方法如何在 JavaScript 中工作

Question

我在做一个关于 codility 的问题，遇到了 this problem为此我写了这样的东西:

function impact(s) {
    let imp = 4; // max possible impact
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'A') return 1;
        else if (s[i] === 'C') imp = Math.min(imp, 2);
        else if (s[i] === 'G') imp = Math.min(imp, 3);
        else if (s[i] === 'T') imp = Math.min(imp, 4);
    }
    return imp;
}

function solution(S, P, Q) {
    const A = new Array(P.length);
    for (let i = 0; i < P.length; i++) {
        const s = S.slice(P[i], Q[i] + 1);
        A[i] = impact(s);
    }
    return A;
}

和it failed all the performance tests

现在我将其更改为以下代码，我认为它会更慢但令我惊讶的是 it scored 100% :

function solution(S, P, Q) {
    let A = []
    for (let i = 0; i < P.length; i++) {
        let s = S.slice(P[i], Q[i] + 1)
        if (s.indexOf('A') > -1) A.push(1)
        else if (s.indexOf('C') > -1) A.push(2)
        else if (s.indexOf('G') > -1) A.push(3)
        else if (s.indexOf('T') > -1) A.push(4)
    }
    return A
}

这对我来说毫无意义，因为我使用了 4 个 indexOf，这应该比同一字符串的 1 个线性迭代慢。但事实并非如此。

那么，String.indexOf() 是如何工作的，为什么 4 个 .indexOf 比 1 个迭代快得多？

Answer 1

在您的第一个解决方案中，您有两个循环。第二个循环在 impact 中。第二个循环大致对应于第二个解决方案中的四个 indexOf。

第二个循环的一次迭代最多进行 4 次比较，并且最多有 n 次迭代。所以这最多进行 4n 次比较。 indexOf 解决方案也是如此。这四个 indexOf 中的每一个都可能需要扫描整个数组，这表示 n 次比较。因此，这也相当于 4n 比较的最坏情况。

然而，主要区别在于 indexOf 执行的扫描不是在 JavaScript 中实现的，而是在高效的预编译代码中实现的，而第一个解决方案使用(较慢)进行扫描JavaScript 代码。根据经验，使用原生字符串/数组方法总是更有效(例如 indexOf、slice、includes 等)。 ..) 而不是使用显式 for 循环实现类似的功能。

另一件需要考虑的事情是，如果在 i 位置的数据中有一个“A”，那么第二个解决方案将在 i 比较之后找到它(内部到indexOf 实现)，而第一个解决方案将在 4i 次比较后找到它，因为它也在寻找“A”的相同迭代。当某处没有“A”但有“C”等时，此额外成本会降低，等等。