Wie kann ich die Effizienz und/oder Leistung meiner relativ einfachen Java-Zählmethode verbessern?

Question

Ich baue einen Klassifikator, der viele Textdokumente durchlesen muss, aber ich fand heraus, dass meine Methode umso langsamer wird, je mehr Dokumente sie verarbeitet hat. Diese Methode dauert 60ms (auf meinem PC), während das Lesen, Normalisieren, Tokenisieren, Aktualisieren meines Vokabulars und das Ausgleichen verschiedener Listen von ganzen Zahlen nur 3-5ms dauert (auf meinem PC). Meine countWordFrequencies Methode ist wie folgt:

public List<Integer> countWordFrequencies(String[] tokens) 
{ 
    List<Integer> wordFreqs = new ArrayList<>(vocabulary.size()); 
    int counter = 0; 

    for (int i = 0; i < vocabulary.size(); i++) 
    { 
     for (int j = 0; j < tokens.length; j++) 
      if (tokens[j].equals(vocabulary.get(i))) 
       counter++; 

     wordFreqs.add(i, counter); 
     counter = 0; 
    } 

    return wordFreqs; 
} 

Was ist der beste Weg für mich, diesen Prozess zu beschleunigen? Was ist das Problem dieser Methode?

Das ist meine gesamte Klasse, es gibt eine andere Klassenkategorie, ist es eine gute Idee, dies auch hier zu posten oder brauchst du das nicht?

public class BayesianClassifier 
{ 
    private Map<String,Integer> vocabularyWordFrequencies; 
    private List<String> vocabulary; 
    private List<Category> categories; 
    private List<Integer> wordFrequencies; 
    private int trainTextAmount; 
    private int testTextAmount; 
    private GUI gui; 

    public BayesianClassifier() 
    { 
     this.vocabulary = new ArrayList<>(); 
     this.categories = new ArrayList<>(); 
     this.wordFrequencies = new ArrayList<>(); 
     this.trainTextAmount = 0; 
     this.gui = new GUI(this); 
     this.testTextAmount = 0; 
    } 

    public List<Category> getCategories() 
    { 
     return categories; 
    } 

    public List<String> getVocabulary() 
    { 
     return this.vocabulary; 
    } 

    public List<Integer> getWordFrequencies() 
    { 
     return wordFrequencies; 
    } 

    public int getTextAmount() 
    { 
     return testTextAmount + trainTextAmount; 
    } 

    public void updateWordFrequency(int index, Integer frequency) 
    { 
     equalizeIntList(wordFrequencies); 
     this.wordFrequencies.set(index, wordFrequencies.get(index) + frequency); 
    } 

    public String readText(String path) 
    { 
     BufferedReader br; 
     String result = ""; 

     try 
     { 
      br = new BufferedReader(new FileReader(path)); 

      StringBuilder sb = new StringBuilder(); 
      String line = br.readLine(); 

      while (line != null) 
      { 
       sb.append(line); 
       sb.append("\n"); 
       line = br.readLine(); 
      } 

      result = sb.toString(); 
      br.close(); 
     } 
     catch (IOException e) 
     { 
      e.printStackTrace(); 
     } 

     return result; 
    } 

    public String normalizeText(String text) 
    { 
     String fstNormalized = Normalizer.normalize(text, Normalizer.Form.NFD); 

     fstNormalized = fstNormalized.replaceAll("[^\\p{ASCII}]",""); 
     fstNormalized = fstNormalized.toLowerCase(); 
     fstNormalized = fstNormalized.replace("\n",""); 
     fstNormalized = fstNormalized.replaceAll("[0-9]",""); 
     fstNormalized = fstNormalized.replaceAll("[/()!?;:,.%-]",""); 
     fstNormalized = fstNormalized.trim().replaceAll(" +", " "); 

     return fstNormalized; 
    } 

    public String[] handleText(String path) 
    { 
     String text = readText(path); 
     String normalizedText = normalizeText(text); 

     return tokenizeText(normalizedText); 
    } 

    public void createCategory(String name, BayesianClassifier bc) 
    { 
     Category newCategory = new Category(name, bc); 

     categories.add(newCategory); 
    } 

    public List<String> updateVocabulary(String[] tokens) 
    { 
     for (int i = 0; i < tokens.length; i++) 
      if (!vocabulary.contains(tokens[i])) 
       vocabulary.add(tokens[i]); 

     return vocabulary; 
    } 

    public List<Integer> countWordFrequencies(String[] tokens) 
    { 
     List<Integer> wordFreqs = new ArrayList<>(vocabulary.size()); 
     int counter = 0; 

     for (int i = 0; i < vocabulary.size(); i++) 
     { 
      for (int j = 0; j < tokens.length; j++) 
       if (tokens[j].equals(vocabulary.get(i))) 
        counter++; 

      wordFreqs.add(i, counter); 
      counter = 0; 
     } 

     return wordFreqs; 
    } 

    public String[] tokenizeText(String normalizedText) 
    { 
     return normalizedText.split(" "); 
    } 

    public void handleTrainDirectory(String folderPath, Category category) 
    { 
     File folder = new File(folderPath); 
     File[] listOfFiles = folder.listFiles(); 

     if (listOfFiles != null) 
     { 
      for (File file : listOfFiles) 
      { 
       if (file.isFile()) 
       { 
        handleTrainText(file.getPath(), category); 
       } 
      } 
     } 
     else 
     { 
      System.out.println("There are no files in the given folder" + " " + folderPath.toString()); 
     } 
    } 

    public void handleTrainText(String path, Category category) 
    { 
     long startTime = System.currentTimeMillis(); 

     trainTextAmount++; 

     String[] text = handleText(path); 

     updateVocabulary(text); 
     equalizeAllLists(); 

     List<Integer> wordFrequencies = countWordFrequencies(text); 
     long finishTime = System.currentTimeMillis(); 

     System.out.println("That took 1: " + (finishTime-startTime)+ " ms"); 

     long startTime2 = System.currentTimeMillis(); 

     category.update(wordFrequencies); 
     updatePriors(); 

     long finishTime2 = System.currentTimeMillis(); 

     System.out.println("That took 2: " + (finishTime2-startTime2)+ " ms"); 
    } 

    public void handleTestText(String path) 
    { 
     testTextAmount++; 

     String[] text = handleText(path); 
     List<Integer> wordFrequencies = countWordFrequencies(text); 
     Category category = guessCategory(wordFrequencies); 
     boolean correct = gui.askFeedback(path, category); 

     if (correct) 
     { 
      category.update(wordFrequencies); 
      updatePriors(); 
      System.out.println("Kijk eens aan! De tekst is succesvol verwerkt."); 
     } 
     else 
     { 
      Category correctCategory = gui.askCategory(); 
      correctCategory.update(wordFrequencies); 
      updatePriors(); 
      System.out.println("Kijk eens aan! De tekst is succesvol verwerkt."); 
     } 
    } 

    public void updatePriors() 
    { 
     for (Category category : categories) 
     { 
      category.updatePrior(); 
     } 
    } 

    public Category guessCategory(List<Integer> wordFrequencies) 
    { 
     List<Double> chances = new ArrayList<>(); 

     for (int i = 0; i < categories.size(); i++) 
     { 
      double chance = categories.get(i).getPrior(); 

      System.out.println("The prior is:" + chance); 

      for(int j = 0; j < wordFrequencies.size(); j++) 
      { 
       chance = chance * categories.get(i).getWordProbabilities().get(j); 
      } 

      chances.add(chance); 
     } 

     double max = getMaxValue(chances); 
     int index = chances.indexOf(max); 

     System.out.println(max); 
     System.out.println(index); 
     return categories.get(index); 
    } 

    public double getMaxValue(List<Double> values) 
    { 
     Double max = 0.0; 

     for (Double dubbel : values) 
     { 
      if(dubbel > max) 
      { 
       max = dubbel; 
      } 
     } 

     return max; 
    } 

    public void equalizeAllLists() 
    { 
     for(Category category : categories) 
     { 
      if (category.getWordFrequencies().size() < vocabulary.size()) 
      { 
       category.setWordFrequencies(equalizeIntList(category.getWordFrequencies())); 
      } 
     } 

     for(Category category : categories) 
     { 
      if (category.getWordProbabilities().size() < vocabulary.size()) 
      { 
       category.setWordProbabilities(equalizeDoubleList(category.getWordProbabilities())); 
      } 
     } 
    } 

    public List<Integer> equalizeIntList(List<Integer> list) 
    { 
     while (list.size() < vocabulary.size()) 
     { 
      list.add(0); 
     } 

     return list; 
    } 

    public List<Double> equalizeDoubleList(List<Double> list) 
    { 
     while (list.size() < vocabulary.size()) 
     { 
      list.add(0.0); 
     } 

     return list; 
    } 

    public void selectFeatures() 
    { 
     for(int i = 0; i < wordFrequencies.size(); i++) 
     { 
      if(wordFrequencies.get(i) < 2) 
      { 
       vocabulary.remove(i); 
       wordFrequencies.remove(i); 

       for(Category category : categories) 
       { 
        category.removeFrequency(i); 
       } 
      } 
     } 
    } 
} 

Answer 1

Ihre Methode hat O(n*m) Laufzeit (wobei n die Vokabulargröße und m die Token-Größe). Mit Hashing konnte dies auf O(m) reduziert werden, was deutlich besser ist.

for (String token: tokens) { 
    if(!map.containsKey(token)){ 
     map.put(token,0); 
    } 
    map.put(token,map.get(token)+1); 
} 

Answer 2

Statt eine Liste für das Vokabular zu verwenden, und eine andere für die Frequenzen, würde ich eine Karte verwenden, die Wort- speichert> Frequenz. Auf diese Weise können Sie die doppelte Schleife vermeiden, die meiner Meinung nach Ihre Leistung zerstört.

public Map<String,Integer> countWordFrequencies(String[] tokens) { 
    // vocabulary is Map<String,Integer> initialized with all words as keys and 0 as value 
    for (String word: tokens) 
     if (vocabulary.containsKey(word)) { 
     vocabulary.put(word, vocabulary.get(word)+1); 
     } 
    return vocabulary; 
} 

Answer 3

ein Map Verwendung sollte die Leistung erheblich steigern, da Sleiman Jneidi in seiner Antwort vorgeschlagen. Dies kann jedoch geschehen, viel eleganter mit Java 8 Streaming-APIs:

Map<String, Long> frequencies = 
    Arrays.stream(tokens) 
      .collect(Collectors.groupingBy(Function.identity(), 
             Collectors.counting())); 

Answer 4

Wenn Sie nicht Java 8 Sachen verwenden möchten, können Sie versuchen, MultiSet von Guave zu verwenden