9

2 つの等しい長さの英単語間の接続を見つけようとする小さなプログラムを作成しました。単語 A は一度に 1 文字を変更することで単語 B に変換されます。新しく作成された各単語は英語の単語でなければなりません。

例えば：

Word A = BANG
Word B = DUST

結果：

BANG -> BUNG ->BUNT -> DUNT -> DUST

私のプロセス:

  1. 英語の単語リスト (109582 単語で構成) を にロードしますMap<Integer, List<String>> _wordMap = new HashMap();。キーは単語の長さになります。

  2. ユーザーは 2 つの単語を入力しました。

  3. createGraph はグラフを作成します。

  4. これらの 2 つのノード間の最短経路を計算します

  5. 結果を出力します。

すべてが完全に正常に機能しますが、ステップ 3 でかかった時間には満足できません。

見る：

Completely loaded 109582 words!
CreateMap took: 30 milsecs
CreateGraph took: 17417 milsecs
(HOISE : HORSE)
(HOISE : POISE)
(POISE : PRISE)
(ARISE : PRISE)
(ANISE : ARISE)
(ANILE : ANISE)
(ANILE : ANKLE)
The wholething took: 17866 milsecs

ステップ 3でグラフを作成するのにかかる時間に満足していません。これが私のコードです (グラフに JgraphT を使用しています)。

private List<String> _wordList = new ArrayList();  // list of all 109582 English words
private Map<Integer, List<String>> _wordMap = new HashMap();  // Map grouping all the words by their length()
private UndirectedGraph<String, DefaultEdge> _wordGraph =
        new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);  // Graph used to calculate the shortest path from one node to the other.


private void createGraph(int wordLength){

    long before = System.currentTimeMillis();
    List<String> words = _wordMap.get(wordLength);
    for(String word:words){
        _wordGraph.addVertex(word);  // adds a node
        for(String wordToTest : _wordList){
            if (isSimilar(word, wordToTest)) {        
                _wordGraph.addVertex(wordToTest);  // adds another node
                _wordGraph.addEdge(word, wordToTest);  // connecting 2 nodes if they are one letter off from eachother
            }
        }            
    }        

    System.out.println("CreateGraph took: " + (System.currentTimeMillis() - before)+ " milsecs");
}


private boolean isSimilar(String wordA, String wordB) {
    if(wordA.length() != wordB.length()){
        return false;
    }        

    int matchingLetters = 0;
    if (wordA.equalsIgnoreCase(wordB)) {
        return false;
    }
    for (int i = 0; i < wordA.length(); i++) {

        if (wordA.charAt(i) == wordB.charAt(i)) {
            matchingLetters++;
        }
    }
    if (matchingLetters == wordA.length() - 1) {
        return true;
    }
    return false;
}

私の質問：

プロセスを高速化するためにアルゴリズムを改善するにはどうすればよいですか?

これを読んでいる redditor の皆さん、はい、昨日 /r/askreddit のスレッドを見てこれを作成しました。

4

3 に答える 3

18

これが最初の考えです：

Map<String, List<String>>a (または、 Guava を使用している場合は a) を作成し、Multimap<String, String>単語ごとに 1 文字ずつ「空白化」し、その空白化された単語のリストに元の単語を追加します。したがって、次のようになります。

.ORSE => NORSE, HORSE, GORSE (etc)
H.RSE => HORSE
HO.SE => HORSE, HOUSE (etc)

その時点で、単語が与えられると、それが類似しているすべての単語を非常に簡単に見つけることができます。同じプロセスをもう一度実行するだけですが、マップに追加する代わりに、「空白化された」バージョンごとにすべての値を取得するだけです。

于 2012-11-10T18:36:17.790 に答える
0

特にライブラリ クラスを使用しているため、どこに多くの時間が費やされているかを確認するには、おそらくプロファイラーを実行する必要があります。

開始する前にすべての単語を小文字にして、equalsIgnoreCase()on every 比較を避けることができます。実際、これはコードの矛盾です。equalsIgnoreCase()最初は使用しますが、大文字と小文字を区別して文字を比較します: if (wordA.charAt(i) == wordB.charAt(i)). これは本質的に次のループequalsIgnoreCase()と同じことを行っているため、チェックを完全に削除する価値があるかもしれません。charAt

比較ループを変更して、すべての文字を比較してから一致する文字と異なる文字を確認するのではなく、複数の異なる文字が見つかったときに早期に終了するようにすることができます。

（更新：この回答は、現在のコードの最適化に関するものです。質問をもう一度読んで、代替アルゴリズムについて質問している可能性があることに気付きました！）

于 2012-11-10T18:33:09.497 に答える
0

同じ長さの単語のリストをソートしてから、種類のループネストを作成できますfor (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { }。

そして isSimilar で違いを数え、2 で false を返します。

于 2012-11-10T18:43:53.910 に答える