Как я могу оптимизировать этот код? - PullRequest
Новая
       42

Как я могу оптимизировать этот код?

1 голос
/ 03 ноября 2010

В моем текущем проекте мы используем TreeSet и TreeMap на Java с входным массивом из 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 элементов создание карты на машине с частотой 2,4 ГГц с 6 ГБ ОЗУ может занять более 15 минут.Что я могу сделать, чтобы сделать этот код более эффективным?К сожалению, сокращение входных данных не вариант.

Ответы [ 4 ]

6 голосов
/ 03 ноября 2010

Похоже, ваш 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 bar
  • Песня 3 - foo bar baz

Песня1 будет видно, что foo не содержит lyricWords, поэтому он вызовет buildSongSet и создаст набор для foo.Он добавится в набор, содержащий foo.

Song 2 увидит, что foo находится в lyricWords, и добавит себя в набор.Он увидит, что панель не входит в набор, и создаст набор и добавит себя.Ему не нужно проходить предыдущие песни, так как в первый раз слово было найдено в Песне 2.

Песня 3 следует той же логике.

Еще одна вещь, которую вы можете попробовать сделать, чтобы оптимизировать свойКод должен найти способ не обрабатывать повторяющиеся слова в тексте.если ваша лирика foo foo foo foo bar bar bar foo bar, то вы будете делать много ненужных проверок.

EDIT также см. ответ rsp - есть дополнительные ускорения, но большое ускорение избавляет от внутреннего цикла - рад, что теперь он сокращен до 15 секунд.

4 голосов
/ 03 ноября 2010

Весь метод buildSongSet() не нужен imho, так как ваш основной цикл уже добавляет песни в коллекцию по слову.Единственное, чего вам не хватает, - это добавления набора для нового слова, например: 

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

Одна проблема, которую вы не решали, это то, что песни добавляются в набор несколько раз, длякаждый случай появления слова в песне.

Другая проблема заключается в том, что в случае, если песня содержит всего 1 слово, вы не добавляете его вообще!Всегда лучше сначала проверить условие: 

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

Ваше условие выполняет одну проверку слишком много (пустая строка имеет длину <1), и замена проверок также может ускорить процесс: </p>

if (word.length() > 1 && !commonWords.contains(word)) {
3 голосов
/ 03 ноября 2010

Пожалуйста, попробуйте изменить TreeSet на HashSet. Я не вижу, где вы получаете преимущества TreeSet.

0 голосов
/ 04 ноября 2010

, если вам нужен очень расширяемый и простой способ решения этой проблемы с производительностью порядка нескольких миллисекунд. Рассмотрим люцен http://lucene.apache.org/

см. Мой ответ здесь для примера того, как индексировать и искать Как индексировать и искать текстовые файлы в Lucene 3.0.2?

...