我想搜索一個非常大的文本文件，其中SHA1哈希使用 Python 按哈希值排序。文本文件有10GB和500 000 000行。每行如下所示：000009F0DA8DA60DFCC93B39F3DD51A088ED3FD9:27我由此比較文件中是否出現給定的哈希值。我用BinarySearch試過，但它只適用于一個小測試文件。如果我使用該文件進行10GB搜索需要太長時間，并且該過程有時會因為16GB RAM超出而被終止。f=open('testfile.txt', 'r')text=f.readlines()data=text#print datax = '000009F0DA8DA60DFCC93B39F3DD51A088ED3FD9:27'def binarySearch(data, l, r, x): while l <= r: mid = l + (r - l)/2; # Check if x is present at mid if data[mid] == x: return mid # If x is greater, ignore left half elif data[mid] < x: l = mid + 1 #print l # If x is smaller, ignore right half else: r = mid - 1 #print r# If we reach here, then the element# was not present return -1result = binarySearch(data,0, len(data)-1, x)if result != -1: print "Element is present at index % d" % resultelse: print "Element is not present in array"有沒有辦法將10GB文本文件一次加載到 RAM 中并一遍又一遍地訪問它？我有16GB RAM可用的。應該夠了吧？我還能做些什么來加快搜索速度嗎？不幸的是，我不再知道了。
1 回答
GCT1015
TA貢獻1827條經驗 獲得超4個贊
將您的示例輸入input.txt如下
000000005AD76BD555C1D6D771DE417A4B87E4B4:4
00000000A8DAE4228F821FB418F59826079BF368:3
00000000DD7F2A1C68A35673713783CA390C9E93:630
00000001E225B908BAC31C56DB04D892E47536E0:5
00000006BAB7FC3113AA73DE3589630FC08218E7:2
00000008CD1806EB7B9B46A8F87690B2AC16F617:4
0000000A0E3B9F25FF41DE4B5AC238C2D545C7A8:15
0000000A1D4B746FAA3FD526FF6D5BC8052FDB38:16
0000000CAEF405439D57847A8657218C618160B2:15
0000000FC1C08E6454BED24F463EA2129E254D43:40
并刪除計數，使您的文件變為（in.txt如下）：
000000005AD76BD555C1D6D771DE417A4B87E4B4
00000000A8DAE4228F821FB418F59826079BF368
00000000DD7F2A1C68A35673713783CA390C9E93
00000001E225B908BAC31C56DB04D892E47536E0
00000006BAB7FC3113AA73DE3589630FC08218E7
00000008CD1806EB7B9B46A8F87690B2AC16F617
0000000A0E3B9F25FF41DE4B5AC238C2D545C7A8
0000000A1D4B746FAA3FD526FF6D5BC8052FDB38
0000000CAEF405439D57847A8657218C618160B2
0000000FC1C08E6454BED24F463EA2129E254D43
這將確保每個條目都有固定的大小。
現在您可以使用基于 mmap 的文件讀取方法，如https://docs.python.org/3/library/mmap.html
import mmap
import os
FIELD_SIZE=40+1 # also include newline separator
def binarySearch(mm, l, r, x):
while l <= r:
mid = int(l + (r - l)/2);
# Check if x is present at mid
mid_slice = mm[mid*FIELD_SIZE:(mid+1)*FIELD_SIZE]
mid_slice = mid_slice.decode('utf-8').strip()
# print(mid_slice)
if mid_slice == x:
return mid
# If x is greater, ignore left half
elif mid_slice < x:
l = mid + 1
#print l
# If x is smaller, ignore right half
else:
r = mid - 1
#print r
# If we reach here, then the element
# was not present
return -1
# text=f.readlines()
# data=text
#print data
x = '0000000CAEF405439D57847A8657218C618160B2'
with open('in.txt', 'r+b') as f:
mm = mmap.mmap(f.fileno(), 0)
f.seek(0, os.SEEK_END)
size = f.tell()
result = binarySearch(mm, 0, size/FIELD_SIZE, x)
if result != -1:
print("Element is present at index % d" % result)
else:
print("Element is not present in array")
輸出：
$ python3 find.py
Element is present at index 8
由于文件沒有完全在內存中讀取，因此不會出現內存不足的錯誤。
添加回答
舉報
0/150
提交
取消