对已排序csv进行高效查询

Question

我有一个.csv，里面有几百万行。第一列是每个条目的id，每个id只出现一次。对第一列进行排序。直观地说，使用分治算法高效地查询这个文件可能非常容易。然而，我找不到任何与此相关的东西。

示例.csv文件：

+----+------------------+-----+
| id | name             | age |
+----+------------------+-----+
| 1  | John Cleese      | 34  |
+----+------------------+-----+
| 3  | Mary Poppins     | 35  |
+----+------------------+-----+
| .. | ...              | ..  |
+----+------------------+-----+
| 87 | Barry Zuckerkorn | 45  |
+----+------------------+-----+

我不想在内存中加载文件(太大)，我更喜欢不使用数据库。我知道我可以在sqlite中导入这个文件，但我有这个数据的多个副本，出于多种原因，我宁愿避免这样做。

有一个好包裹我正在俯瞰吗？或者这是我必须自己写的东西？

Answer 1

好的，我的理解是，你想要一个轻量级数据库的一些功能，但被限制使用csv文本文件来保存数据。IMHO，这可能是一个有问题的设计：在过去的几百行中，我只会看到一个csv文件，一个中间或交换格式。

由于这是一种非常罕见的设计，它的包装不太可能已经存在——就我而言，我一无所知。因此，我设想了两种可能的方法：扫描文件一次，构建一个索引id->row_position，然后将该索引用于查询。根据行的实际长度，可以只对第n行进行索引，以更改内存的速度。但它需要一个索引文件

另一种方法是直接的分而治之算法：使用stat/fstat来获取文件大小，并搜索从文件中间开始的下一行末尾。在它之后你会立即得到一个id。如果你想要的id就是那个id，那就好了，你赢了，如果它更大，就在上半部分递归，如果更小，就在下半部分递归。但是，由于有必要搜索行的末尾，请准备好像从未在预期范围内找到行的末尾或在末尾找到行一样将其置于角落。

Answer 2

Serges回答后，我决定编写自己的实现，就在这里。它不允许换行，也不处理有关.csv格式的很多细节。它假设.csv在第一列上排序，并且第一列是整数值。

import os
def query_sorted_csv(fname, id):
filesize = os.path.getsize(fname)
with open(fname) as fin:
row = look_for_id_at_location(fin, 0, filesize, id)
if not row:
raise Exception('id not found!')
return row
def look_for_id_at_location(fin, location_lower, location_upper, id, sep=',', id_column=0):
location = int((location_upper + location_lower) / 2)
if location_upper - location_lower < 2:
return False
fin.seek(location)
next(fin)
try:
full_line = next(fin)
except StopIteration:
return False
id_at_location = int(full_line.split(sep)[id_column])
if id_at_location == id:
return full_line
if id_at_location > id:
return look_for_id_at_location(fin, location_lower, location, id)
else:
return look_for_id_at_location(fin, location, location_upper, id)
row = query_sorted_csv('data.csv', 505)

您可以在一个200万行250MB.csv文件中每秒查找大约4000个id。相比之下，您可以在逐行循环整个文件的同时每秒查找3个id。