Best practice per contenere enormi elenchi di dati in Java

Question

Sto scrivendo un piccolo sistema in Java in cui estraggo la funzione n-gram dai file di testo e in seguito devo eseguire il processo di selezione delle caratteristiche per selezionare le funzionalità più discriminatorie.

Il processo di estrazione feature per un singolo file restituisce una mappa che contiene per ogni caratteristica univoca, le sue occorrenze nel file. Unisco tutte le mappe del file (mappa) in una mappa che contiene la frequenza del documento (DF) di tutte le funzionalità uniche estratte da tutti i file. La mappa unificata può contenere oltre 10.000.000 voci.

Attualmente il processo di estrazione delle feature sta funzionando benissimo e voglio eseguire la selezione delle funzionalità in cui ho bisogno di implementare il guadagno delle informazioni o il rapporto di guadagno. Dovrò prima ordinare la mappa, eseguire calcoli e salvare i risultati per ottenere una lista (per ogni caratteristica, il suo punteggio di selezione delle caratteristiche)

La mia domanda è: Qual è la migliore pratica e la migliore struttura dati per contenere questa grande quantità di dati (~ 10M) ed eseguire calcoli?

Answer 1

La mia intuizione è che si può trarre ispirazione dal paradigma iniziale MapReduce e suddividere il problema in molti più piccoli ma simili e quindi aggregare questi risultati parziali per raggiungere la soluzione completa.

Se si risolve un'istanza di problema più piccola alla volta (cioè un blocco di file) ciò garantirà una penalità di consumo di spazio limitata dai requisiti di spazio per questa singola istanza.

Questo approccio per elaborare il file pigramente funzionerà in modo invariato rispetto alla struttura dati scelta.

Answer 2

È possibile utilizzare un sistema di memorizzazione nella cache, controllare MapDB è molto efficiente e ha un'implementazione della mappa dell'albero (in modo che i dati possano essere ordinati senza alcuno sforzo). Inoltre, fornisce archivi dati per salvare i dati su disco quando non può essere tenuto in memoria.

// 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

Questa è una domanda molto ampia, quindi anche la risposta sarà ampia. La soluzione dipende (almeno) queste tre cose:

1. La dimensione delle voci

Memorizzazione di 10.000.000 di interi richiederà circa 40MiB di memoria, mentre la memorizzazione di 10.000.000 x 1 KiB record richiederà più di 9GiB . Questi sono due problemi diversi. Dieci milioni di interi sono banali da archiviare in memoria in qualsiasi collezione Java di riserva, mentre mantenere 9GiB in memoria ti costringerà a modificare e sintonizzare Java Heap e Garbage Collector. Se le voci sono ancora più grandi, ad esempio 1MiB, puoi dimenticare completamente la memoria in memoria. Invece, dovrai concentrarti sulla ricerca di una buona struttura dati supportata da disco, magari su un database.

2. L'hardware che si sta utilizzando

Memorizzazione di dieci milioni di dischi 1 KiB su una macchina con 8 GB di RAM non è lo stesso che la loro memorizzazione su un server con 128GiB . Le cose che sono praticamente impossibili con la precedente macchina sono banali con quest'ultima.

3. Il tipo di calcolo (s) che si vuole fare

Hai menzionato l'ordinamento, quindi le cose come TreeMap o forse PriorityQueue vengono in mente. Ma è il calcolo più intenso? E qual è la chiave che stai usando per ordinarli? Avete in programma di localizzare (ottenere) entità basate su altre proprietà che non sono la chiave? Se è così, ciò richiede una pianificazione separata. Altrimenti avresti bisogno di scorrere tutte le dieci milioni di voci.

I calcoli vengono eseguiti in una singola discussione o in più thread? Se potresti avere modifiche simultanee dei tuoi dati, ciò richiede una soluzione separata. Strutture di dati come TreeMap e PriorityQueue dovrebbero essere bloccate o sostituite con strutture concorrenti come ConcurrentLinkedHashMap o ConcurrentSkipListMap.