对行长度未知的大文件进行二分搜索

Question

我正在处理大量数据 CSV 文件。每个文件包含数百万条记录，每个记录都有一个密钥。记录按其键排序。在搜索某些数据时，我不想遍历整个文件。 我见过这个解决方案： Reading Huge File in Python

但它建议您使用文件上的行长度相同 - 在我的情况下不支持。

我考虑过为每行添加填充，然后保持固定的行长度，但我想知道是否有更好的方法来做到这一点。

我正在使用 python

Answer 1

您不必有固定宽度的记录，因为您不必进行面向记录的搜索。相反，您可以只进行面向字节的搜索，并确保每次执行搜索时都重新对齐键。这是一个（可能有错误的）示例，说明如何将链接到的解决方案从面向记录修改为面向字节：

bytes = 24935502 # number of entries
for i, search in enumerate(list): # list contains the list of search keys
  left, right = 0, bytes - 1 
  key = None
  while key != search and left <= right:
    mid = (left + right) / 2
    fin.seek(mid)
    # now realign to a record
    if mid:
        fin.readline()
    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

Answer 2

为了解决这个问题，你也可以使用二分查找，但你需要稍微改变一下：

1. 获取文件大小。
2. 使用 File.seek 查找到大小的中间位置。
3. 并搜索第一个 EOL 字符。然后你会找到一条新线。
4. 检查这一行的键，如果不是您想要的，请更新大小并转到2。

这是示例代码：

fp = open('your file')
fp.seek(0, 2)
begin = 0
end = fp.tell()

while (begin < end):
    fp.seek((end + begin) / 2, 0)
    fp.readline()
    line_key = get_key(fp.readline())
    if (key == line_key):
        pass # find what you want
    elif (key > line_key):
        begin = fp.tell()
    else:
        end = fp.tell()

也许代码有错误。验证一下你自己。如果您确实想要最快的方法，请检查性能。

Answer 3

所引用问题的答案是二分搜索仅适用于固定长度记录，这是错误的。而且您根本不需要进行搜索，因为您有多个项目需要查找。只需一次一行遍历整个文件，为每行构建一个 key:offset 字典，然后对于每个搜索项，使用 os.key:offset 跳转到感兴趣的记录。 lseek 对应于每个键的偏移量。

当然，如果您不想读取整个文件，哪怕一次，您就必须进行二分搜索。但是，如果构建索引可以分摊到多次查找上，如果每天只进行一次查找，也许可以保存索引，那么就不需要搜索了。