Comment puis-je optimiser ce code?

Question

Mon projet actuel nous permet d'utiliser TreeSet et TreeMap en Java, avec un tableau d'entrée de 10514 éléments de morceau lus à partir d'un fichier texte. Chaque morceau contient des champs Artiste, Titre et Lyrique. Le but de ce projet est de mener des recherches rapides sur les paroles en utilisant des ensembles et des cartes.

D'abord, j'itérer sur le tableau de morceau d'entrée, l'accès au champ de paroles et de créer un objet Scanner à itérer sur les mots lyriques en utilisant ce code: commonWords est un TreeSet de mots qui ne doivent pas être les clés et lyricWords est l'ensemble carte des mots aux chansons.

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

    } 

Pour construire le songSet, j'utiliser ce code:

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

Maintenant, puisque buildSongSet est appelée à l'intérieur d'une boucle, créant la carte en N^exécute 2 temps. Lorsque le tableau d'entrée est composé de 4 morceaux, les recherches sont très rapides, mais lorsque vous utilisez la totalité des 10514 éléments, il faut plus de 15 minutes pour construire la carte sur une machine cadencée à 2,4 GHz avec 6 Go de RAM. Que puis-je faire pour rendre ce code plus efficace? Malheureusement, la réduction des données d'entrée n'est pas une option.

Answer 1

Il semble que votre buildSongSet effectue un travail redondant. Votre bloc:

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

ajoute un morceau à un ensemble existant. Donc, quand vous trouvez un mot que vous ne connaissez pas, il suffit d'ajouter une chanson. Changement 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); 
} 

les chansons restantes reste à itéré sera alors ajouté à cette songset du premier bloc de code si elles contiennent ce mot. Je pense que cela devrait fonctionner.

EDIT juste vu c'était devoirs ... donc supprimé les recommandations HashSet ..

Ok .. donc supposons que vous avez ces chansons pour des paroles:

• Chanson 1 - foo
• Song 2 - foo bar
• chanson 3 - foo bar baz

Le morceau 1 verra que foo ne contient pas de mots lyriques, il appellera alors buildSongSet et créera un ensemble pour foo. Il va s'ajouter dans l'ensemble contenant foo.

Le morceau 2 verra que foo est dans lyricWords, et s'ajoutera à l'ensemble. Il verra que la barre n'est pas dans l'ensemble, et créer un ensemble et ajouter lui-même. Il n'a pas besoin de parcourir les morceaux précédents car la première fois que le mot a été vu était dans le morceau 2.

Le morceau 3 suit la même logique.

Une autre chose que vous pouvez faire pour optimiser votre code est de trouver un moyen de ne pas traiter les mots en double dans les paroles. Si vos paroles sont foo foo foo foo bar bar bar foo, alors vous allez faire beaucoup de contrôles inutiles.

EDIT voir aussi rsp's answer - des accélérations supplémentaires là-bas, mais la grande accélération est de se débarrasser de la boucle intérieure - content qu'il soit à 15 secondes maintenant.

Answer 2

S'il vous plaît, essayez de changer TreeSet à HashSet. Je ne vois pas où vous obtenez les avantages de TreeSet.

Answer 3

La méthode entière buildSongSet() n'est pas nécessaire, car votre boucle principale ajoute déjà des chansons à la collection par mot. La seule chose qui vous manque est l'ajout d'un ensemble pour un nouveau mot, quelque chose comme:

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

Une question que vous n'abordez est que les chansons finissent par être ajouté aux multiples fois fixés, pour chaque occurence du mot dans la chanson.

Un autre problème est que dans le cas où une chanson contient seulement 1 mot, vous ne l'ajoutez pas du tout! Il est toujours préférable de vérifier l'état premier:

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

Votre condition est en train de faire un chèque trop (la chaîne vide a une longueur < 1) et la permutation des contrôles peut accélérer les choses aussi:

if (word.length() > 1 && !commonWords.contains(word)) { 

Answer 4

si vous voulez une solution très extensible et facile à résoudre avec des performances de l'ordre de quelques millisecondes. Tenir compte Lucene http://lucene.apache.org/

renvoie à ma réponse ici par exemple de la façon d'indexer et de rechercher How do I index and search text files in Lucene 3.0.2?