Häufigkeit der Werte in einer Datei zählen; Heap Size beschränken!

[lesezeichen]

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.

[Jaraz]

Hi,

wenn du nicht zwischendurch irgendwo speichern darfst, auf keinen Fall mit String bzw. Objekten, der Overhead eines Objects ist zu groß.

Gruß Jaraz

[lesezeichen]

Hi,

wenn du nicht zwischendurch irgendwo speichern darfst, auf keinen Fall mit String bzw. Objekten, der Overhead eines Objects ist zu groß.

Gruß Jaraz

genau, ohne zwischenspeichern.

ich dachte eher so an:

liste mit werten bereitstellen, datei einlesen, direkt vergleichen und dann zaehlen ...

doch wie moeglichst effizient?

[geloescht_Newlukai]

Ich weiß ja nicht, wie groß die Zahlen werden. Aber als "Trick" fiele mir da das hier ein:

long[] haufigkeiten = new long[Long.MAX]; //beim Lesen der Datei: 

haufigkeiten[ausgeleseneZahl]++;

Man hat keine Objekte, und trotzdem eine komfortable Zählmöglichkeit.

Greetz

Newlukai

[Jaraz]

long[] haufigkeiten = new long[Long.MAX];

Nur das das Array schon den Speicher killt.

Kannst ja mal bei dir versuchen so ein Array anzulegen.

Gruß Jaraz

[geloescht_Newlukai]

Damn. Hab' ich mir schon gedacht.

Dann könnte man noch eine Liste aus Objekten erstellen, was aber auch schon zu groß wird. Kann man nicht eine HashMap so "mißbrauchen", daß man die eingelesene Zahl direkt als HashCode verwendet und im zugehörigen Bucket die Anzahl als int sichert?

Als letztes fiele mir eine 2. Datei ein, in der Du die Zahlen mit der Anzahl sicherst, um den RAM-Bedarf sehr gering zu halten. Dann wird aber die Festplatte viel angestrengt.

[perdian]

long[] haufigkeiten = new long[Long.MAX];

Man hat keine Objekte, und trotzdem eine komfortable Zählmöglichkeit.

Du hast zwar keine Objekte, sondern nur primitive Typen, aber es ist falsch zu glauben, die würden keinen Speicher belegen.

Die Array-Deklaration da oben mag ja ganz harmlos aussehen, aber rechnen wir das mal durch:

Eine Variable vom Typ long benötigt 64bit. Da ein Array von primitiven Datentypen immer mit den ensprechenden 0-Werten vorbelegt wird, benötigen wir also für jeden Eintrag im Array eine entspreche long Variable.

Long.MAX = 9223372036854775807

Das heisst wir benötigen 9223372036854775807 * 64 bit Speicher.

Rechnen wir das mal durch :-)

9223372036854775807 * 64

= 590295810358705651648 Bit

= 73786976294838206456 Byte

= 72057594037927935 KByte

= 70368744177663 MByte

= 68719476735 GByte

= 67108863 TByte

= 65535 PByte

= 63 EByte

Selbst bei einem int[integer.MAX_VALUE] Array würde es bei einem Verbauch von knapp 8 GByte schon sehr eng werden, aber ich glaube die 63 EByte beim Long Array dürften auch beim momentanen Fortschritt noch eine ganze Weile unerreichbar bleiben

Back to Topic: Solange das Programm nicht innerhalb weniger Sekunden durchgelaufen sein muss würde ich den Weg über eine Datenbank gehen. Eine Tabelle erstellen, die zwei Felder hat "key" und "numberOfOccurences" und damit arbeiten. Wird zeitlich vielleicht etwas dauern, aber diesen Tradeoff muss man hinnehmen.

[Jaraz]

Wenn es maximal 2 Millionen unterschiedliche Werte sind, würde ein int (wenn int für den höchsten Wert reicht) Array mit 2 Millionen Einträgen und je nachdem wie häufig Werte vorkommen, ein byte, short oder int array mit ebenfalls 2 Millionen Einträgen reichen.

Allerdings musst du dann bei jeder Zeile im Schnitt 1000000 int vergleiche durchführen, das könnte etwas Zeit in Anspruch nehmen.

Wahrscheinlich kannst du das ganze mit einer passenden Sortierung noch verbessern, dann wird der Algorithmus aber schonmal deutlich komplizierter als dein Ansatz.

Gruß Jaraz

[geloescht_Newlukai]

War' mir schon klar, daß auch primitive Datentypen Speicher belegen. Nur fällt halt der ganze zusätzliche Speicher weg, den Objekte benötigen.

Die Zahl ist aber trotzdem imposant. War' mir auch klar, daß das nicht geht, schließlich hab' ich noch nie ein Array mit Integer.MAX hinbekommen...

Wenn die Grenzen nicht wären, hätte man jedenfalls eine elegante Lösung.

Wie Du aber schon sagtest, wäre es wohl am besten über Datei oder noch besser über Datenbank zu fahren.

[perdian]

Sorry Perdi hab auf ändern und nicht auf zitieren geklickt und den Beitrag leider nicht mehr im Cache. Kannst du nochmal posten wenn du willst.

Jaraz

[Jaraz]

Was fällt denn bei Objekten an "zusätzlichem" Speicher an?

Ein Integer bei mir (Sun 1.4.2) 16 Byte.

Object 8 Byte, String mit 4 Zeichen 48 Byte.

http://www.sosnoski.com/Performance/Code/ObjectSize.java

Gruß Jaraz

[perdian]

Sorry Perdi hab auf ändern und nicht auf zitieren geklickt und den Beitrag leider nicht mehr im Cache.

Und ich wundere mich schon, seit wann ich mir Jaraz unterschreibe *lach*.

Kannst du nochmal posten wenn du willst.

Bekomme ich jetzt nicht mehr zusammen, beim nächsten Mal

Ein Integer bei mir (Sun 1.4.2) 16 Byte.

Object 8 Byte, String mit 4 Zeichen 48 Byte.

Darum ja zusätzlich in Anführungszeichen. Natürlich hast du immer einen gewissen Overhead mit drin, worum es mir ging war die genrelle Aussage "Primitiver Datentyp gleich besser, weil weniger Speicher" nicht unbedingt immer stimmen muss.