Warum ist diese Schleife rückwärts viel langsamer als vorwärts?

Question

Ich habe hier eine Antwort auf die Frage eines anderen Mannes Wie zählt man das Auftreten von Zeichenketten in einer Zeichenkette? Ich habe also mit Algorithmen gespielt aquí und nach dem Benchmarking einiger Funktionen habe ich mich gefragt, warum eine Rückwärtsschleife deutlich langsamer ist als eine Vorwärtsschleife.

Benchmark-Test hier

---

HINWEIS: Der unten stehende Code funktioniert nicht so, wie er sollte, es gibt andere, die funktionieren (das ist nicht der Punkt dieser Frage), bewusst sein bevor du ihn kopierst>einfügst

Weiterleiten

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

Rückwärts

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

Answer 1

Ich glaube, der Rückwärtstest hat einen Fehler:

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

sollte sein

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

Wenn i es string.length , string.charAt(i) ist undefiniert. Wenn Sie dies mehrere tausend Mal tun, könnte sich ein erheblicher Unterschied ergeben.

Hier ist ein modifizierter Test die sehr viel näher an identischen Leistungen zu liegen scheint.

Answer 2

Ich habe den Engpass selbst gefunden.

als ich dies tat

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

Ich habe versehentlich die "var" aus var i also habe ich i global. Nachdem ich das Problem behoben hatte, erhielt ich die erwarteten Ergebnisse.

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

Ich hätte nie gedacht, dass dies ein RIESIGER Unterschied sein kann, also aufgepasst, Leute.

Festgelegter Benckmark-Test hier

Vorher:

Danach:

PS: für den praktischen Gebrauch, verwenden Sie NICHT diese Funktionen, die indexOf Version ist viel schneller.

Answer 3

Da es sich nicht um vollständig gespiegelte Funktionen handelt, fügen Sie console.log() s innerhalb aller if s und else s der beiden Funktionen und vergleichen Sie die Ergebnisse, werden Sie sehen, dass die Tests nicht fair sind.

Sie haben etwas falsch gemacht. Ich schlage vor, dass Sie sicherstellen, dass beide wie erwartet funktionieren, bevor Sie mit den Tests beginnen.