我该如何优化此代码？

Question

我当前的项目让我们在Java中使用TreeSet和TreeMap,从文本文件中读入10514个Song元素的输入数组.每首歌曲包含艺术家,标题和抒情字段.该项目的目的是使用集合和地图对歌词进行快速搜索.

首先,我遍历输入的Song数组,访问lyrics字段并创建一个Scanner对象,使用此代码迭代歌词: commonWords是一个不应该是键的单词TreeSet,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分钟.我该怎么做才能使这段代码更有效率？不幸的是,减少输入数据不是一种选择.

Answer 1

看起来你的buildSongSet正在做多余的工作.你的块:

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

将歌曲添加到现有集合中.因此,当您找到一个您不知道的单词时,只需添加一首歌即可.将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 - foo
• 歌曲2 - foo吧
• 歌曲3 - foo bar baz

歌曲1将看到foo不包含lyricWords,因此它将调用buildSongSet并为foo创建一个集合.它会将自己添加到包含foo的集合中.

歌曲2将看到foo在lyricWords中,并将自己添加到集合中.它会看到bar不在集合中,并创建一个集合并自行添加.自从第一次看到单词出现在Song 2中以来,它不需要遍历以前的歌曲.

歌曲3遵循相同的逻辑.

您可以尝试优化代码的另一件事是找出一种不处理歌词中重复单词的方法.如果你的歌词是foo foo foo foo bar bar bar foo bar那么你将会做很多不必要的检查.

编辑也看到了rsp的答案 - 那里有额外的加速,但是大的加速是摆脱内循环 - 很高兴它现在已经下降到15秒.