4

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;
}
Community
  • 1
  • 1
Vitim.us
  • 20,746
  • 15
  • 92
  • 109

4 Answers4

4

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.

meetamit
  • 24,727
  • 9
  • 57
  • 68
  • you are correct about the `i>=0` but not about the undefined, because I was just not going till the beginnig of the string and not checking the character at position 0. Thanks but this is not the cause of the bottleneck. – Vitim.us Jun 07 '12 at 08:02
  • I found the issue, so I answered myself. – Vitim.us Jun 07 '12 at 08:24
2

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.

Community
  • 1
  • 1
Vitim.us
  • 20,746
  • 15
  • 92
  • 109
0

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. ?

Markus Mikkolainen
  • 3,397
  • 18
  • 21
  • both functions are using the same input, but your example doesn't make sense to me. You will always get only one match on `aaabbaaa` to `aab` no matter what. – Vitim.us Jun 07 '12 at 08:09
  • yes you should but it seems to me that the first code will not find a match for aab in aaabbaaa. – Markus Mikkolainen Jun 07 '12 at 08:19
  • it will go: Aaabbaaa AAabbaaa AAAbbaaa (FAIL) then continue matching aaaBbaaa to Aab (FAIL) and will not match. – Markus Mikkolainen Jun 07 '12 at 08:22
  • i would study regular expression matchers and finite state machines. ;) Generating a simple DFA is often the fastest way to match stuff, especially if you can compile it straight to bytecode which gets jitted. – Markus Mikkolainen Jun 07 '12 at 10:13
  • that new one will probably work, but i am not sure if it is faster than a proper DFA or NFA for cases where you have long false matches. – Markus Mikkolainen Jun 07 '12 at 10:16
  • I'm sure it is slower than Regex solution, would be a lot faster in C, but due to Javascript nature native functions will always be faster. the bottleneck is probably the string comparison `==`but thats not the point of the question, it was just for studying purposes not for real application. Thank you anyway ;D – Vitim.us Jun 07 '12 at 18:36
0

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.

ajax333221
  • 11,436
  • 16
  • 61
  • 95