1

我有一个多千兆字节的文本文件，数百万行已排序：

aaaaa
bcijkjf
dfsdf
gdfgdfhqiuzhf
zzdiszfhj

在不将整个文件加载到内存的情况下，如何通过二等分搜索来搜索是否存在一行？（可能在 O(log n) 的行数中）

Python库bisect.bisect_left中的文件行中是否有类似的功能？f = open('file.txt', 'r')

该窗口最初是[a, b] = [0, file_size]. 然后它会在文件中查找位置m=(a+b)/2，查找下一\n行，然后读取以下行l。如果要搜索的模式小于或大于l（按字典顺序），那么我们继续[m, b]or [a, m]。在我自己动手之前，这在 Python 中是否存在？

4

1 回答 1

2

您可以使用mmap内置模块。它提供对文件的随机访问（即，文件的行为类似于存储在文件系统中的大型字节数组）。你可以在这里找到更多信息。

import mmap

def bisect_search(file_path, line):
    line = line.encode()
    with open(file_path, 'r+b') as f:
        mm = mmap.mmap(f.fileno(), 0)
        lo = 0
        hi = mm.size()
        while lo < hi:
            mid = (lo + hi) // 2
            left_endl_idx = mm.rfind(b'\n', lo, mid)
            right_endl_idx = mm.find(b'\n', mid, hi)
            if left_endl_idx == -1:
                left_endl_idx = lo - 1
            if right_endl_idx == -1:
                right_endl_idx = hi
            mid_line = mm[left_endl_idx + 1: right_endl_idx]
            if mid_line == line:
                return True
            if mid_line < line:
                lo = right_endl_idx + 1
            else:
                hi = left_endl_idx
    return False

True如果line文件中存在，则该函数返回，False否则返回。让我们使用以下myfile.txt文件运行几个示例：

aaaaa
bcijkjf
dfsdf
gdfgdfhqiuzhf
zzdiszfhj

>>> bisect_search('myfile.txt', 'hello')
False
>>> bisect_search('myfile.txt', 'aaaaa')
True
>>> bisect_search('myfile.txt', 'aaaa')
False
>>> bisect_search('myfile.txt', 'dfsdf')
True
>>> bisect_search('myfile.txt', 'zzdiszfhjj')
False

这个函数应该比对大文件的线性搜索要快得多。

注意：此代码适用于\n结尾，目前不适用于\r\nWindows 风格的结尾（对于 OP 不是必需的）。

于 2022-02-22T15:05:28.097 回答