2

私は Java でボーグル ソルバーを作成しました。ボードを解くのに約 1 分 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;
}
4

1 に答える 1

0

最初に行うことは、ArrayListsの代わりdicにcheckedHashSetsを作成することです。これにより、O（N）の代わりにO（1）のアクセス時間が与えられます。これらのルックアップが主要なボトルネックであるという仮定が正しければ、プログラムのパフォーマンスは大幅に向上するはずです。

それでも問題が十分に改善されない場合は、問題がどこにあるかを特定できるように、Javaプログラムのプロファイルを作成する方法を学ぶために数分投資する価値があります。

于 2013-03-08T04:13:49.350 に答える