使我的字典搜索更高效

我在Java中創建了一個boggle求解器，解決一塊板需要大約一分30秒的時間，並且我相信它是因爲我遍歷字典的方式。這個想法是檢查它是否是一個單詞，以及看它是否是一個有效的前綴。如果它有一個有效的前綴，它將返回true，以便程序繼續運行。如果它返回false，程序將停止運行正在進行的過程。我讀了關於特里結構，但我不知道如何實施它們。與編寫的代碼示例一個小的解釋會很感激使我的字典搜索更高效

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

來源

2013-03-08 Louis B

看到'dic'和'checked'的聲明是很有價值的。另外，如果你可以顯示一些執行配置文件的時間來確認a）這個函數實際上佔用了執行時間的大部分時間，b）這個函數的哪些部分佔用了執行時間的大部分時間，這可以幫助你我們瞄準最有前途的優化領域。 – Simon 2013-03-08 03:23:02

如果事實證明字典訪問實際上是瓶頸，那麼在http://www.superliminal.com/sources/TrieMap.java.html中有一個Java實現。 – Simon 2013-03-08 03:25:54

他們都arrayLists，我也不知道如何顯示執行配置文件的時機，因爲我是相當新的Java /編程 – 2013-03-08 03:57:13

我建議做的第一件事將是使dic和checked HashSets代替的ArrayList，這將給你的O（1）訪問時間而不是O（N）。如果你認爲這些查找是關鍵瓶頸是正確的，那麼你的程序的性能應該會大大提高。

如果這樣做不足以改善問題，在學習如何剖析Java程序以便確定問題所在之處時，花幾分鐘的時間就值得投入。

來源

2013-03-08 04:13:49 Simon

我試圖讓他們所有的哈希集，但我無法找出一種方法來獲取字符串存儲在HashSet的。 ArrayList有.get（）方法，而hashset有一個itorator，但是當我使用它時，它每次都沒有返回。有什麼想法嗎？ – 2013-03-13 00:45:36

如果您可以使用帶迭代器的HashSet來顯示一些簡潔的自包含代碼，以顯示其不正確的行爲（最好將其作爲單獨的問題來完成此操作），那麼我或其他人可能可以爲您提供幫助。如果你正在尋找一個如何做的例子，這裏有一個簡單的例子：http://stackoverflow.com/questions/6235010/problem-with-a-hashsets-iterator。 – Simon 2013-03-13 03:35:08

使我的字典搜索更高效

回答

相關問題