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” var i，所以我把它变成了i全局的。修复它后，我得到了预期的结果。

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

我从来没有想过这可能是一个巨大的差异，所以要注意伙计们。

在此处修复基准测试

前：

前

后：

后

PS：为了实际使用，不要使用这个函数，indexOf版本要快得多。

于 2012-06-07T08:22:43.473 回答
0

你在测试什么数据。如果您的数据有很多匹配的前缀，但反过来却没有很多错误匹配，那可能会影响它。

也不会像“aaabbaaa”这样的搜索错误尝试找到“aab”它将匹配aa，然后失败，然后从第三个a继续并失败。?

于 2012-06-06T22:09:36.913 回答
0

因为它们不是完整的镜像函数，所以在两个函数console.log()的所有ifs 和elses 中添加 s 并比较结果，您会发现测试不公平。

你做错了什么。我建议在开始测试之前确保它们都按预期工作。

于 2012-06-06T23:15:09.150 回答