4

ここに別の男の質問への回答があります文字列内の文字列の出現をカウントする方法は? だから私はここ でアルゴリズムをいじっていました.いくつかの関数をベンチマークした後、なぜ後方ループが前方ループよりもかなり遅いのか疑問に思っていました.

グラフ

ベンチマークテストはこちら

注：以下のこのコードは想定どおりに機能しません。他にも機能するものがあります（それはこの質問のポイントではありません）。コピー>貼り付けする前に注意してください

前方

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

後方へ

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

4 に答える 4

4

後方テストにはバグがあると思います。

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

する必要があります

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

の場合、iは未定義です。これを数千回行うと、かなりの違いが生じる可能性があります。string.lengthstring.charAt(i)

これは、同じパフォーマンスにはるかに近いように見える修正されたテストです。

于 2012-06-06T22:08:27.270 に答える
2

ボトルネックは自分で見つけました。

私がこれをしたとき

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

から誤って「var」を削除してvar iしまったので、iグローバルにしました。それを修正した後、期待どおりの結果が得られました。

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

これが大きな違いになるとは思っていなかったので、注意してください。

ここでベンチマークテストを修正

前：

前

後：

後

PS: 実際に使用する場合は、この関数を使用しないでください。indexOfバージョンの方がはるかに高速です。

于 2012-06-07T08:22:43.473 に答える
0

どのデータでテストしていますか。データに一致するプレフィックスがたくさんあるが、逆に一致するfalseがあまりない場合は、データに影響を与える可能性があります。

また、「aaabbaaa」のような場合の検索バグは、「aab」を見つけようとして、aaに一致し、失敗し、3番目のaから続行して失敗します。？

于 2012-06-06T22:09:36.913 に答える
0

これらは完全なミラー関数ではないため、両方の関数のconsole.log()すべてifの および内に を追加elseして結果を比較すると、テストが公平ではないことがわかります。

あなたは何か間違ったことをしました。テストを開始する前に、両方が期待どおりに機能することを確認することをお勧めします。

于 2012-06-06T23:15:09.150 に答える