Was ist der schnellste Weg, um Symbolereignisse in Java zu sammeln?

Question

Mein Ziel ist es, eine Funktion zu machen, die das Auftreten von einigen Symbolen (Zeichen) in Zeile zählt. Eine int ID gibt jedem Zeichen, das ich zählen muss. Die Menge der Zeichen ist begrenzt und ich weiß es von Anfang an. Alle Linien bestehen nur aus den Zeichen des Gebots. Die Funktion verarbeitet Gazzilions von Linien. Mein Profiler zeigt immer die Funktion, die die Statistiken sammelt, ist die langsamste (97%), obwohl das Programm viele andere Dinge tut. Zuerst habe ich einen HashMap und Code wie folgt:

occurances = new HashMap<>(); 
    for (int symbol : line) { 
     Integer amount = 1; 
     if (occurances.containsKey(symbol)) { 
      amount += occurances.get(symbol); 
     } 
     occurances.put(symbol, amount); 
    } 

Der Profiler zeigte hashMap.put 97% Prozessorauslastung

nimmt Dann versuchte ich es mit einem einmal erstellten Arraylist zu ersetzen: und optimierte es ein kleines Bit (die Zeilen sind immer länger als 1 Zeichen), aber es ist immer noch sehr langsam.

int symbol = line[0]; 
    occurances.set(symbol, 1); 

    for (int i = 1; i < length; i++) { 
     symbol = line[i]; 
     occurances.set(symbol, 1 + occurances.get(symbol)); 
    } 

Bitte, wenn jemand ein paar bessere Ideen hat, wie diese Aufgabe mit einer besseren Leistung zu lösen, würde Ihre Hilfe sehr werden appreceated.

Answer 1

Man könnte so etwas wie dies versuchen:

public class CharCounter { 

    final int max; 
    final int[] counts; 

    public CharCounter(char max) { 
     this.max = (int) max; 
     counts = new int[this.max + 1]; 
    } 

    public void addCounts(char[] line) { 
     for (int symbol : line) { 
      counts[symbol]++; 
     } 
    } 

    public Map<Integer, Integer> getCounts() { 
     Map<Integer, Integer> countsMap = new HashMap<>(); 
     for (int symbol = 0; symbol < counts.length; symbol++) { 
      int count = counts[symbol]; 
      if (count > 0) { 
       countsMap.put(symbol, count); 
      } 
     } 
     return countsMap; 
    } 
} 

Dieses ein Array verwendet die Zählungen zu halten und verwendet die Zeichen selbst als Index für das Array.
Dadurch müssen Sie nicht mehr prüfen, ob eine Karte den angegebenen Schlüssel usw. enthält. Außerdem müssen die Zeichen nicht mehr autoboxiert werden.

Und ein Performance-Vergleich zeigt etwa 20x Speedup:

public static final char MIN = 'a'; 
public static final char MAX = 'f'; 

private static void count1(Map<Integer, Integer> occurrences, char[] line) { 
    for (int symbol : line) { 
     Integer amount = 1; 
     if (occurrences.containsKey(symbol)) { 
      amount += occurrences.get(symbol); 
     } 
     occurrences.put(symbol, amount); 
    } 
} 

private static void count2(CharCounter counter, char[] line) { 
    counter.addCounts(line); 
} 

public static void main(String[] args) { 
    char[] line = new char[1000]; 
    for (int i = 0; i < line.length; i++) { 
     line[i] = (char) ThreadLocalRandom.current().nextInt(MIN, MAX + 1); 
    } 

    Map<Integer, Integer> occurrences; 
    CharCounter counter; 

    // warmup 
    occurrences = new HashMap<>(); 
    counter = new CharCounter(MAX); 
    System.out.println("Start warmup ..."); 
    for (int i = 0; i < 500_000; i++) { 
     count1(occurrences, line); 
     count2(counter, line); 
    } 
    System.out.println(occurrences); 
    System.out.println(counter.getCounts()); 
    System.out.println("Warmup done."); 


    // original method 
    occurrences = new HashMap<>(); 
    System.out.println("Start timing of original method ..."); 
    long start = System.nanoTime(); 
    for (int i = 0; i < 500_000; i++) { 
     count1(occurrences, line); 
    } 
    System.out.println(occurrences); 
    long duration1 = System.nanoTime() - start; 
    System.out.println("End timing of original method."); 
    System.out.println("time: " + duration1); 


    // alternative method 
    counter = new CharCounter(MAX); 
    System.out.println("Start timing of alternative method ..."); 
    start = System.nanoTime(); 
    for (int i = 0; i < 500_000; i++) { 
     count2(counter, line); 
    } 
    System.out.println(counter.getCounts()); 
    long duration2 = System.nanoTime() - start; 
    System.out.println("End timing of alternative method."); 
    System.out.println("time: " + duration2); 

    System.out.println("Speedup: " + (double) duration1/duration2); 
} 

Ausgang:

Start warmup ... 
{97=77000000, 98=82000000, 99=86500000, 100=86000000, 101=80000000, 102=88500000} 
{97=77000000, 98=82000000, 99=86500000, 100=86000000, 101=80000000, 102=88500000} 
Warmup done. 
Start timing of original method ... 
{97=77000000, 98=82000000, 99=86500000, 100=86000000, 101=80000000, 102=88500000} 
End timing of original method. 
time: 7110894999 
Start timing of alternative method ... 
{97=77000000, 98=82000000, 99=86500000, 100=86000000, 101=80000000, 102=88500000} 
End timing of alternative method. 
time: 388308432 
Speedup: 18.31249185698857 

Auch wenn Sie die -verbose:gc JVM-Flag hinzufügen Sie, dass die ursprüngliche Methode recht tun muss sehen ein bisschen Müll sammeln, während die alternative Methode keine benötigt.

Answer 2

können Sie die char direkt an einen int umwandeln und als

Index verwenden

for (i=0; ; i++){ 
    occurences[(int)line[i]]++; 
} 

Answer 3

Es ist sehr möglich, dass Parametrisierung HashMap nicht es viele Performance-Probleme verursachen.

Was ich tun würde, ist eine Klasse namens IntegerCounter erstellen. Schauen Sie sich AtomicInteger (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/concurrent/atomic/AtomicInteger.java) Code an und kopieren Sie alles von dort außer dem Code, der es Atomic macht. Mit IntegerCounter und Inkrementieren der einzelnen Instanz davon sollten Sie eine Menge Garbage Collection speichern.

Die Verwendung der new Integer(x) für die Schlüsselsuche sollte eine Escape-Analyse ermöglichen, um sie automatisch zu bereinigen.

HashMap<Integer, IntegerCounter> occurances; 

// since the set of characters are already known, add all of them here with an initial count of 0 

for (int i = 0; i < length; i++) { 
    occurances.get(new Integer(line[i])).incrementAndGet(); 
} 

Answer 4

Wie vorgeschlagen here können Sie versuchen, somthing zu tun, wie

List<Integer> line = //get line as a list; 
Map<Integer, Long> intCount = line.parallelStream() 
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); 

Answer 5

In Ihrem Code in den meisten Schleifeniterationen Sie den Eintrag in den 3-mal Map Nachschlag werden:

1.

occurances.containsKey(symbol) 

2.

occurances.get(symbol); 

3.

occurances.put(symbol, amount); 

Das ist mehr als nötig und Sie können einfach die Tatsache nutzen, dass get kehrt null dies zu 2-Lookups zu verbessern:

Integer currentCount = occurances.get(symbol); 
Integer amount = currentCount == null ? 1 : currentCount + 1; 
occurances.put(symbol, amount); 

---

Des Weiteren durch Integer verwenden, neue Integer Objekte müssen werden oft erstellt (sobald sie 127 oder die obere Grenze überschreiten, die für die zwischengespeicherten Werte verwendet wird), was die Leistung verringert.

Da Sie den Zeichensatz vor dem Analysieren der Daten kennen, können Sie auch 0 s (oder gleichwertig) als Werte für alle Zeichen eingeben. Dadurch entfällt die Überprüfung, ob sich bereits ein Mapping in der Karte befindet.

Der folgende Code verwendet eine Hilfsklasse, die ein int count-Feld enthält, um stattdessen die Daten zu speichern, wodurch der Wert ohne Boxing/Unboxing-Konvertierungen erhöht werden kann.

class Container { 
    public int count = 0; 
} 

int[] symbolSet = ... 
Map<Integer, Container> occurances = new HashMap<>(); 
for (int s : symbolSet) { 
    occurances.put(s, new Container()); 
} 

for (int symbol : line) { 
    occurances.get(symbol).count++; 
} 

---

Auch kann eine andere Datenstruktur auch helfen. Dinge, die in den Sinn kommen, sind Perfect Hashing oder Speichern der Daten in einer anderen Datenstruktur als Map. Anstatt jedoch ArrayList zu verwenden, würde ich die Verwendung eines int[]-Arrays empfehlen, da hierfür keine Methodenaufrufe erforderlich sind und außerdem die Notwendigkeit von Boxing/Unboxing-Konvertierungen zu/von Integer entfällt. Die Daten können nach der Berechnung der Frequenzen noch in eine geeignetere Datenstruktur umgewandelt werden.