struktura danych do indeksowania dużego pliku

Question

Potrzebuję zbudować indeks dla bardzo dużego (50GB +) pliku tekstowego ASCII, który pozwoli mi zapewnić szybki losowy dostęp do odczytu do pliku (uzyskać n-tą linię, dostać n-tą słowo w n-tą linię). Postanowiłem użyć List<List<long>> map, gdzie element map[i][j] jest pozycją jth słowa i-tej linii w pliku.

Utworzę indeks po kolei, tzn. Odczytuję cały plik i wypełniam indeks przy pomocy map.Add(new List<long>()) (nowa linia) i map[i].Add(position) (nowe słowo). Następnie odzyskaję określoną pozycję słowa przy pomocy map[i][j].

Jedyny problem jaki widzę to to, że nie mogę przewidzieć całkowitej liczby linii/słów, więc wpadnę na O (n) przy każdej realokacji List, nie mam pojęcia, jak mogę tego uniknąć.

Czy są jakieś inne problemy ze strukturą danych wybraną do zadania? Która struktura może być lepsza?

UPD: Plik nie zostanie zmieniony w czasie wykonywania. Nie ma innych sposobów na pobieranie treści poza wymienionymi na liście.

Answer 1

1. Zwiększenie rozmiaru dużej listy jest bardzo kosztowną operacją; więc lepiej jest zarezerwować rozmiar listy na początku.
2. Proponuję użyć 2 list. Pierwsza zawiera indeksy słów w pliku, a druga zawiera indeksy na pierwszej liście (indeks pierwszego słowa w odpowiedniej linii).
3. Prawdopodobnie przekroczysz całą dostępną pamięć RAM. A kiedy system zacznie wyświetlać w pamięci RAM zarządzanej przez GC, wydajność programu zostanie całkowicie wyeliminowana. Proponuję przechowywanie danych w pliku mapowanym w pamięci zamiast w pamięci zarządzanej. http://msdn.microsoft.com/en-us/library/dd997372.aspx

Pliki odwzorowane w pamięci UPD są skuteczne, gdy trzeba pracować z ogromną ilością danych niepasujących do pamięci RAM. Zasadniczo jest to twój jedyny wybór, jeśli twój indeks staje się większy niż dostępna pamięć RAM.