如果你有一个很大的日志文件,数十亿行。这些文件有一些列,例如 IP 地址:xxx.xxx.xxx.xxx
.
我怎样才能快速找到准确的一行,就像我想找到123.123.123.123
.
幼稚的逐行搜索似乎太慢了。
如果你有一个很大的日志文件,数十亿行。这些文件有一些列,例如 IP 地址:xxx.xxx.xxx.xxx
.
我怎样才能快速找到准确的一行,就像我想找到123.123.123.123
.
幼稚的逐行搜索似乎太慢了。
如果您没有任何其他信息可以继续(例如日期范围,假设文件已排序),那么逐行搜索是您的最佳选择。现在,这并不意味着您需要逐行阅读。此外,向后搜索可能更有效,因为您知道该条目是最近的。
一般方法(用于向后搜索)是这样的:
声明一个缓冲区。您将一次尽可能快地将文件的块读取到此缓冲区中(最好使用可以直接读取而无需任何缓冲/缓存的低级操作系统调用)。
因此,您寻找文件的末尾减去缓冲区的大小并读取那么多字节。
现在您在缓冲区中向前搜索第一个换行符。稍后记住该偏移量,因为它代表部分线。从下一行开始,您向前搜索到缓冲区的末尾以查找您的字符串。如果它必须在某个列中,但其他列可能包含该值,那么您需要进行一些解析。
现在您继续向后搜索您的文件。您寻找您读取的最后一个位置减去块大小加上您在搜索换行符时找到的偏移量。现在,你再读一遍。如果您愿意,您可以将该部分行移动到缓冲区的末尾并读取更少的字节,但如果您的块足够大,它不会产生巨大的差异。
然后继续,直到到达文件的开头。当读取的字节数小于块大小时,当然有一种特殊情况(即,您不要忽略第一行)。我假设您不会到达文件的开头,因为很明显您不想搜索整个内容。
所以这就是当你不知道价值在哪里时的方法。如果您确实对排序有一些想法,那么您当然可能想要进行二进制搜索。在这种情况下,您可以使用较小的块大小(至少足以捕获整行)。
您确实需要在文件中搜索一些规律性并加以利用,除此之外,如果您有更多的处理器,您可以将文件分成多个部分并并行搜索 - 假设 I/O 不会成为瓶颈。