3

我的浏览器从这个似乎没有终止的循环中崩溃。

function checkLetters(word){
    for(i=0;i<5;i++){
        for(j=i+1;j<5;j++){
            if(word.charAt(i) == word.charAt(j)){
                return false;
                break;
            } 
        }
    }
    return true;
}
var compLibrary = [];
for (var k=0;k<library.length;k++) {
    if(checkLetters(library[k]) == true) {
        compLibrary.push(library[k]);
    }
}

我正在尝试在库中搜索没有重复字母的单词并将其推入一个新数组整个库是五个字母的单词。

4

6 回答 6

3

这不是一个无限循环，但它看起来确实是一个非常昂贵的操作。没有任何真正优雅的方法来检测无限循环（或递归），所以大多数引擎只是求助于

  1. 不尝试检测它，并且永远运行直到某些较低级别的控制器（例如内核）杀死它。
  2. 当它达到一定的递归深度、循环计数或运行时间时自动杀死自己。

您的算法循环 5 * 4 * library.length 次，因此根据您的库实际有多长，您的代码肯定会触发 #2。但是有更快的方法来查找重复的字母：

function checkLetters(word) {
    var i=word.length;
    var seenChars={};
    var c;
    while (i-->0) {
      c = word.CharAt(i); # The current character
      if (c in seenChars) return false;
      seenChars[c] = 1;
    }
    return true;
}
var compLibrary = [];
for (var k=0; k < library.length; k++) {
    if (checkLetters(library[k]) == true) {
        compLibrary.push(library[k]);
    }
}
于 2013-08-09T01:06:03.967 回答
0 
function checkLetters(word){
    for(i=0;i<5;i++){      //both i and j were not instantiated
        for(j=i+1;j<5;j++){
            if(word.charAt(i) == word.charAt(j)){ //It could be crashing if
                return false;                     //word <= 5
                break;//a break after a return
            }         //statement is redundant.
        }
    }
    return true;
}

您必须var在声明变量之前放置。

word.charAt(i)可以写成word[i]

于 2013-08-09T01:02:59.837 回答
0

尝试这个：

function checkLetters(word){
  for(var i=0,j=1,l=word.length-1; i<l; i++,j++){
    if(word.charAt(i) == word.charAt(j)){
      return false;
    } 
  }
  return true;
}
var compLibrary = [];
for(var i=0,l=library; i<l; i++){
  if(checkLetters(library[i]) == true){
    compLibrary.push(library[i]);
  }
}
于 2013-08-09T01:04:36.507 回答
0

tldr; 最初发布的代码不应使浏览器崩溃。

下面解释了为什么嵌套循环并不总是对效率不利，并展示了一个反例，当运行超过 100,000 个模拟单词时，原始代码可以成功运行而不会导致浏览器崩溃。

发布的代码的复杂性很低，它应该运行得非常快。它在几分之一秒内执行（不到 20 毫秒！），即使是“20 * 8000” - 即 C * O(n)。请注意，时间复杂度是线性的，因为 checkLetters 中的嵌套循环具有恒定的时间：由于这个小的固定限制（每次调用最多“20 个循环”），它在这里并不代表性能问题。

因此，我认为这不是一个问题，它是一个效率问题。我断言原始代码不会“崩溃”现代浏览器环境。对于更长或未绑定的单词，然后使用（可能）较低复杂度的探测尝试可能会得到回报 - 但内部循环在这里以小的恒定时间运行。（实际上，由于单词中字母的分布和单词长度，我想对于像英语这样的自然语言，常数很少超过“90 个循环”。）

见http://jsfiddle.net/FqdX7/6/

library = []
for (w = 0; w < 100000; w++) {
    library.push((w + "12345").slice(0,5))
}
function checkLetters(word){
    for(i=0;i<5;i++){
        for(j=i+1;j<5;j++){
            if(word.charAt(i) == word.charAt(j)){
                return false;
            } 
        }
    }
    return true;
}
$('#time').text("running")
start = +(new Date)
var compLibrary = [];
for (var k=0;k<library.length;k++) {
    if(checkLetters(library[k]) == true) {
        compLibrary.push(library[k]);
    }
}
time = +(new Date) - start
$('#time').text(time + "ms")

在我的机器上（在 Safari 中），对于 100,000 个单词的输入，代码运行时间约为 30毫秒（如果删除了“return false”，则约为 40 毫秒）！

相比之下，使用探针（seenChars 查找）的答案实际上在 Safari/Chrome 中运行得更糟。请参阅http://jsfiddle.net/Hw2wr/5/，其中 100k 字需要大约 270 毫秒 - 或大约慢 9 倍。但是，这高度依赖于浏览器，评论中的jsperf表明，在 Firefox中，探测方法更快（大约 2 倍），但在 IE中再次变慢（比如 4-5 倍）。

YMMV。我认为原始代码对于给定的情况是可以接受的，而“崩溃”问题在其他地方。

于 2013-08-09T01:16:03.583 回答
0

这个循环不应该

for(i=0;i<5;i++){
        for(j=i+1;j<5;j++){

成为这些方面的东西

for(var i=0; i< word.length ;i++){
        for(j=i+1; j<word.length/2; j++){
于 2013-08-09T00:50:42.597 回答
0

看不到您的问题是什么，但这是我为您的问题建议的解决方案：

var words = ['hello', 'bye', 'foo', 'baz'];

function hasUniqLetters(word){
  var uniq = word.split('').filter(function(letter, idx){
    return word.indexOf(letter) == idx;
  });
  return uniq.length == word.length;
}

var result = words.filter(hasUniqLetters);

console.log(result); //=> ["bye","baz"]
于 2013-08-09T00:52:06.787 回答