Оптимизация последовательного поиска в цикле - PullRequest
Новая
       10

Оптимизация последовательного поиска в цикле

0 голосов
/ 07 июня 2018

Я пытаюсь получить ArrayList (или набор, или что-нибудь подобное) исполнителей из списка песен.Каждая песня имеет функцию getArtists, которая возвращает массив каждого исполнителя, участвующего в песне.
Цель состоит в том, чтобы иметь список исполнителей, и у каждого исполнителя должен быть список (или набор, в зависимости от того, что быстрее), который содержит всеПесни, в которых он участвует.

Мой код работает, но он довольно медленный (для 1600 песен требуется 5 секунд).Как я могу ускорить его?

Мой код 

private ArrayList<Artist> getArtistsFromSongs(List<Song> songs)
{
    long start = System.currentTimeMillis();

    ArrayList<Artist> artists = new ArrayList<>();
    for (Song song : songs)
    {
        String[] artistsStringArray = song.getArtists();
        for (String artistString : artistsStringArray)
        {
            boolean artistAlreadyExists = false;
            int heExistsAt = -1;

            for (int i = 0; i < artists.size(); i++)
            {
                if (artists.get(i).name.equals(artistString))
                {
                    artistAlreadyExists = true;
                    heExistsAt = i;
                }
            }
            if (artistAlreadyExists)
            {
                artists.get(heExistsAt).songs.add(song);
            } else
            {
                Artist newArtist = new Artist(artistString, new ArrayList<>());
                newArtist.songs.add(song);
                artists.add(newArtist);
            }
        }
    }
    long test = System.currentTimeMillis() - start; //~5500 milliseconds
    return artists;
}

Класс 

class Artist
{
    public final String name;
    public final ArrayList<Song> songs;

    Artist(String name, ArrayList<Song> songs)
    {
        this.name = name;
        this.songs = songs;
    }
}

Заранее спасибо.

1 Ответ

0 голосов
/ 07 июня 2018

Чтобы повысить производительность, измените artists с ArrayList<Artist> на HashMap<String, Artist>.

Таким образом, вы можете заменить самый внутренний цикл последовательного поиска на быстрый и простой поиск по карте . 

Map<String, Artist> artists = new HashMap<>();
for (Song song : songs) {
    for (String artistName : song.getArtists()) {
        Artist artist = artists.get(artistName);
        if (artist == null) {
            artist = new Artist(artistName, new ArrayList<>());
            artists.put(artistName, artist);
        }
        artist.Songs.add(song);
    }
}

В Java 8+ это можно улучшить, особенно если немного изменить класс Artist. 

Map<String, Artist> artists = new HashMap<>();
for (Song song : songs) {
    for (String artistName : song.getArtists()) {
        artists.computeIfAbsent(artistName, Artist::new).addSong(song);
    }
}

class Artist {
    public final String name;
    public final ArrayList<Song> songs = new ArrayList<>();

    Artist(String name) {
        this.name = name;
    }

    void addSong(Song song) {
        this.songs.add(song);
    }
}

Примечание:Соглашение об именах Java заключается в том, чтобы имена полей начинались со строчной буквы, поэтому второе решение, приведенное выше, было изменено, чтобы отразить это.

...