我有一个384MB的文本文件,有5000万行。每行包含两个空格分隔的整数:一个键和一个值。文件按键排序。我需要一种高效的方法来查找Python中大约200个键列表的值。
我目前的做法如下。需要30秒。必须有更高效的Python foo才能将此效率降低到最多几秒的合理效率。
# list contains a sorted list of the keys we need to lookup
# there is a sentinel at the end of list to simplify the code
# we use pointer to iterate through the list of keys
for line in fin:
line = map(int, line.split())
while line[0] == list[pointer].key:
list[pointer].value = line[1]
pointer += 1
while line[0] > list[pointer].key:
pointer += 1
if pointer >= len(list) - 1:
break # end of list; -1 is due to sentinel
编码二进制搜索+搜索解决方案(感谢kigurai!)以下内容:
entries = 24935502 # number of entries
width = 18 # fixed width of an entry in the file padded with spaces
# at the end of each line
for i, search in enumerate(list): # list contains the list of search keys
left, right = 0, entries-1
key = None
while key != search and left <= right:
mid = (left + right) / 2
fin.seek(mid * width)
key, value = map(int, fin.readline().split())
if search > key:
left = mid + 1
else:
right = mid - 1
if key != search:
value = None # for when search key is not found
search.result = value # store the result of the search
如果你只需要5千万行中的2亿行,那么把它们全部读入内存是一种浪费。我会对搜索键列表进行排序,然后使用seek()或类似的方法对文件应用二进制搜索。这样你就不会把整个文件读到内存中,我认为这会加快速度。
S.Lotts答案的轻微优化:
因为我们使用的是字典而不是列表,所以键不必是数字。这将为每一行保存map()操作和字符串到整数的转换。如果您希望键是数字,则在结束时进行转换a,此时您只需要为每个键执行一次转换,而不是为5000万行中的每一行执行一次转换。
目前还不清楚“list[pointer]”到底是什么意思。不过,考虑一下。
相关问题 更多 >
编程相关推荐