c# - 索引大文件的数据结构

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

UPD 内存映射文件在您需要处理不适合 RAM 的大量数据时非常有效。基本上，如果您的索引变得比可用 RAM 大，这是您唯一的选择。