CODEWITHSUNDEEP
javascriptperformanceloops
Vitim.us
Vitim.us

Reputation: 22128

Why this loop backwards is much slower than going forward?

I have a answer to another guy question here How to count string occurrence in string? So I was playing with algorithms here, and after benchmarking some functions I was wondering why a backwards loop was significantly slower than forward.

graph

Benchmark test here

NOTE: This code below does not work as supposed to be, there are others that work (thats not the point of this question), be aware before Copying>Pasting it

Forward

function occurrences(string, substring) {

  var n = 0;
  var c = 0;
  var l = substring.length;

  for (var i = 0, len = string.length; i < len; i++) {

    if (string.charAt(i) == substring.charAt(c)) {
      c++;
    } else {
      c = 0;
    }

    if (c == l) {
      c = 0;
      n++;
    }
  }
  return n;
}

Backwards

function occurrences(string, substring) {

  var n = 0;
  var l = substring.length - 1;
  var c = l;

  for (i = string.length; i > 1; i--) {

    if (string.charAt(i) == substring.charAt(c)) {
      c--;
    } else {
      c = l;
    }

    if (c < 0) {
      c = l;
      n++;
    }
  }
  return n;
}

Upvotes: 4

Views: 367

Answers (4)

Vitim.us
Vitim.us

Reputation: 22128

I found the bottle-neck myself.

when I did this

for (i = string.length; i > 1; i--) {

I accidentaly deleted the "var" from var i, so I've made i global. After fixing it I got the expected results.

for (var i = string.length; i > 1; i--) {

I never though that this may be a HUGE difference, so pay attention guys.

Fixed Benckmark test here

Before:

Before

After:

After

PS: for practical use, do NOT use this functions, the indexOf version is much faster.

Upvotes: 2

ajax333221
ajax333221

Reputation: 11764

Because they are not complete mirrored functions, add console.log()s inside all ifs and elses of both functions and compare the results, you will see that the tests aren't fair.

You did something wrong. I suggest to ensure that they both work as expected before even start the testings.

Upvotes: 0

Markus Mikkolainen
Markus Mikkolainen

Reputation: 3497

What data are you testing with. If your data has lots of matching prefixes but not many false matches the other way round , that might affect it.

also wont that search bug on cases like "aaabbaaa" try to find "aab" it will match aa, then fail , then continue from third a and fail. ?

Upvotes: 0

meetamit
meetamit

Reputation: 25157

I think the backwards test has a bug:

for (i = string.length; i > 1; i--) {

should be

for (i = string.length - 1; i >= 0; i--) {

When i is string.length, string.charAt(i) is undefined. Do this several thousand times, and it could yield a substantial difference.

Here's a modified test that seems to yield much closer to identical performances.

Upvotes: 4

Related Questions