struttura dei dati per l'indicizzazione grande file

Question

Ho bisogno di costruire un indice per un file di testo ASCII molto grande (50 GB +), che mi permetterà di fornire veloce accesso in lettura casuale di file (ottenere la linea n-esima, ottenere ennesima parola in linea ennesima). Ho deciso di utilizzare List<List<long>> map, dove l'elemento map[i][j] è la posizione della parola jth di ith nel file.

Costruirò l'indice in modo sequenziale, ovvero leggo l'intero file e l'indice di popolamento con map.Add(new List<long>()) (nuova riga) e map[i].Add(position) (nuova parola). Quindi recupererò la posizione della parola specifica con map[i][j].

L'unico problema che vedo è che non posso prevedere il conteggio totale delle linee/parole, quindi mi imbattersi in O (n) su ogni List riallocazione, nessuna idea di come posso evitare questo.

Ci sono altri problemi con la struttura dati che ho scelto per l'attività? Quale struttura potrebbe essere migliore?

UPD: il file non verrà modificato durante il runtime. Non ci sono altri modi per recuperare il contenuto tranne quello che ho elencato.

Answer 1

1. L'aumento delle dimensioni di un elenco di grandi dimensioni è un'operazione molto costosa; quindi, è meglio prenotare la dimensione dell'elenco all'inizio.
2. Suggerisco di utilizzare 2 elenchi. Il primo contiene indici di parole all'interno di un file e il secondo contiene indici nel primo elenco (indice della prima parola nella riga appropriata).
3. È molto probabile che si superi la RAM disponibile. E quando il sistema inizia a caricare la RAM gestita da GC, le prestazioni del programma verranno completamente eliminate. Suggerirei di memorizzare i dati in un file mappato in memoria piuttosto che nella memoria gestita. http://msdn.microsoft.com/en-us/library/dd997372.aspx

memoria mappata file UPD sono efficaci, quando si ha bisogno di lavorare con enormi quantità di dati che non rientrano nella RAM. Fondamentalmente, è la tua unica scelta se il tuo indice diventa più grande della RAM disponibile.