Ich schreibe ein kleines System in Java, in dem ich ein N-Gramm-Feature aus Textdateien extrahiere und später einen Feature-Selection-Prozess durchführen muss, um die meisten Diskriminator-Features 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 sehr gut und ich möchte Feature Selection durchführen, in dem ich Information Gain oder Gain Ratio implementieren muss. Ich muss die Map 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 Vorgehensweise und die beste Datenstruktur, um diese große Datenmenge (~ 10M) zu speichern und Berechnungen durchzuführen?
Dies ist eine sehr weit gefasste Frage, daher wird auch die Antwort breitgefächert. Die Lösung hängt von (mindestens) diesen drei Dingen ab:
Speichern von 10.000.000 ganzen Zahlen wird über 40MiB Speicher benötigen, während die Speicherung 10.000.000 x 1KiB Datensätze mehr als 9GiB erfordern. Dies sind zwei verschiedene Probleme. Zehn Millionen ganzen Zahlen sind trivial im Speicher in jedem Lager Java Sammlung zu speichern, während 9GiB halten im Speicher wird Sie zwingen, zu optimieren und tunen die Java Heap und Garbage Collector. 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, vielleicht eine Datenbank.
Das Speichern von zehn Millionen 1KiB-Datensätzen auf einem Rechner mit 8 GiB RAM ist nicht dasselbe wie das Speichern auf einem Server mit 128GiB. Dinge, die mit der ehemaligen Maschine so gut wie unmöglich sind, sind bei letzterer trivial.
Sie haben erwähnt, Sortierung, so Dinge wie TreeMap oder vielleicht Priorityqueue in dem Sinne 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 würden entweder gesperrt oder mit gleichzeitigen Strukturen ersetzt werden, wie beispielsweise ConcurrentLinkedHashMap oder ConcurrentSkipListMap .
Meine Intuition ist, dass Sie sich von dem ursprünglichen MapReduce -Paradigma inspirieren lassen und Ihr Problem in mehrere kleinere, aber ähnliche Teile aufteilen können und dann diese Teilergebnisse aggregieren, um die vollständige Lösung zu erreichen.
Wenn Sie immer eine kleinere Probleminstanz lösen (d. h. einen Dateiblock), garantiert dies Ihnen einen Speicherplatzverbrauch, der durch den Speicherplatzbedarf für diese einzelne Instanz begrenzt ist.
Dieser Ansatz zur langsamen Verarbeitung der Datei funktioniert invariant für die von Ihnen gewählte Datenstruktur.
Sie können ein Cachesystem verwenden, MapDB überprüfen, es ist sehr effizient und verfügt über eine Baumkartenimplementierung (damit Sie Ihre Daten haben können ohne Mühe bestellt). Außerdem stellt es Datenspeicher bereit, um Ihre Daten auf dem Datenträger zu speichern, wenn sie nicht im Speicher gehalten werden können.
%Vor%Tags und Links java data-structures feature-selection computation feature-extraction