Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Große Datenmenge wie speichern (HashMap? TreeMap?)
Aus einem großen Text werden alle Tokens (d.h. in etwa Wörter) eingelesen und mit der Häufigkeit ihres Auftretens gespeichert. Bisher habe ich dafür eine HashMap genommen. Beim Testen mit größeren Dateien funktioniert das aber nicht mehr, bei 5,5 Millionen Tokens (nicht: 5,5 Millionen Key-Value-Paare, damit könnte ich leben) ist quasi Schluss und die Performance des einlesens geht gegen null.
Ich vermute, dass zu viele Rehashes nötig waren und so das Einfügen neuer Elemente zu lange dauert.
Nun habe ich nach Lösungen gesucht und zwei mögliche gefunden:
- Ich verwende eine TreeMap. Laut API wird hier ein Zeitaufwand von log(n) garantiert.
- Ich verwende weiterhin eine HashMap, setze aber die initiale Kapazität und möglicherweise auch den load factor hoch an. Der Platzbedarf ist kein Problem: Das Programm soll nur alle Jubeljahre mal laufen.
Welche Variante ist zu empfehlen? Ich frage mich insbesondere, warum man nicht einfach immer eine TreeMap nehmen sollte und wie der Zeitaufwand der Hashmap aussieht, wenn ich genug Kapazität zuteile und so Rehashes vermeide.
Wenn ich die Daten habe, muss ich sie übrigens in beliebiger Reihenfolge abbarbeiten. Für die weiteren Operationen ist es also nicht notwendig, dass ich sortierten Zugriff auf die Schlüssel-/ Wertepaare erhalte.
Naja, das laesst sich doch einfach ausprobieren? Die zweite Variante ist einfach nur ein anderer Konstruktor-Aufruf und die erste klappt mit einer Zeile Aenderung, wenn du immer mit dem Map-Interface arbeitest.
- ich würde gerne verstehen, warum eine Variante besser ist (mich irritiert die angeblich garantierte logarithmische Zeitaufwand der TreeMap)
- auch ein passender Algorithmus braucht für eine Anwendung dieser Größenordnung ein Weilchen
- der Rechner mit dem Programm ist grade nicht verfügbar ;-)
M.W. ist schneller als logarithmisch nicht drin, dabei sollte doch die - unsortierte - HashMap beim Einfügen (und das ist doch mit 'put' gemeint, oder?) schneller als die sortierte TreeMap sein.
"Konstant" (O(1)) ist schneller als Logarithmisch (O(log(n)). Wenn man bei einer TreeMap ein "put" macht, wird der Baum bis zu den Blättern durchsucht, und dort im passenden Blatt der neue Knoten eingefügt. Bei der HashMap wird (auf Basis des Hash-Wertes des Objekt) direkt die Position ausgerechnet, wo das Objekt eingefügt werden muss.
Falls ich das richtig verstanden habe, machst du jetzt sowas wie
Code:
for (all tokens t)
{
if (map.containsKey(t)) map.put(t, map.get(t)+1);
else map.put(t, 1);
}
Da sollte die Anzahl der Tokens auf die Performance des Einfügens keinen Einfluß haben. Man könnte überlegen, ob man sich eine counter-Klasse macht
Code:
for (all tokens t)
{
Counter counter = map.get(t);
if (counter != null)
{
counter.increase();
}
else map.put(t, new Counter());
}
um das Automboxing zu sparen, aber das hat auf die asymptotische Zeit auch keinen Einfluß.
Bist du sicher, dass nicht das Einlesen selbst so lange dauert?
Danke, da hatte ich einen Denkfehler (konstant vs. log)
Ich mache bisher sowas, wobei der Code nach der While-Schleife nicht erreicht wird. Sprich: Hier liegt das Performance-Problem:
Code:
HashMap count = new HashMap()
while (tokens im input) {
String token = nächstes token im input
print (jedes 100 000. token); // bis 5,5 Millionen geht das schnell, dann Einbruch
if (count[token] == null)
count[token] = 0;
count[token]++
}
Die Fragen, wie du die Tokens liest (d.h. ob es vielleicht DAran liegt) und wie genau die die Werte in die Map legst, sind damit aber nicht beantwortet.
ich konnte jetzt nochmal testen. Zunächst lief es mit TreeMap deutlich schneller, aber bei 5,5 Mio. Tokens (was hier etwa 300000 Types, also Einträgen in der Map, entsprach) kam es zu Performanceeinbußen. Bei 6 Mio. Einträgen gab es dann eine Exception, da der Speicher ausging.
Nachdem ich der JVM mehr Speicher gegeben habe, läuft es jetzt problemlos und mit der HashMap etwas schneller.
Das Einlesen geschieht übrigens wie folgt (ist Groovy-Code, was sich hier aber nur in der kürzeren Deklaration der Variablen niederschlägt):
Code:
def FileReader fr = new FileReader(this.file)
def reader = new BufferedReader(fr)
def p = java.util.regex.Pattern.compile(/[,+()"'<>\[\]\s]/)
def sc = new Scanner (reader)
sc.useDelimiter(p)
while (sc.hasNext()) {
OK, wenn's zwischen 5.5M und 6M auf einmal kracht, könnten einige Geschwindigkeitseinbußen vorher schon mit dem Speichermangel zusammengehongen haben.
Mit Groovy kenne ich mich nicht aus. Was der Scanner mit dem Delimiter genau macht, weiß ich auch nicht. Falls er da bei jedem "getNext"-Aufruf irgendein RegEx-Pattern-Matching durchführt, könnte man das evt. deutlich beschleunigen, aber dazu müßte ich mir erstmal den Scanner-Code ansehen (bin im Moment aber an einem JDK-losen Rechner)
@Marco: Der Scanner kommt von Java. Mit this.file wird hier auf eine txt-Satei zugegriffen, darauf wird dann ein BufferedReader* erstellt.
Der Scanner holt dann aus diesem Datenstrom jeweils ein Token. Tokens sind definiert als die Zeichengruppen _zwischen_ den unterschiedlichen, durch den RegEx spezifizierten Delimitern (Whitespace, Anführungszeichen, Klammern usw.)
*Hier werde ich auch nochmal mit der Puffergröße experimentieren.
package wordcounter;
import java.io.*;
/**
* @author ark
*
*/
public final class StringTree{
private static final class Node{
public char character;
public int count;
public Node brother;
public Node child;
public Node(){
// nur zwecks public-Deklaration
}
}
private PushbackReader r;
// Die wohl wichtigste Eigenschaft:
private Node tree;
// Hier wird ein Bitmuster über alle Trennzeichen (Unicode)
// aufbewahrt. Die Ordnung der Bits folgt der Little-Endian-Idee, wobei
// gesetzte Bits Trennzeichen darstellen.
private int[] delimiter=new int[2048];
// Folgende Eigenschaften werden nur intern zur Verarbeitung über
// Methodengrenzen hinweg genutzt, um Parameterübergaben zu ersparen.
private char curr;
private StringBuilder sb;
public StringTree(Reader r,char[] delimiter){
this.r=new PushbackReader(r,1);
tree=new Node();
// Hier werden die entsprechenden Bits gesetzt, um später mit O(1)
// entscheiden zu können, ob ein Zeichen Begrenzer ist oder nicht.
char c;
for(int i=0;i<delimiter.length;i++){
c=delimiter[i];
this.delimiter[c>>>5]|=1<<c;
}
// Zur Wortbegrenzung würde ich spontan das folgende Muster verwenden,
// aber natürlich kenne ich die gestellten Anforderungen nicht.
// Begrenzer sind hier alle Zeichen <=0xFF, die nicht Buchstabe und
// nicht Ziffer sind. Wenn dir dieses Muster gefällt, brauchst du
// nur das Codestück über diesem Kommentar auszukommentieren und
// stattdessen das folgende verwenden:
// this.delimiter[0]=0xFFFFFFFF;
// this.delimiter[1]=0xFC00FFFF;
// this.delimiter[2]=0xF8000001;
// this.delimiter[3]=0xF8000001;
}
// Hier kannst du den Baum beim Aufbauen bewundern.
public void buildTree() throws IOException{
int c;
while(true){
if((c=r.read())<0) return;
r.unread(c);
put(tree);// Der erste Buchstabe eines Wortes wurde gefunden.
}
}
private void put(Node node) throws IOException{
while(true){
if(!next()){
node.count++;
//System.out.println("\t"+node.count);// bisher gezählt
return;
}
//System.out.print(curr);// aktuell besuchtes Zeichen
if(node.child==null){
node.child=new Node();
node.child.character=curr;
node=node.child;
continue;
}
node=findMatchingBrother(node.child,node);
}
}
// Ein Knoten kennt nicht alle Kinder, wohl aber ein Kind und dieses alle
// seine Geschwister. Dabei wird deren Reihenfolge schön sortiert gehalten.
private Node findMatchingBrother(Node brother,Node parent){
if(brother.character>curr){
parent.child=new Node();// voranhängen
parent.child.character=curr;
parent.child.brother=brother;
return parent.child;
}
while(brother.character<curr){
if(brother.brother==null){
brother.brother=new Node();// ans Ende hängen
brother.brother.character=curr;
return brother.brother;
}
parent=brother;// nur als Platzhalter bedient
brother=brother.brother;
if(brother.character>curr){
parent.brother=new Node();// dazwischenhängen
parent.brother.character=curr;
parent.brother.brother=brother;
return parent.brother;
}
}
return brother;// existiert bereits
}
// Diese kleine Hilfsmethode holt das nächste Zeichen und gibt true zurück,
// wenn es den Anforderungen an ein Wort genügt.
private boolean next() throws IOException{
int x=r.read();
char c=(char)x;
if(x<0||((delimiter[c>>>5]&1<<c)!=0)){
return false;
}
curr=(char)x;
// Wenn Groß-/Kleinschreibung ignoriert werden soll, musst du
// stattdessen die folgende Zeile verwenden. Die Wörter können dann
// aber freilich nicht mehr 1:1 wiedergegeben werden.
// curr=Character.toLowerCase((char)x);
return true;
}
// gibt den gesamten Baum aus
public void printResult(){
sb=new StringBuilder();
printNode(tree.child);// die Wurzel hat nur alle Trennzeichen gezählt
sb=null;
}
private void printNode(Node node){
sb.append(node.character);
if(node.count>0){
StringBuilder tempsb=new StringBuilder(
sb.length()+1+(int)Math.ceil(Math.log10(node.count)+1)
);
tempsb.append(sb).append("\t").append(node.count);
System.out.println(tempsb.toString());
}
if(node.child!=null){
printNode(node.child);
}
sb.deleteCharAt(sb.length()-1);
if(node.brother!=null){
printNode(node.brother);
}
}
// Hier wird der gesamte Baum in die Luft gejagt
// (also alle Kanten werden entfernt).
public void dispose(){
disposeNode(tree);
}
private void disposeNode(Node node){
if(node.child!=null){
disposeNode(node.child);
node.child=null;
}
if(node.brother!=null){
disposeNode(node.brother);
node.brother=null;
}
}
// zum Test
public static void main(String[] args) throws Exception{
char[] delimiter=new char[]{
'[',',','+','(',')', '\"','\'','<','>','[',']',
' ','\t','\n','\u000B','\f','\r'
};
Reader r=new FileReader("src/wordcounter/StringTree.java");// UTF-8
StringTree stree=new StringTree(r,delimiter);
stree.buildTree();
r.close();
stree.printResult();
stree.dispose();
}
// Methoden zum Einfügen, Löschen und Zählen eines einzelnen Wortes
// kannst du ja dann selbst implementieren. ;-)
}
Lies dir vor Verwendung bitte auch die Kommentare durch, sie könnten interessant sein.
Die Idee hinter diesem Algorithmus ist folgende: Die Reihenfolge der Zeichen im String mit den Zeichen selbst gibt den Pfad an, über den man das entsprechende Wort findet. Wenn z.B. zuerst das Wort
DES
hinzugefügt wird, sieht der entsprechende Pfad im Baum so aus (Anzahl in eckigen Klammern):
D[0] -> E[0] -> S[1]
Wenn jetzt das Wort
DESSEN
hinzugefügt wird, erweitert sich der Baum wie folgt:
D[0] -> E[0] -> S[1] -> S[0] -> E[0] -> N[1]
Leider habe ich bis heute nicht verstanden, wie ein Rot-Schwarz-Baum funktioniert, geschweige denn, wie man ihn implementiert. Aus diesem Grund erfolgt die Suche nach dem passenden Bruder in einer (sortiert gehaltenen) verketteten Liste, also mit O(n) und nicht mit O(log n). Wenn du Lust, Laune, Zeit und das notwendige Know-How hast, kannst du ja einen speziell an die Bedürfnisse angepassten Rot-Schwarz-Baum verwenden. Interesse an einer solchen Implementierung habe ich dann natürlich auch.
Ich bitte um Feedback (Fehler dürfen natürlich auch gemeldet werden ) und hoffe, dass damit das Problem gelöst ist. (Ich weiß ja nicht, wie die Verteilung ist. Der Algorithmus arbeitet um so speicherschonender, je länger das Präfix eines Tokens ist, das (Präfix) mit dem Präfix der bisher eingefügten Tokens übereinstimmt. Wenn also vorrangig die Suffixe gleich sind, müsste man an den entsprechenden Stellen anders herum arbeiten bzw. aus dem Stream rückwärts lesen. Wenn man Aussagen über die Anzahl "erlaubter" Zeichen machen kann, kann nötigenfalls von char auf byte reduziert werden, um Speicherplatz zu sparen. Auch eine Verkleinerung der Zählvariablen von 32 auf 24 oder sogar nur 16 Bit wäre denkbar, wenn nötig.)
Ark
EDIT: Ich habe in der Methode dispose() die Zeile herausgenommen, die die Wurzel entfernt hat. Nach Aufruf von dispose() kann der Baum also wiederverwendet werden. Eine Methode, die einen neuen Reader einsetzt, musst du dann noch selbst implementieren, falls du über mehrere Dateien hinweg zählen willst.
EDIT2: Mir ist noch etwas eingefallen, um schonender mit dem Speicher umzugehen. Allerdings würde dann auch Abfall produziert (was bei der momentanen Implementierung der Fall ist). Falls also noch immer der Speicher knapp werden sollte: Es besteht noch immer Optimierungspotential. Allerdings sieht dann der Worst Case speicherplatztechnisch sogar schlechter aus; die von mir gerade angedachte Optimierung ist also nur bedingt eine Optimierung.
