如何使用 Java 查找文件中的某些行

您似乎在询问有关如何解决此问题的注释和提示。

1. 请注意，文件是字节，但文本搜索意味着字符集编码。

这意味着“我只将文件分成 2MB 块”可能意味着块可以从字符的中间开始（像 UTF-8 这样的字符集编码可能需要超过 1 个字节来存储一个字符），这会使事情复杂化。一种解决方案是获取您的“针”（您正在搜索的字符串），将其转换为字节（例如），然后搜索它们。needle.getBytes(StandardCharsets.UTF_8)

2. 有 2 种方法可以解决“如果大海捞针包含针头，但我的分块过程在针头中途块怎么办？

重叠

如果“针”很小，则可以重叠。假设您有一个 9MB 的文件，您想分块 2MB 块，并且 needle 的长度为 50 字节。重叠解决方案要求将每个块的端点扩展 49 个字节（比针的大小小 1 个字节）。因此，第一个块并不完全是 0-2097151（价值 2MB）。它比这多了 49 - 它从 0 到 2097200。第二个块确实从 2097151 开始（有 49 个重叠）。这样一来，两个块仍然不可能报告针头，但您可以保证，如果该边界处有一根针，其中一个会报告针头。如果针头非常大，这将变得笨拙。

半场传球

可以处理大针的解决方案是将边界半匹配传递给收集器。

通常，在此类多线程作业中，您使用 map-reduce 概念：

1. 将一些输入映射到块中。
2. 每个块都是独立的（要计算块的结果，你只需要其中的数据;你不需要知道块之外的任何数据）。
3. 许多工作线程将“块作业”（描述要处理的块的简单描述符）从管道中拉出，并将它们映射到更小、更简单的结果值。
4. 最后一个线程收集所有结果并减少它们。理想情况下，这是流式处理（任何 2+ 块都可以减少为单个块），但如果此过程在所有块结果都输入之前无法减少，则通常没问题。例如，如果 reducer 需要连续块的结果来完成其工作，这很好。

此模型意味着您可以进行半匹配。处理单个（例如 2 MB）数据块的线程将其转换为结果。结果由任意数量的“找到它！”条目组成，它们有 3 种风格：

• 在 X 处找到一根针（在块中，整个针从 bytepos X 开始，到 bytepos X+needlesize 结束）。
• 找到一个长度为 Y 的针后缀（块以一堆与针的末端重叠的字节开头。例如，针是，这个块以 开头。这并不意味着实际上找到了一根针，但它是这个块处理器必须向减速器报告的一部分。Hello, World!orld!
• 相同，但在另一边：找到一个长度为 Y 的针前缀（块以 结尾）。Hello, Wor

缩减器可以排列针前缀和针后缀的报告（例如，对于 ，长度为 13，如果块 14 报告“针前缀 = 8”，块 15 报告“针后缀=5”，则文件中的 chunk15start 减去 8 处有一个针。Hello, World!

nananananaba 问题（这是 Boyer Moore 试图解决的问题）也必须在这里应用！如果针是“nananaba”，一个块以“nanana”结尾，下一个块以“nanaba”开头，那么那里有一根针，但它不是从第一个块的“nanana”开始的。它以 4 个字符开始。

这个模型叫做map-reduce：

每个块处理器将输入数据映射到中间结果值。通常，结果比输入小得多。

单个 reducer（有时在自己的专用线程上运行，但可以简单地由工作线程在执行映射操作之间完成）将采用多个映射（这些结果值）并将它们减少到单个结果值。继续前进，直到只剩下一个这样的结果值，从中生成所需的答案应该是微不足道的。将 2+ 映射压缩为单个映射的工作称为减少。

因此，map-reduce。如果您有兴趣，可以阅读例如维基百科以获取更多详细信息。

3. 这可能毫无意义

这取决于很多因素，但是在很多很多系统上，使用多个线程对从磁盘读取的文件进行极其基本的处理（这是非常基本的，甚至Boyer-Moore也是）是没有意义的 - 磁盘是瓶颈，而不是CPU。例如，微不足道的是，在旋转磁盘上（诚然，这已经是旧闻了），这将明显变慢，因为要向所有 20 个线程提供数据，磁盘需要旋转和旋转，为每个线程提供来自磁盘单独切片的数据。磁盘完全是瓶颈，因此唯一的工作是确保磁盘能够尽可能有效地提供字节。也就是说，对于连续文件（所有字节一个接一个地分层的文件），最好让一个线程从头到尾一次性读取字节。

在另一个极端，某种快速的 NVMe 多 raid 启动意味着连续访问对性能没有影响，CPU 可能是瓶颈而不是 raid 设置，因此多核会有所帮助。

我敢打赌多核会让事情变得更慢，如果有的话。从中等速度的磁盘上处理 20GB 的数据需要几秒钟。向问题抛出线程不会改变这一点。

4. 如何确定块大小？

这基本上无关紧要。但是，启动正确数量的线程。

一般来说，你知道你想要多少个线程（通常大约是你拥有的 CPU 内核数量的 2 倍，但实际上，“CPU 内核线程数量”就是你所需要的）。因此，您可以通过将总文件大小除以该大小来计算块大小。但是，这真的无关紧要。假设一个磁盘根本不关心你如何从中提取字节（极不可能，请参阅上一点！） - 如果你有一个 10TB 的文件，并且块大小为 512MB，这意味着 2048 块。您的 CPU 不太可能有 2048 个内核。不过没关系：如果它有 20 个内核，有 20 个线程在运行，并且每个线程只处理一个 500MB 的块，然后转到另一个块进行处理，它不会对这个过程的速度产生有意义的影响。只要块大小不是极端主义的（比如说，20 字节的块大小，这将是一个问题），并且所有内核通常都会很忙（微不足道的情况：如果总共有 10 个块和 20 个内核，那就不好了，你至少需要 20 个作业。最好是 200 个，这样如果某些块最终的处理速度比其他块快得多，事情就可以平衡了） - 你会没事的。

fork/join 框架就是为这些东西设计的，你可能想研究一下。

1. 诚然，某些 UTF-8 字符由 2 个或更多字节组成，正如上面的答案所提到的，但对于您的特定任务，文本可能只包含 ASCII 字符（始终为 1 个字节）。因此，我建议您专门询问这个问题，因为您可以避免处理多字节字符。
2. 使用很棒。例如，找到您的行后，您可以通过向后读取文件直到换行符来获取它前面的行。RandomAccessFile
3. 关于“分割的字符串”：如果 2MB 部分末尾的文本与您搜索的行的开头相对应，那么您可以继续阅读这 2MB 部分以外的文件——毕竟这是一个。RandomAccessFile