索引大文件的数据结构

Question

我需要为一个非常大的(50GB +)ASCII文本文件构建索引,这将使我能够提供对文件的快速随机读取访问(获取第n行,在第n行获得第n个单词).我决定使用List<List<long>> map,其中map[i][j]元素是文件中第i行第j个字的位置.

我将按顺序构建索引,即读取整个文件并使用map.Add(new List<long>())(新行)和map[i].Add(position)(新单词)填充索引.然后,我将检索具体的单词位置map[i][j].

我看到的唯一问题是我无法预测行/单词的总数,因此我会在每次List重新分配时碰到O(n),不知道如何避免这种情况.

我为此任务选择的数据结构是否还有其他问题？哪种结构可能更好？

UPD:在运行时期间不会更改文件.除了我列出的内容之外,没有其他方法可以检索内容.

Answer 1

1. 增加大型列表的大小是非常昂贵的操作; 所以,最好在开头保留列表大小.
2. 我建议使用2个列表.第一个包含文件中单词的索引,第二个包含第一个列表中的索引(相应行中第一个单词的索引).
3. 您很可能超过所有可用的RAM.当系统开始页面输入/页面输出GC管理的RAM时,程序的性能将被完全杀死.我建议将数据存储在内存映射文件中,而不是存储在托管内存中.http://msdn.microsoft.com/en-us/library/dd997372.aspx

当您需要处理大量不适合RAM的数据时,UPD内存映射文件是有效的.基本上,如果您的索引比可用RAM大,那么它是您唯一的选择.