1

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

首先,我遍历输入的 Song 数组,访问歌词字段并创建一个 Scanner 对象以使用以下代码遍历歌词: commonWords是不应该是键的单词的 TreeSet,并且lyricWords是单词到 Songs 的整体映射。

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

    }

为了构建歌曲集,我使用以下代码:

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

将歌曲添加到现有集合。所以,当你找到一个你不知道的词时,只需添加一首歌曲即可。将 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 - 富吧
  • 歌曲 3 - foo bar baz

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

歌曲 2 将看到 foo 在 lyricWords 中,并将其自身添加到集合中。它将看到 bar 不在集合中,并创建一个集合并添加自己。它不需要遍历之前的歌曲,因为第一次看到这个词是在歌曲 2 中。

歌曲 3 遵循相同的逻辑。

您可以尝试做的另一件事来优化您的代码是找出一种不处理歌词中重复单词的方法。如果你的歌词是 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);

您没有解决的一个问题是,歌曲最终会被多次添加到集合中,对于歌曲中每个单词的出现。

另一个问题是,如果一首歌只包含一个单词,你根本不添加它!最好先检查条件:

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

您的情况是检查太多(空字符串的长度 < 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 回答