Best Practice für das Halten riesiger Datenlisten in Java

Question

Ich schreibe ein kleines System in Java, in dem ich N-Gram-Funktion aus Textdateien extrahiere und später Feature-Auswahlprozess durchführen muss, um die meisten Diskriminator-Funktionen auszuwählen.

Der Feature Extraction-Prozess für eine einzelne Datei gibt eine Map zurück, die für jedes eindeutige Feature seine Vorkommen in der Datei enthält. Ich füge alle Maps (Map) der Datei zu einer Map zusammen, die die Document Frequency (DF) aller eindeutigen Features enthält, die aus allen Dateien extrahiert wurden. Die vereinheitlichte Karte kann mehr als 10.000.000 Einträge enthalten.

Derzeit funktioniert der Feature Extraction-Prozess großartig und ich möchte Feature-Auswahl durchführen, in denen ich Information Gain oder Gain Ratio implementieren muss. Ich muss die Karte zuerst sortieren, Berechnungen durchführen und die Ergebnisse speichern, um schließlich eine Liste von (für jedes Feature, seine Feature Selection Score) zu erhalten

Meine Frage ist: Was ist die beste Praxis und das Beste Datenstruktur, um diese große Datenmenge (~ 10M) zu speichern und Berechnungen durchzuführen?

Answer 1

Meine Intuition ist, dass Sie sich von dem anfänglichen Paradigma inspirieren lassen und Ihr Problem in mehrere kleinere, aber ähnliche teilen und diese Teilergebnisse dann aggregieren können, um die vollständige Lösung zu erreichen.

Wenn Sie immer eine kleinere Probleminstanz lösen (d. H. Dateibrocken), garantiert dies Ihnen einen Speicherplatzverbrauch, der durch den Platzbedarf für diese einzelne Instanz begrenzt wird.

Dieser Ansatz zur langsamen Verarbeitung der Datei funktioniert invariant für die von Ihnen gewählte Datenstruktur.

Answer 2

Sie können ein Caching-System verwenden, überprüfen Sie MapDB, es ist sehr effizient und verfügt über eine Tree Map-Implementierung (so können Sie Ihre Daten ohne Aufwand bestellt haben). Außerdem stellt es Datenspeicher bereit, um Ihre Daten auf der Festplatte zu speichern, wenn sie nicht im Speicher gehalten werden können.

// here a sample that uses the off-heap memory to back the map 
Map<String, String> map = DBMaker.newMemoryDirectDB().make().getTreeMap("words"); 

//put some stuff into map 
map.put("aa", "bb"); 
map.put("cc", "dd"); 

Answer 3

Dies ist eine sehr weit gefasste Frage, so dass die Antwort auch breit ist. Die Lösung ist abhängig von (mindestens) diese drei Dinge:

1. Die Größe Ihrer Einträge

Speichern von 10.000.000 ganzen Zahlen wird über 40MiB Speicher benötigen, während 10.000.000 Speicherung x 1KiB Datensätze mehr erfordern als 9GiB . Dies sind zwei verschiedene Probleme. Zehn Millionen Ganzzahlen sind trivial in jeder Java-Sammlung im Speicher zu speichern, während 9GiB im Speicher zu halten, zwingt und zwingt Sie den Java-Heap und Garbage Collector zu optimieren. Wenn die Einträge noch größer sind, sagen Sie 1MB, dann können Sie den In-Memory-Speicher vollständig vergessen. Stattdessen müssen Sie sich darauf konzentrieren, eine gute datenträgergestützte Datenstruktur zu finden, möglicherweise eine Datenbank.

2. Die Hardware Sie

Speicher von zehn Millionen 1KiB Aufzeichnungen auf einer Maschine mit 8 GiB RAM verwenden sind, ist nicht das Gleiche wie sie auf einem Server mit 128GiB Speicherung . Dinge, die mit der ehemaligen Maschine so gut wie unmöglich sind, sind bei letzterer trivial.

3. Die Art der Berechnung (en) möchten Sie

Sie haben Sortierung erwähnt zu tun, also Dinge wie TreeMap oder vielleicht PriorityQueue in den Sinn kommen. Aber ist das die intensivste Berechnung? Und mit welchem ​​Schlüssel sortieren Sie sie? Planen Sie, Entitäten basierend auf anderen Eigenschaften zu finden (zu bekommen), die nicht der Schlüssel sind? Wenn dies der Fall ist, erfordert dies eine separate Planung. Andernfalls müssten Sie alle zehn Millionen Einträge durchlaufen.

Laufen Ihre Berechnungen in einem oder mehreren Threads? Wenn Sie gleichzeitig Änderungen an Ihren Daten vornehmen möchten, erfordert dies eine separate Lösung. Datenstrukturen wie TreeMap und PriorityQueue müssten entweder gesperrt oder durch gleichzeitige Strukturen wie ConcurrentLinkedHashMap oder ConcurrentSkipListMap ersetzt werden.