CODEWITHSUNDEEP
javascriptalgorithmindexof
Sourabh
Sourabh

Reputation: 8482

How does indexOf method on string work in JavaScript

I was doing a question on codility and came across this problem for which I wrote something like this:

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;
}

And it failed all the performance tests

Now I changed it to the following code which I thought would be slower but to my surprise 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
}

Which to me made no sense, because I was using 4 indexOf which should be slower than 1 linear iteration of the same string. But it's not.

So, how does String.indexOf() work and why are 4 .indexOf so much faster than 1 iteration?

Upvotes: 1

Views: 145

Answers (1)

trincot
trincot

Reputation: 349956

In your first solution you have two loops. The second loop is in impact. That second loop corresponds roughly to the four indexOf you have in the second solution.

One iteration of the second loop will do at most 4 comparisons, and there will be at most n iterations. So this makes at most 4n comparisons. The same can be said of the indexOf solution. Each of these four indexOf may need to scan the whole array, which represents n comparisons. And so that also amounts to a worst case of 4n comparisons.

The main difference however, is that the scanning that an indexOf performs, is not implemented in JavaScript, but in highly efficient pre-compiled code, while the first solution does this scanning with (slower) JavaScript code. As a rule of thumb, it is always more efficient to use native String/Array methods (like there are indexOf, slice, includes,...) than implementing a similar functionality with an explicit for loop.

Another thing to consider is that if there is an "A" in the data at position i, then the second solution will find it after i comparisons (internal to the indexOf implementation), while the first solution will find it after 4i comparisons, because it also makes the comparisons for the other three letters during the same iterations in which it looks for an "A". This extra cost decreases for when there is no "A", but a "C" somewhere, ...etc.

Upvotes: 1

Related Questions