0

我需要优化搜索引擎。所做的是通过像这样进行所有可能的组合来找到所有可能的 2 到 n 字母单词

（对于 2 个字母的单词）w = 任何字母都可以在第一个字母点 + 任何剩下的字母（但第一个字母）用于第二个点；checkIfIsWord(w)

（对于 n 个字母单词） n1 + n2 + n3 + n4 + ... n ；checkIfIsWord(w)

这是有效的，但相当耗时。请帮我想想如何让它更快！

这是代码：

String w = "";
    for (int i = 0; i < letters.length; i++)
    {
        for (int j = 0; j < letters.length; j++)
        {
            if (i == j) continue;
            w = "" + (char) letters[i] + (char) letters[j];
            checkIfIsWord(w);
            for (int k = 0; k < letters.length; k++)
            {
                if (i == k || j == k) continue;
                w = "" + (char) letters[i] + (char) letters[j] + (char) letters[k];
                checkIfIsWord(w);
                for (int m = 0; m < letters.length; m++)
                {
                    if (i == m || j == m || j == m || k == m) continue;
                    w = "" + (char) letters[i] + (char) letters[j] + (char) letters[k] + (char) letters[m];
                    checkIfIsWord(w);
                    ...
                }
            }
        }
    }

方法checkIfIsWord

void checkIfIsWord(String w) 
{ 
    if (w.length() > 2 
        && words.contains(w.toLowerCase()) // (1) 
        && !allWords.contains(w)) 
    { 
       allWords.add(w); 
        runOnUiThread(updateMaxWords); 
    } 
}
4

1 回答 1

1

如果您有一个预定义字符串列表，正如我从您的评论中收集的那样，您应该反过来检查它。遍历列表中的所有单词并存储符合您条件的单词。这只会具有线性复杂性。

在您的方法中checkIfIsWord：

void checkIfIsWord(String w) 
{ 
    if (w.length() > 2 
        && words.contains(w.toLowerCase()) // (1) 
        && !allWords.contains(w)) 
    { 
        allWords.add(w); 
        runOnUiThread(updateMaxWords); 
    } 
}

标有 的行将(1)检查您当前的单词与w当前在 中的所有条目words。这就是.contains()内部所做的。这意味着在您的结果列表中allWords，您只能将值的子集存储在words. 更快的实现肯定如下：

for(String word : words)
{
    if(word.length() > 2
       && word.length() < n)
    {
        allWords.add(word);
        runOnUiThread(updateMaxWords);
    }
}

现在，如果您说具有 16k 个条目的字符串数组会消耗大量内存，这是正确的。但是您的原始解决方案也有同样的问题，因为标有 的行(1)只允许列表中已经存在的单词words成为结果集的一部分。如果你想解决这个问题，我建议将这些词移到数据库中，而不是将它们全部保存在 RAM 中。

于 2013-03-07T14:50:40.197 回答