java - 让我的字典搜索更有效率

Question

我用 Java 创建了一个 boggle 求解器，求解一个棋盘大约需要 1 分 30 秒，我确信它是因为我遍历字典的方式。这个想法是它检查它是否是一个单词，并查看它是否是一个有效的前缀。如果它是一个有效的前缀，它将返回 true 以便程序继续运行。如果它返回 false，那么程序将停止运行它正在学习的类(class)。我阅读了有关 trie 结构的信息，但不太了解如何实现它们。带有书面代码的示例以及一个简短的解释将不胜感激

private ArrayList <String> dic = new ArrayList<String>(/*dictionary()*/);//my useable dictionary
private ArrayList <String> dicFinal = new ArrayList<String>();//all the words found
private ArrayList <String> checked = new ArrayList<String>();//all words that have   already been checked go here
public boolean CheckTest (String word)throws IOException{//if its impossible to create a word with the combination of letters then it returns false, 
    String backw=reverse(word);
    boolean isValid = true;     
    if (word.length()<=1){isValid = true;}
    else if (checked.contains(word)&&checked.contains(backw)){}
    else{
        boolean isWord=true;
        if(checked.contains(word)){}
        else if(dic.contains(word)==true){
            setCount(getCount()+1);
            dicFinal.add(word);
            dic.remove(word);
            isWord=true;
        }
        else
            isWord=false;
        if(checked.contains(backw)==true){}
        else if (dic.contains(backw)==true){
            setCount(getCount()+1);
            dicFinal.add(backw);
            dic.remove(word);
        }
        if(isWord==false){
            for(int i=0;i<dic.size();i++){
                if(word.length()<=dic.get(i).length()&&dic.get(i).substring(0, word.length()).equalsIgnoreCase(word.substring(0, word.length()))){
                    isValid=true;
                    i=dic.size();
                }
                else 
                    isValid=false;
            }
        }
    }
    checked.add(word);
    checked.add(backw);
    return isValid;
}

Answer 1

我建议首先要做的是制作 dic 和 checked HashSets 而不是 ArrayLists，这会给你 O(1) 的访问时间的 O(N)。如果您关于这些查找是关键瓶颈的假设是正确的，那么您的程序的性能应该会得到极大的提高。

如果这还不够改善问题，那么花几分钟时间学习如何分析 Java 程序以查明问题所在是值得的。