Für eine meiner Anwendungen muss die folgende Funktion sehr oft aufgerufen werden. Diese Funktion beansprucht viel CPU und ich frage mich, ob Sie wissen, wie Sie die Leistung verbessern können.
Der Code zählt das Auftreten einer Kombination von vier Zeichen. Während des Tests habe ich festgestellt, dass die Anzahl der Einträge in der Map ungefähr 100 beträgt. Die Länge von text liegt im Bereich von 100 bis 800. Die anfängliche Größe von 200 ist eine Schätzung und der Code scheint es zu sein schneller ausführen als ohne Angabe einer Anfangsgröße. Es ist jedoch wahrscheinlich nicht der optimale Wert.
%Vor%Ich arbeite viel im NLP und maschinellen Lernen, also muss ich die ganze Zeit so etwas tun, und es gibt eine Tonne von Möglichkeiten für Optimierung.
Ein paar Punkte zu beachten:
Zunächst werden Sie von der Standardklasse JDK HashMap getötet. Es ist ein schöner Container für Allzweck-Computing, aber es ist schrecklich für High-Performance-Computing. Für jeden Eintrag in Ihre Sammlung (eine vierstellige Zeichenfolge (8 Bytes) und eine Ganzzahl (4 Bytes) wird die Standard-Java-HashMap verbrauchen:
Ihre kleinen 12 Bytes Daten werden also 64 Bytes. Und das ist bevor die HashMap ein Array von Hash-Werten zugewiesen hat, die während ihrer Suchoperationen verwendet werden. Denken Sie daran, dass all diese kleinen Objekte mehr Arbeit für den GC bedeuten, aber noch wichtiger, dass Ihre Objekte einen größeren Teil des Hauptspeichers umfassen und weniger wahrscheinlich in den CPU-Cache passen. Wenn Sie viele Cache-Fehler haben, verlieren Sie die Leistung.
HINWEIS: Ein Kommentator hat mich daran erinnert, dass alle Teilstrings dasselbe zugrunde liegende Zeichen-Array haben werden, was ein guter Punkt ist, den ich vergessen habe. Dies bedeutet jedoch, dass jeder Karteneintrag von 64 Byte auf 44 Byte reduziert wird. Was immer noch schade ist, wenn es nur 12 Bytes geben sollte.
Wenn Sie all diese Ganzzahlwerte boxen und auspacken, wird Ihr Code langsamer ausgeführt und verbraucht mehr Speicher. In den meisten Fällen interessiert uns das nicht, und die Vanilla-HashMap-Implementierung ist in Ordnung, selbst wenn es obligatorisch ist und die Speicherkapazität des Spiels gierig ist. Aber in Ihrem Fall, wenn dieser Code innerhalb einer engen inneren Schleife ausgeführt wird, würden wir lieber eine spezialisierte Klasse haben, die weiß, dass ihre Werte immer Ganzzahlen sind und die Notwendigkeit zum Boxen eliminiert.
Wenn Sie sich den JDK-Quellcode ansehen, werden Sie sehen, dass Ihr Code am Ende die Methoden hashCode() und equals() des Strings zweimal aufruft. Einmal für die map.get() und einmal für die map.put() . Es gibt jedoch eine andere Art von Sammlung namens HashBag , die Nachschlagen, Einfügen und Zählen von Inkrementierungen mit nur einer Suche durchführen kann. Eine "bag" -Kollektion ist ein bisschen wie ein "set", außer dass sie Duplikate enthalten kann, und sie verfolgt, wie viele Duplikate es gibt. Für jedes Ihrer Tetragramme würden Sie einfach bag.put(tetragram) aufrufen, ohne zuerst eine Anzahl abrufen und aktualisieren zu müssen. Leider gibt es im JDK keine Bag-Implementierungen, Sie müssen also eine solche finden oder sie selbst schreiben.
Glücklicherweise können Ihre Tetragramme verlustfrei als long -Werte kodiert werden (da jedes Java-Zeichen 2 Byte breit ist und ein long Ihnen acht Bytes zum Arbeiten gibt). Sie können daher das Zeichenarray durchlaufen und jedes Tetragramm in ein long umwandeln und den gesamten Aufwand für die Konstruktion so vieler kleiner Strings vermeiden. Dann können Sie Ihre Ergebnisse in einem LongIntHashMap (aus der Trove-Bibliothek) behalten. Dies wird viel schneller sein als Ihre aktuelle Implementierung, weil Sie vermeiden können, all diese winzigen kleinen String-Objekte zu erstellen.
Obwohl die Trove LongIntHashMap ziemlich gut ist, ist sie nicht ganz so gut wie LongHashBag . Es gibt keinen equals -Aufruf (da longs mit dem Operator == verglichen werden können), aber Sie zahlen immer noch den Preis von zwei hashCode -Aufrufen. Wenn Sie mit der Optimierung wirklich aggressiv werden wollen, können Sie sich den Quellcode von LongIntHashMap ansehen und herausfinden, wie Sie ihn in ein LongHashBag ändern können. Es ist nicht so schwierig und das ist genau das, was ich in meinem eigenen Code gemacht habe.
Okay, hier ist ein bisschen Code:
%Vor% Ich habe gerade verschiedene Lösungen getestet, und ich war dabei, eine 25% -ige Leistungsverbesserung zu erreichen, indem ich den LongHashBag -Ansatz anstelle des standardmäßigen HashMap -Ansatzes einsetze.
Ich war jedoch dabei, eine Verbesserung von 300% zu erzielen, indem ich die resultierenden Objekte recycelte. Grundsätzlich, anstatt dies zu tun:
%Vor%... Ich mache das jetzt ...
%Vor%Der aufrufende Code ist verantwortlich für das Erstellen des LongHashBag-Objekts und stellt sicher, dass wir damit fertig sind, wenn wir die Zählmethode erneut aufrufen.
Aber es würde auch funktionieren, das zu tun ...
%Vor%... was ein bisschen Overhead für die Wartung des Pools bedeutet. Und der Anrufercode muss sich daran erinnern, die Tasche wieder in den Pool zu legen, wenn sie sie benutzt.Aber die Leistungsvorteile könnten sich definitiv lohnen.
Das sind übrigens genau die Arten von Tricks, die ich jeden Tag benutze. Das Objekt-Pooling ist zu einem meiner zuverlässigsten Tricks geworden, um die Leistung zu verbessern.
Aber wie ich schon sagte, führt das Recycling dieser Objekte zu einer Leistungssteigerung von 300%.
Sie könnten versuchen, einen Präfixbaum (Trie) als Datenstruktur zu implementieren, insbesondere wenn Sie den Bereich des Figuren. Es würde höchstens 4 Ebenen tief sein und Ihnen potenziell konstante (und schnellere konstante) Zeit geben. Wie das im Vergleich zur Hashmappe funktioniert, hängt wirklich von den Daten ab, die Sie haben.
Bearbeiten
Alternativ können Sie, wenn Sie den Bereich der Zeichen kennen, sie einfach in einen viel schnelleren Datentyp stopfen.
Da Sie wissen, dass alle Ihre Zeichen zwischen A und Z oder 0 und 9 sind, können Sie das jeweils in 6 Bits komprimieren:
%Vor% Bearbeiten : Das obige Beispiel wurde aktualisiert, um A-Z, 0-9 abzudecken. Beachten Sie nun zwei Dinge: Zuerst müssen Sie ein großes Array erstellen, aber Sie müssen das nicht jedes Mal tun (Sie müssen es jedoch jedes Mal löschen!). Zweitens bietet dies eine sehr schnelle Suche nach der Anzahl der Vorkommen eines bestimmten Wortes, aber wenn Sie über alle Wörter iterieren wollen (sagen wir, um alle Wörter zu finden, die tatsächlich aufgetreten sind), dann dauert O(42^4) time.
Nun, eine mögliche Option besteht darin, von der Verwendung eines unveränderlichen Wrappertyps in einen veränderlichen zu wechseln:
%Vor%Ändern Sie dann Ihren Code zu:
%Vor%Auf diese Weise wird ein Wert nur einmal mit einem Wort verknüpft ... danach wird er in-place erhöht.
(Sie könnten möglicherweise AtomicInteger anstelle von Counter verwenden, wenn Sie einen integrierten Typ verwenden möchten.)
Neben der Big-O-Optimierung (falls vorhanden) gibt es eine sehr einfache Möglichkeit, Ihre Anwendung erheblich zu beschleunigen: Verwenden Sie etwas, das über die Standard-Java-APIs hinausgeht, die sehr langsam sind Umgang mit einem Los von Daten.
Ersetzen:
%Vor%Mit Troves (was bedeutet, dass Sie das Troj-Jar zu Ihrem Projekt hinzufügen müssen):
%Vor%Und:
%Vor%mit:
%Vor%Wenn Sie mit einer Menge an Daten arbeiten, ist die Verwendung von Wrappern wie Integer anstelle von Primitiven (wie int) und die Verwendung der Standard-Java-API der sicherste Weg, um sich in den Fuß zu schießen. p>
Ich habe noch nicht einmal damit begonnen, Ihren Code zu analysieren, und mir ist aufgefallen, dass diese Methode auf keinem Mitgliedsfeld funktioniert und statisch gemacht werden kann. Statische Methoden sind immer leistungsfähiger als nicht statische Methoden. Ich werde in einer Minute nach mehr Problemen suchen ...
Ich bin mir nicht sicher, ob das schneller wäre, aber ich habe das Gefühl, es wäre so.
%Vor%Je nachdem, was Sie mit der Map machen, wenn Sie fertig sind, brauchen Sie am Ende möglicherweise keine Konvertierung in eine Map.
Tags und Links algorithm java performance count hashmap