3

我最近在一次采访中被问到这个问题。

给定一个输入文件、一个正则表达式和一个输出文件。读取输入文件，将每一行与正则表达式匹配，并将匹配的行写入输出文件。

我想出了使用链接到 FileReader 的 BufferedReader 的粗略方案（以优化从磁盘读取）。我使用了类似的写作方案。

面试官接着说，这个过程需要 3 秒从文件中读取一行，1 秒将正则表达式与该行进行比较，另外 5 秒写回。所以每行总共需要9秒。我们该怎样改进这个？

我建议一次读取整个文件，处理它并立即写入整个输出文件。但是，有人告诉我这无济于事（写 1 行 = 5 秒，写 2 行 = 10 秒）。

面试官进一步表示，这是由于硬件/硬盘驱动器的限制。有人问我如何改进我的代码以减少每行的总秒数（当前为 9 ）？

我只能想到缓冲的读/写，也找不到太多关于 SO 的内容。有什么想法吗 ？

4

3 回答 3

2

我认为面试官正在寻找一种在写入输出的同时执行读取/正则表达式检查的解决方案。如果您设置一个通过读取和过滤异步填充的工作队列，并将写入放在一个单独的线程中，那么从第二行开始，每行合并的过程需要 5 秒。

这里的假设是读取、解析和写入可以相互独立地发生。在这种情况下，您可以在编写第 1 行的同时阅读第 2 行：您只需要四秒钟来读取和应用您的正则表达式，并且在编写器准备好第二行之前您有整整五秒钟的时间。写作仍然是你的瓶颈，但整个过程加快了大约 44%，这还不错。

于 2013-03-03T14:22:08.653 回答
0

好吧，既然读取的时间是固定的，而写入的时间是固定的，那么在这种情况下，您唯一的选择就是更改正则表达式位的性质。

您可以编写代码来快速应用正则表达式测试，而无需正则表达式可以做的所有聪明事情的开销。

另一方面，如果问题是每个 IO 请求需要几秒钟才能执行，但限制不是实际驱动器，那么让多个读取器同时读取。

于 2013-03-03T14:24:23.867 回答
0

棘手的问题，因为我们对系统知之甚少。

我的猜测是使用线程/异步处理。使用一个 Thread 读取，一个处理两个或多个进行写入，从而减少 IO Wait 所花费的时间。

让我尝试将其转换为 ASCII 图表：

  • R/r 表示读数（3 秒）
  • P/p 表示处理（1 秒）
  • W/w 表示写作（5 秒）

大写字母标记开始，小写字母标记继续工作。“：”表示线程空闲

Thread 1: RrrRrrRrrRrrRr
Thread 2: ...P..P..P..P.
Thread 3: ....Wwwww
Thread 4: .......Wwwww

使用此设置，第一批在 9 秒后被写回（这里没什么可做的），但第二批在 12 秒后完成。单线程第二个总共需要 18 秒

于 2013-03-03T14:24:27.613 回答