Beiträge

Beginner   Java allgemein   JDBC   JNI   Networking   Online-Ressourcen   Swing + AWT   XML   Meckerecke    Antworten     Neuer Beitrag     Gesamtdarstellung Detaildarstellung Einzeldarstellung Threaddarstellung

Beitrag 1024 von 2212 (46%)

Autor	lesi
Datum	06.09.05, 17:10
Betreff	Häufigkeit der Werte in Datei zählen - Heap Space beschränkt

---

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.

---

Auf diesen Beitrag antworten   Neuen Beitrag verfassen