python - 搜索大型排序文本文件的最快、最有效的方法

Question

我有一个很大的静态文本/csv 文件，其中包含大约 10 万行 (2MB)。它本质上是一本字典，我需要在 Python 中定期查找这些数据。

文件格式为:

    key         value1       value2     
    alpha       x1           x2
    alpha beta  y1           y2
    gamma       z1           z2  
    ...

• 键可以是多词字符串。
• 列表按关键字的字母顺序排序
• 值是字符串

这是一个 Web 应用程序的一部分，每个用户一次将查找 100-300 个键，并期望为每个键同时获得值 1 和值 2。该应用程序最多将有 100 个用户，每个用户都在同一数据上查找这 100-300 个键。

我只需要返回第一个完全匹配项。例如，如果用户搜索键 [alpha, gamma]，我只需要返回 [('x1','x2'), ('z1','z2' )]，代表'alpha'和'gamma'的第一个精确匹配。

我一直在阅读有关我所拥有的选项的信息，我非常希望您能就以下哪种方法最适合我的用例提供意见。

1. 将文件一次读入有序集中，并执行 200 次左右的查找。但是，对于每个使用该应用程序的用户 (~100)，该文件将被加载到内存中。

2. 将文件一次读入列表，并使用二进制搜索(例如 bisect )。与 1.) 类似的问题。该文件将为每个需要进行搜索的用户加载到内存中。

3. 不要将整个文件读入内存，一次只读一行。我可以将 .csv 按每个字母(a.csv、b.csv、...)拆分为 26 个文件，以加快速度。

4. Whoosh是一个搜索库，因为它创建了一次索引就引起了我的注意。但是，我不确定它是否完全适用于我的用例，因为它看起来像是全文搜索，我不能仅限于查找第一列。如果这个特定库不是一个选项，是否有任何其他方法可以在 Python 中创建可重用索引以支持这些类型的查找？

我非常乐于接受想法，我绝不会局限于上述四个选项!

谢谢你:)

Answer 1

类似于方法 2 的方法怎么样。您仍然可以将文件读入内存，但可以将文件存储到 hash map 中，而不是将其存储到列表中并使用二进制搜索来搜索键。 .

这样做的好处是可以利用 HashMap 的 O(1) 平均查找时间和 O(n) 的最坏情况。可以找到时间复杂度的好处和理由 here和 here .由于您只是在查找键，因此拥有恒定的查找时间将是搜索文件的好方法。这种方法也比二进制搜索的平均 O(log n) 搜索时间更快。

您可以将文件存储为

table = {
    key1: (value1, value2),
    key2: (value1, value2),
    key2: (value1, value2)
}

请注意，此方法仅在您的键全部不同且没有重复键时才可行。