Häufigkeit der Werte in Datei zählen! Heap Space beschränkt!

[lesi]

Hallo,

folgendes Problem:

Ich möchte möglichst effizient das Vorkommen, also die Häufigkeit gleicher Werte in einer sehr grossen Datei (ca. 500 MB) bestimmen. Die Datei einzählt ca. 2 Millionen gleiche einfache Zahlen bie einer Gesamtzahl von ca. 50 Millionen Zahlen.

Die Datei ist dabei so aufgebaut:

.....
865531667
396993597
601196596
6289283
206531325
556596040
920326407
.....

Die Zahlen haben also eine unterschiedliche Länge.

Wenn zwei Zahlen gleich sind, so erfolgt eine Ausgabe in der Form

.....
865531667 = 2
.....

Wenn drei Zahlen gleich sind, dementsprechend:

.....
865531667 = 3
.....

Das komplizierte an der Sache ist, dass der Heap-Space nur einen bestimmten Speicherplatz einnehmen darf (in diesem Fall maximal 50 MB, also "-Xmx50m").

Was ist am sinnvollsten? Da es 2 Millionen gleiche Zahlen sind, muss also nur gezaehlt werden welche Zahl wie oft vorkommt. Welche Datenstruktur kann man dafuer am Besten nehmen?? Wie baut man das am Besten auf?

Ich habe schonmal ein wenig ausprobiert, leider war es mir nicht moeglich eine Implementierung zu finden, die mit einem so geringen Heap Space arbeitet, aber hier trotzdem meine Lösung:

 public void haeufigkeit() throws Exception 
    {  
    	FileReader fr = new FileReader("datei");
	BufferedReader bf = new BufferedReader(fr);

    	try 
    	{
    		String zeile; 

    		// heap muss auf 50 mb gesetzt werden ("java.exe -Xmx50m")

    		HashMap zahlen = new HashMap(); 

    		while ( (zeile=bf.readLine()) != null) {
    			Anzahl anzahl = (Anzahl) zahlen.get(zeile);
    			 
    			if (anzahl == null) {
    				anzahl = new Anzahl();
    				zahlen.put(zeile,anzahl);
    			}
    			((Anzahl)zahlen.get(zeile)).zaehler++;
    			System.out.println(zeile + ", " + ((Anzahl)zahlen.get(zeile)).zaehler);
    		}
    		
    		System.out.println("File-Evaluation done");
    		    		
    	} 
    	catch(Exception e) 
    	{ 
    		System.err.println(e.getMessage()); 
    	} 
    	finally 
    	{ 
    		if(bf!=null) try { bf.close(); } catch(Exception e) {}
    	}

Dieser Code kommt mit dem Heap nicht klar, es kommt eine Outofmemory-Exception? Was kann man machen? Danke.

 

[bygones]

ich würde keine eigene datenstruktur nehmen. probiers mit einer Map Implementierung. Key ist die Nummer, Value die Häufigkeit.

andere Möglichkeit. Jede Zahl repräsentiert ein File. in dem File steht die Häufigkeit.. neue Zahl -> neue Datei. bekannte Zahl (file existiert) -> neue Zahl reinschreiben.

Ist umständlich, braucht aber im Grunde null Speicher....

 

[Guest]

Verwende java.lang.Integer als Key in dem Map, statt Strings.
Die Zähler auch als Integer und verwende diese immer wieder.

Die Klasse Integer ist so implementiert, dass Werte im Bereich -128 und 128
gecached werden. Mit z.B. Integer.valueOf(5) kriegst du eine gecachte Instanz,
kein neues Objekt.

 

[Guest]

:autsch: -128 bis 127

 

[byte]

hm bei 2 mio zahlen (wenn ich das oben richtig gelesen habe) wären das aber ne menge dateien.

 

[Guest]

Noch etwas, wenn Du die Zahlen ausliest, passt socher ein grosser Anteil davon
in den Zahlenbereich von java.lang.Short. Die Zähler werden oft auch nicht die
256 überschreiten, daher Byte, Short und Integer.
Das ergibt dann ein HashMap mit folgendem Inhalt

Key       Zähler

Integer   Byte
Short     Byte
Integer   Short
Byte      Byte
Short     Byte
Byte      Short
usw.

 

[messi]

Schreib eine eigene Hashtable-Implementierung mit zwei Feldern: Zahl (long?) und Zähler (int?). Beide zusammen sollten anfangs schon die 50mb ausnutzen, damit du nicht kopieren und neu hashen musst. Benutze keine Maps aus java.util, weil du immer Objekte als Schlüssel und Wert nehmen musst.

 

[Guest]

Verwende java.lang.Integer als Key in dem Map, statt Strings.
Die Zähler auch als Integer und verwende diese immer wieder.

wie funktioniert das dann mit dem readline ?

 

[Guest]

Verwende java.lang.Integer als Key in dem Map, statt Strings.
Die Zähler auch als Integer und verwende diese immer wieder.

wie funktioniert das dann mit dem readline ?

Einfach String zu Integer konvertieren.
Schau Dir am besten die Klasse java.util.Scanner an.

 

[meez]

Verwende java.lang.Integer als Key in dem Map, statt Strings.

Warum denn...Strings werden ja auch in einem Pool gehalten...

 

[Guest]

Es geht um die Länge der Strings gegenüber einem Integer/Short/Byte in Bytes gezählt.

 

[Gast]

gut, danke schonmal ... 650000 Zahlen schafft er mit einer heapsize von 50 MB .. kann man da noch irgendwie mehr rausholen?

    public void häufigkeit() throws Exception 
    {  
    	FileReader fr = new FileReader("etl");
		BufferedReader bf = new BufferedReader(fr);
    	try 
    	{
    		HashMap zahlen = new HashMap(); 
    		Integer zeile;

    		//int count = 0;
    		
    		while ((zeile=new Integer(bf.readLine())) != null) {
    			
    			Anzahl anzahl = (Anzahl) zahlen.get(zeile);

    			//System.out.println(count + ": " + zeile); // 650038: 40895988
    			 
    			if (anzahl == null) {
    				anzahl = new Anzahl();
    				zahlen.put(zeile,anzahl);
    			}
    			((Anzahl)zahlen.get(zeile)).zaehler++;
    			System.out.println(zeile + ", " + ((Anzahl)zahlen.get(zeile)).zaehler);
    			//count++;
    		}
    		
    	    
    		System.out.println("File-Evaluation done");
    		    		
    	} 
    	catch(Exception e) 
    	{ 
    		System.err.println(e.getMessage()); 
    	} 
    	finally 
    	{ 
    		if(bf!=null) try { bf.close(); } catch(Exception e) {}
    	} 
	}
	
    
    class Anzahl { 
   
    		int zaehler = 0; 
	}

 

[Gast]

nein, das ist nicht gut in der form ... ich habe gerade erst begriffen, dass er so den gesamten file einliesst und auch doppelte zahlen mit der jeweiligen aufaddierung darstellt.

also:

....
1, 1 mal
2, 1 mal
4, 1 mal,
3, 1 mal,
1, 2 mal,
1, 3 mal,
5, 1 mal,
2, 2 mal
...

und so weiter ... das ist nicht sinn der sache ...

das programm sollte moeglichst effizient
....
1, 3 mal,
2, 2 mal,
3, 1 mal,
4, 1 mal,
5, 1 mal
...
ausgeben...

vielleicht ideen? danke?

 

[Guest]

Berechne mal das Worst-Case-Szenario. 2 * 50 Millionen Integer (Zahl und Zähler).
Mit den 50MB kommst du nie hin.

 

[Gast]

das ist mir schon klar.

darum geht es auch nicht, es geht darum 2 millionen zahlen und 2 millionen zaehler (es sind also viele doppelte zahlen vorhanden) darzustellen.

 

[na-oma]

mhh...
"2 Millionen gleiche einfache Zahlen" d.h. das wären
4 mio integer, das bekommt man mit 50 MB schon hin(wenn man keinen zusätzlichen speicher zur verwaltung braucht)

50 MB sind 1024*1024*8*50=419 430 400 bit. bei 32 bit pro Int sind das ca. 13 Mio Zahlen. Müsste also gehen.

In der Java-Klasse Integer sind ausser

private final int value;

keine weiteren nicht-statischen Felder enthalten, also müsste ein Integer-Objekt in der Theorie nur 32 bits Speicher brauchen. Allerdings weiss ich nicht, wieviel Overhead Java hinzufügt.

Deine Klasse Anzahl sollte auch nur 32 bit verbrauchen...

Einen Knackpunkt sehe ich allerdings:

Wenn du eine Hashmap (die als Array implementiert ist) dauernd vergrößerst, muss sie bei jeder Vergrößerung kopiert werden. Das heisst, wenn dein Speicher > halb voll ist, kannst du sie nicht mehr weiter vergrößern, da sie nicht mehr zu kopieren geht. Deshalb steht dir effektiv nur 25 MB Speicher zur verfügung, bei der nächsten Vergrößerung is Sense.
Das würden immernoch 6 553 600 Integer sein. immernoch das 10fache deiner angegeben max-zahl.

Hah ich habs:

Um das ständige Kopieren zu vermeiden nimmst du:

public HashMap(int initialCapacity)

d.h. du schreibst:

HashMap zahlen = new HashMap(2 000 000);

wenn er sich jetz schon über die größer der HashMap beschwert kannste die HashMap wohl für deine Zwecke vergessen. jedenfalls vermeidest du damit das ständige Vergrößern & Kopieren des Arrays der HashMap.


Wenn das allerdings geht...dann solltest du wirklich an Shorts als Zähler denken...oder irgendwie die Größe deiner Variablen reduzieren.

 

[na-oma]

Wenn du allerdings das ganze nicht speichern willst, sondern nur geordnet ausgeben, dann machst du einfach folgendes:

aktuellezahl = 999999999999
anzahl = 0
max = 999999999999
min = 0

do {
  aktuellezahl = 999999999999
  anzahl = 0
  gehe durch datei {
      wenn zeile < aktuellezahl && zeile > min { aktuellezahl = zeile; anzahl = 1 }
      wenn zeile == aktuellezahl : anzahl++
  }

  ausgeben (aktuellezahl  " ist " anzahl "mal vorhanden")
  min = aktuellezahl
} while(aktuellezahl < max) //sonst alle durch

is zwar dodal unperformant, aber braucht keinen speicher

p.s. @Speicher...ich hoffe, es liegt nicht an der Datei die geöffnet ist. Wenn die komplett im Speicher liegt?? weiss nicht wie die Dateioerationen implementiert sind, und kein bock nachzuschaun...

 

[Guest]

Das hier sollte funktionieren. Bedenke aber das HashMap intern mit Map.Entry Objekten arbeitet,
die wieder Platz kosten, dafür aber eine sau schnelle Verarbeitung ermöglichen.

Short one = Short.valueOf((short)1);
HashMap<Integer,Short> map = new HashMap<Integer,Short>(2000000,0.9f);
String line;
while((line=in.readLine()) != null) {
  Integer nn = Integer.valueOf(line);
  Short cc = map.get(nn);
  map.put(nn, (cc==null)?one:Short.valueOf((short)(cc.shortValue()+1)));
}

Den Code von java.util.HashMap muss man erst verstehen. ???:L

 

[messi]

Schon mal mit TreeMap probiert?

Im Übrigen werden in der Sun JVM Objekte im Heap in 8-Byte-Blöcken abgelegt. (8 bytes alignment). D. h. es spielt keine Rolle, ob ihr mit java.lang.Long, Integer oder Short rummokelt. Allein java.lang.Object belegt schon 8 Byte -> für Long/Integer/Short/Byte braucht ihr je 16 Byte. Andere JVMs kenne ich aber nicht.

Wie schon oben gesagt: Schreibe eine eigene Datenstruktur, die direkt die Zahlen und die Zähler direkt in Felder abspeichert. Entweder als Hashtable oder falls Geschwindigkeit nicht das Problem ist, dann sortiere die Zahlen in das Feld hinein.

Ansonsten benutze - wie auch schon vorgeschlagen - das Dateisystem als Datenstruktur. Damit nicht zu viele Zahlen im gleichen Verzeichnis stehen, kannst du noch Unterverzeichnisse anlegen und dort ablegen, je nachdem wie die Zahl beginnt. File f = new File("zahlen/8/85/85138765"); usw.

 

[Bleiglanz]

angenommen die erste zahl ist gleich der 50.000.000sten zahl (und die kommt sonst nirgendwo vor)

das kannst du nur erkennen, wenn du JEDE Zahl zwischenspeicherst!

du bräuchtest also (wenn alle zahlen <Integer.MaxValue sind) ein

int[] array = int[50000000] // 50 Millionen * 4 Bytes = 200 MB, könnte noch gehen bei genügend ram

und wenn du eine Zahl x liest, dann machst du array[x]++ (danach sind 48000000 Einsen drin und zwei Millionen Zahlen > 1)

die Alternative mit der Map würde ich nicht empfehlen

weil da ja für Key und Value jeweils eine Objektreferenz dazukommt, also ebenfalls 2 * 2 * 50Mio Bytes benötigt werden ( und du ständig nachschauen musst mit contains, ob ein key schon drin ist, was sehr langsam sein könnte)

 

[messi]

angenommen die erste zahl ist gleich der 50.000.000sten zahl (und die kommt sonst nirgendwo vor)
das kannst du nur erkennen, wenn du JEDE Zahl zwischenspeicherst!
du bräuchtest also (wenn alle zahlen <Integer.MaxValue sind) ein
int[] array = int[50000000] // 50 Millionen * 4 Bytes = 200 MB, könnte noch gehen bei genügend ram
und wenn du eine Zahl x liest, dann machst du array[x]++ (danach sind 48000000 Einsen drin und zwei Millionen Zahlen > 1)

Es gibt "nur" 2.000.000 unterschiedliche Zahlen. Das Feld wäre dann 8 MB. Und es spricht auch niemand davon, dass die Zahlen als Feldindex benutzt werden sollen, da sie viel zu groß sind: z.B. 865.531.667. (siehe ersten Post)

int[] zahlen = new int[2E6];
int[] zähler = new int[2E6];
int länge = 0;
...
{
    ...
    int index = 0;
    while (index < länge && x != zahlen[index])
        index++;

    if (index == länge) {
        zahlen[länge] = x;
        zähler[länge]++;
        länge++;
    } else {
        zähler[index]++;
    }
}
...

Das ist natürlich langsam: O(n log n). Schneller geht es, wenn man die Zahlen einsortiert.

 

[Guest]

Das hier sollte funktionieren. Bedenke aber das HashMap intern mit Map.Entry Objekten arbeitet,
die wieder Platz kosten, dafür aber eine sau schnelle Verarbeitung ermöglichen.

Short one = Short.valueOf((short)1);
HashMap<Integer,Short> map = new HashMap<Integer,Short>(2000000,0.9f);
String line;
while((line=in.readLine()) != null) {
  Integer nn = Integer.valueOf(line);
  Short cc = map.get(nn);
  map.put(nn, (cc==null)?one:Short.valueOf((short)(cc.shortValue()+1)));
}

Den Code von java.util.HashMap muss man erst verstehen. ???:L

interessanter Ansatz! doch wie funktioniert das casting des Short? (Zeile: Short cc = map.get(nn)

 

[Guest]

Das hier sollte funktionieren. Bedenke aber das HashMap intern mit Map.Entry Objekten arbeitet,
die wieder Platz kosten, dafür aber eine sau schnelle Verarbeitung ermöglichen.

Short one = Short.valueOf((short)1);
HashMap<Integer,Short> map = new HashMap<Integer,Short>(2000000,0.9f);
String line;
while((line=in.readLine()) != null) {
  Integer nn = Integer.valueOf(line);
  Short cc = map.get(nn);
  map.put(nn, (cc==null)?one:Short.valueOf((short)(cc.shortValue()+1)));
}

Den Code von java.util.HashMap muss man erst verstehen. ???:L

interessanter Ansatz! doch wie funktioniert das casting des Short? (Zeile: Short cc = map.get(nn)

Suche mal nach "Generics", dann weisst du mehr.

 

[Guest]

interessanter Ansatz! doch wie funktioniert das casting des Short? (Zeile: Short cc = map.get(nn)

Suche mal nach "Generics", dann weisst du mehr.[/quote]

danke, das wusste ich nicht. wie sieht der code denn mit einer jvm < 5.0 aus?

 

[messi]

danke, das wusste ich nicht. wie sieht der code denn mit einer jvm < 5.0 aus?

HashMap map = new HashMap(2000000,0.9f);
...
Short cc = (Short) map.get(nn);

 

[lesi]

Hallo,

erstmal danke für die zahlreichen Antworten - habe gerade alles mal überflogen und werde heute Abend alle Vorschläge im Detail durchgehen.

Short one = Short.valueOf((short)1); 
HashMap<Integer,Short> map = new HashMap<Integer,Short>(2000000,0.9f); 
String line; 
while((line=in.readLine()) != null) { 
  Integer nn = Integer.valueOf(line); 
  Short cc = map.get(nn); 
  map.put(nn, (cc==null)?one:Short.valueOf((short)(cc.shortValue()+1))); 
}

Dieser Vorschlag scheint auf die Schnelle 1,6 Millionen Zahlen bei 50 MB Heap processen zu können, doch wie sieht es mit der Speicherung von Zahlen aus, die doppelt vorkommen? So läuft er einfach nur einmal durch und stellt doppelte und mehrfache Zahlen immer wieder dar?

 

[na-oma]

in dieser Zeile:

map.put(nn, (cc==null)?one:Short.valueOf((short)(cc.shortValue()+1)));

wird das gemacht: wenn die zahl noch nicht in der Map ist, wird one (=1 siehe weiter oben) unter der Zahl nn in der Map gespeichert. ansonsten wird eins addiert und noch etwas rumgecastet

ich würde übrigens

so schreiben:

Short one = Short.valueOf((short)1);
HashMap<Integer,Short> map = new HashMap<Integer,Short>(2000000,0.9f);
String line;
Integer nn;
Short cc;
while((line=in.readLine()) != null) {
  nn = Integer.valueOf(line);
  cc = map.get(nn);
  map.put(nn, (cc==null)?one:Short.valueOf((short)(cc.shortValue()+1)));
}

dies vermeidet zwar wahrscheinlich keine Speicher Allokation auf dem Heap, allerdings müssen nicht dauernd neue referenzen auf Integer.valueOf(line) und map.get(nn) bzw. die sich dahinter versteckenden werte angelegt werden.
Das sollte etwas schneller gehen.

 

[messi]

ich würde übrigens so schreiben:

Short one = Short.valueOf((short)1);
HashMap<Integer,Short> map = new HashMap<Integer,Short>(2000000,0.9f);
String line;
Integer nn;
Short cc;
while((line=in.readLine()) != null) {
  nn = Integer.valueOf(line);
  cc = map.get(nn);
  map.put(nn, (cc==null)?one:Short.valueOf((short)(cc.shortValue()+1)));
}

dies vermeidet zwar wahrscheinlich keine Speicher Allokation auf dem Heap, allerdings müssen nicht dauernd neue referenzen auf Integer.valueOf(line) und map.get(nn) bzw. die sich dahinter versteckenden werte angelegt werden.
Das sollte etwas schneller gehen.

Irrelevant. Im schlimmsten Fall wird der Stack Pointer ständig vergrößert und verkleinert. Aber halbwegs gute Compiler optimieren sowas. Außerdem ist es schlechtes Design, wenn lokale Variablen nach ihrer Nutzung noch gültig sind.

 

[Guest]

Irrelevant. Im schlimmsten Fall wird der Stack Pointer ständig vergrößert und verkleinert. Aber halbwegs gute Compiler optimieren sowas. Außerdem ist es schlechtes Design, wenn lokale Variablen nach ihrer Nutzung noch gültig sind.

Du hast recht, es ist schlechtes Design, das ging mir auch durch den Kopf. Ich muss zugeben, dass ich nicht weiss, wieviel CPU-Zeit durch das ständige anlegen und löschen der Referenzen auf dem Stack verlohren geht. Habe da keinen Maßstab, aber wenn du sagst, dass es irrelevant ist, vertraue ich dir da mal.

ot: man könnte natürlich sowas machen:

{
  Integer nn;
  Short cc;
  while((line=in.readLine()) != null) {
    nn = Integer.valueOf(line);
    cc = map.get(nn);
    map.put(nn, (cc==null)?one:Short.valueOf((short)(cc.shortValue()+1)));
  }
}

um das Design zu verbessern...verschlechtert aber die Lesbarkeit. Warum hat sich noch keiner nen while-konstrukt einfallen lassen, indem man beliebige Variablen definieren kann, die nachher wieder gelöscht werden?
mhh wahrscheinlich weil sie uns anhalten wollten eine Funktion zu nehmen...

 

[lesi]

Ist es denn in diesem Zusammenhang möglich eine _Liste_ mit den entsprechenden einfach und mehrfach gefundenen Zahlen _auszugeben_, OHNE dabei mehrfache Zahlen (mit jeweils inkrementiertem Zähler) zu wiederholen, sondern, so gesehen nur einmal den Wert + letzten Stand des Zählers?

Zusätzlich stellt sich mir die Frage, ob eine solche Liste den Heap in irgendeiner Form mitbelastet?

 

[Guest]

for(Map.Entry<Integer,Short> e : map.entrySet()) {
  ausgabe(e.getKey(), e.getValue());
}

Sag' jetzt aber nicht, die Ausgabe soll auf dem Bildschirm erfolgen. :autsch:

 

[lesi]

Zugegebenermassen eine wirklich sehr intelligente Lösung.

Ich werde es jetzt auch nochmal mit weiteren Datenstrukturen ausprobieren und die Perforamce vergleichen.

In jedem Fall Danke ich messi, na-oma, bleiglanz und den Gästen für die hilfreiche Partizipation!!!