在打开的文件的排序行中进行二分搜索（未加载到内存中）

Question

我有一个数千兆字节的文本文件，并且对数百万行进行了排序：

aaaaa
bcijkjf
dfsdf
gdfgdfhqiuzhf
zzdiszfhj

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

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

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

Answer 1

您可以使用 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

如果文件中存在 line，则该函数返回 True，否则返回 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\n Windows 风格的结尾（OP 不需要）。