How does indexOf method on string work in JavaScript

Question

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?

You may want to look at this.

mrpandey
– mrpandey

2019-07-28 12:58:13 +00:00
Commented Jul 28, 2019 at 12:58 — mrpandey
– mrpandey, Commented Jul 28, 2019 at 12:58

trincot · Accepted Answer · 2019-07-28 13:07:15Z

1

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.

edited Jul 28, 2019 at 13:07

answered Jul 28, 2019 at 13:00

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sourabh Over a year ago

So what you are implying is that even after V8's optimizations, if a string has only Ts, 3 iterations in native code behind indexOf are faster than a single for loop iteration in JavaScript?

trincot Over a year ago

Well, if you would have four separate loops that completely mimic the indexOf operations, I guess it could be optimised a lot, but your first solution criss-crosses between four targets of the search, so it is not quite the same sequence of processing.

Collectives™ on Stack Overflow

How does indexOf method on string work in JavaScript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related