我有一個多千兆位元組的文本檔案，數百萬行已排序：
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 中是否存在？
uj5u.com熱心網友回復：
您可以使用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 不是必需的）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/433107.html