1

私の現在のプロジェクトでは、テキスト ファイルから読み込まれた 10514 の Song 要素の入力配列を使用して、Java で TreeSet と TreeMap を使用しています。各曲には、アーティスト、タイトル、および歌詞のフィールドが含まれています。このプロジェクトの目的は、セットとマップを使用して歌詞を高速に検索することです。

まず、入力 Song 配列を繰り返し処理し、歌詞フィールドにアクセスして、次のコードを使用して歌詞の単語を繰り返し処理する Scanner オブジェクトを作成し commonWordsますlyricWords。

public void buildSongMap() {
    for (Song song:songs) {
        //method variables
        String currentLyrics= song.getLyrics().toLowerCase(); 
        TreeSet<Song> addToSet=null;
        Scanner readIn= new Scanner(currentLyrics);
        String word= readIn.next();

        while (readIn.hasNext()) {

            if (!commonWords.contains(word) && !word.equals("") && word.length()>1) {
                if (lyricWords.containsKey(word)) {
                    addToSet= lyricWords.get(word);
                    addToSet.add(song);
                    word=readIn.next();
                } else 
                    buildSongSet(word);

            } else 
                word= readIn.next();
        }

    }

songSet を構築するために、次のコードを使用します。

public void buildSongSet(String word) {     
    TreeSet<Song> songSet= new TreeSet<Song>();
    for (Song song:songs) {
        //adds song to set 
        if (song.getLyrics().contains(word)) {
            songSet.add(song);
        }
    }
    lyricWords.put(word, songSet);
    System.out.println("Word added "+word);
}

ここで、buildSongSet はループ内から呼び出されるため、マップの作成は N^2 時間で実行されます。入力配列が 4 曲の場合、検索は非常に高速に実行されますが、10514 要素の配列全体を使用すると、6 GiB RAM を搭載した 2.4GHz マシンでマップを構築するのに 15 分以上かかる場合があります。このコードをより効率的にするにはどうすればよいですか? 残念ながら、入力データを減らすことはできません。

4

4 に答える 4

6

buildSongSet が冗長な作業を行っているようです。あなたのブロック:

if (lyricWords.containsKey(word)) {
    addToSet= lyricWords.get(word);
    addToSet.add(song);
    word=readIn.next();
}

既存のセットに曲を追加します。ですから、知らない単語を見つけたら、それに 1 曲追加するだけです。buildSongSet を次のように変更します。

public void buildSongSet(String word, Song firstSongWithWord) {     
    TreeSet<Song> songSet= new TreeSet<Song>();
    songSet.add(firstSongWithWord);
    lyricWords.put(word, songSet);
    System.out.println("Word added "+word);
}

繰り返される残りの曲は、その単語が含まれている場合、コードの最初のブロックからその曲セットに追加されます。私はそれがうまくいくと思います。

編集は、これが宿題であることを確認しました...そのため、HashSetの推奨事項を削除しました..

わかりました..では、これらの曲を歌詞の順に並べたとします。

  • 歌 1 - ふー
  • 曲 2 - フーバー
  • 曲 3 - foo bar baz

曲 1 は foo に lyricWords が含まれていないことがわかるため、buildSongSet を呼び出して foo のセットを作成します。foo を含むセットに自身を追加します。

曲 2 は foo が lyricWords にあることを確認し、自分自身をセットに追加します。バーがセットにないことがわかり、セットを作成してそれ自体を追加します。最初に単語が表示されたのは歌 2 であったため、前の歌をたどる必要はありません。

曲 3 も同じロジックに従います。

コードを最適化するために試すことができるもう 1 つの方法は、歌詞内の重複する単語を処理しない方法を見つけることです。歌詞が foo foo foo foo bar bar bar foo bar の場合、多くの不要なチェックを行うことになります。

編集もrspの回答を参照してください-そこに追加のスピードアップがありますが、大きなスピードアップは内側のループを取り除きます-今では15秒に下がってうれしいです。

于 2010-11-03T16:27:57.743 に答える
4

buildSongSet()メインループはすでに単語ごとにコレクションに曲を追加しているため、メソッド全体は必要ありません。欠けているのは、次のような新しい単語のセットの追加だけです。

if (lyricWords.containsKey(word)) {
    addToSet= lyricWords.get(word);
} else {
    addToSet = new TreeSet();
    lyricWords.put(word, addToSet);
}
addToSet.add(song);

あなたが取り組まなかった問題の 1 つは、曲内で単語が出現するたびに、曲がセットに複数回追加されてしまうことです。

もう 1 つの問題は、曲に含まれる単語が 1 つだけの場合、単語をまったく追加しないことです。最初に状態を確認することをお勧めします。

String word = null;
while (readIn.hasNext()) {
    word = readIn.next();

あなたの条件は1つのチェックを多すぎます（空の文字列の長さは1未満です）。チェックを交換すると速度も向上します。

if (word.length() > 1 && !commonWords.contains(word)) {
于 2010-11-03T17:11:20.550 に答える
3

TreeSet を HashSet に変更してみてください。TreeSet の利点がどこで得られるかわかりません。

于 2010-11-03T16:30:53.703 に答える
0

数ミリ秒のオーダーのパフォーマンスでこれを解決する非常に拡張可能で簡単な方法が必要な場合。lucene を検討してくださいhttp://lucene.apache.org/

Lucene 3.0.2 でテキスト ファイルをインデックス付けして検索する にはどうすればよいですか?

于 2010-11-03T22:29:33.370 に答える