在已打开文件的排序行中进行二分搜索(未加载到内存中)
Bisection search in the sorted lines of an opened file (not loaded in memory)
我有一个几千兆字节的文本文件,对几百万行进行排序:
aaaaa
bcijkjf
dfsdf
gdfgdfhqiuzhf
zzdiszfhj
如何在不将整个文件加载到内存的情况下,使用二分搜索来搜索一行是否存在?(可能在 O(log n) 中行数)
Python库中的文件f = open('file.txt', 'r')
的行中是否有类似bisect.bisect_left
的函数?
window 最初是 [a, b] = [0, file_size]
。然后它将在 m=(a+b)/2
位置的文件中查找,查找下一个 \n
,并读取下面的行 l
。如果要搜索的模式小于或大于 l
(按字典顺序),则我们继续 [m, b]
或 [a, m]
。在我自己滚动之前,Python 中是否存在这个?
您可以使用 mmap
built-in module. It provides random access to files (i.e., a file behaves like a large array of bytes stored in the file system). You can find more info here.
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
函数 returns 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\n
Windows-style 结尾(OP 不需要)。
我有一个几千兆字节的文本文件,对几百万行进行排序:
aaaaa
bcijkjf
dfsdf
gdfgdfhqiuzhf
zzdiszfhj
如何在不将整个文件加载到内存的情况下,使用二分搜索来搜索一行是否存在?(可能在 O(log n) 中行数)
Python库中的文件f = open('file.txt', 'r')
的行中是否有类似bisect.bisect_left
的函数?
window 最初是 [a, b] = [0, file_size]
。然后它将在 m=(a+b)/2
位置的文件中查找,查找下一个 \n
,并读取下面的行 l
。如果要搜索的模式小于或大于 l
(按字典顺序),则我们继续 [m, b]
或 [a, m]
。在我自己滚动之前,Python 中是否存在这个?
您可以使用 mmap
built-in module. It provides random access to files (i.e., a file behaves like a large array of bytes stored in the file system). You can find more info here.
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
函数 returns 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\n
Windows-style 结尾(OP 不需要)。