如何直接、高效地访问非常大的文本文件？

Question

我有一个非常大的文本文件（超过10GB），想要通过数据挖掘技术读取其中一些信息。为了实现这个目的，我使用MPI并行技术，让多个进程同时访问同一文件。
事实上，我希望每个进程读取N行文本。由于文件没有结构（每个字段包含的字符数不同），我必须解析文件，这不是并行化的，也需要很长时间。 是否有方法可以直接访问特定行而无需解析和计算行数？ 谢谢您的帮助。

- ezzakrem

Answer 1

如果您的文件没有被索引，那么就没有直接的方法。

对其进行索引可能是值得的（扫描一次以查找所有行尾，并存储每行或每个行块的偏移量）。如果您需要多次处理该文件，并且它不会改变，则索引它的成本可以通过使用索引轻松进行进一步运行来抵消。

否则，如果您不需要所有作业具有完全相同的行/项目数量，可以随意操作。跳转到给定的偏移量（如1G），并查找最接近的行分隔符。重复执行在偏移量2G等位置，直到找到足够的断点为止。

然后，您可以在已确定的每个块上启动并行任务。

- Mat

---

一次扫描以查找换行符并将索引传递给其他进程绝对比其他任何方法更可取，因为任何随机查找都比在文本文件中每行解析某些字段的并行化购买的任何内容昂贵几个数量级。顺序读取和从缓冲区高速缓存中提取是快速的，而其他所有操作都会破坏每个优化。 - Damon

fseek 是一种完全盲目的寻址方式。它将文件指针移动指定字节数，仅此而已。无论这是否恰好是常数时间取决于文件系统实现细节，但在您的情况下这并不重要 - 寻址将是“瞬间”的。（除非您的文件存储在机械磁带驱动器上...） - Mat

@Damon 你为什么认为随机查找很昂贵？ - James Kanze

请注意，如果解决方案涉及随机查找，则必须以二进制模式打开文件（并使用平台相关的行分隔符定义）。如果文件以文本模式打开，则仅允许在文件开头、结尾或由 tell 返回的位置进行合法查找。 - James Kanze

你可以将文件进行内存映射，让操作系统/文件系统自行决定最佳的缓存和查找方式（假设这在操作系统/文件系统中已经优化）。 - edA-qa mort-ora-y

Answer 2

除了已经提到的需要扫描整个文件的选项外，还有其他一些选择：

1. 创建一个主进程通过管道/命名管道将行推送给实际处理的子进程。这可能会慢一些，但是如果说90%的时间在子进程中用于处理文本，那么应该还是可以的。

2. 一个愚蠢但有效的技巧：假设你有N个进程，可以通过argv或其他方式告诉每个进程它的“序列号”，例如 processor -serial_number [1|2|3...N] -num_procs N，它们都可以读取相同的数据，但仅处理具有lineno % num_procs == serial_number的行。它的效率稍低，因为它们将读取全部数据，但是如果它们只处理每第N行，并且这是耗时最长的部分，那么应该没问题。

- Not_a_Golfer

---

+1 鼓励创新思维。有时候，赢得胜利的最佳方式就是改变规则。 - Matthieu M.

Answer 3

不，没有：只有当你读取了未知数据后，才能知道有多少换行符。这个问题的复杂度是 O(n)，因此至少需要读取整个文件一次。然后，你可能想要构建一个索引表，在其中记录文件中的换行符位置：这可以被所有进程使用，在使用 fseek 时可以极大地加快访问速度。

- MrTJ

---

谢谢您的回复，这似乎是一个不错的解决方案。我会尝试一下，看看它是否值得，因为在串行模式下，我读取一个文件，然后对每一行进行许多CPU计算。到目前为止，我有两个解决方案：我解析文件以构建索引文件，然后所有进程都可以使用它。或者我让一个进程从文件中读取，让其他进程进行计算。 - ezzakrem

我所提到的O(n)是指这个符号：http://en.wikipedia.org/wiki/Time_complexity#Linear_time 顺便说一下，索引非常容易并行执行。如果你有几个进程，你可以将文件分割成多个部分进行索引，比如第一个进程读取第一个GB，第二个进程读取第二个GB等等，并将所有新行字符的位置保存到同一个共享资源中。这也可以加速索引。但是不要忘记，根据你使用的存储硬件，顺序读取可能会快得多。 - MrTJ

所以这是关于混合两个步骤的问题： 1- 像你说的那样，让N个进程获取索引。 2- 对于CPU计算，每个进程使用fseek()直接访问特定偏移量。 看起来很不错，值得一试。 谢谢。 - ezzakrem