9

我需要为一个非常大的（50GB+）ASCII 文本文件建立一个索引，这将使我能够提供对文件的快速随机读取访问（获取第 n 行，获取第 n 行中的第 n 个单词）。我决定使用List<List<long>> map，其中map[i][j]element 是文件中第 i 行的第 j 个单词的位置。

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

我看到的唯一问题是我无法预测行/字的总数，所以我会在每次List重新分配时遇到 O(n)，不知道如何避免这种情况。

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

UPD：文件在运行时不会被更改。除了我列出的内容外，没有其他方法可以检索内容。

4

1 回答 1

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

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

于 2013-03-17T07:55:12.143 回答