获取以大列表开头的第一个值的最有效方法

Question

我有一个非常大的列表，其中包含超过 100M 的字符串。该列表的示例如下所示：

l = ['1,1,5.8067',
     '1,2,4.9700',
     '2,2,3.9623',
     '2,3,1.9438',
     '2,7,1.0645', 
     '3,3,8.9331',
     '3,5,2.6772',
     '3,7,3.8107',
     '3,9,7.1008']

我想获取第一个以例如开头的字符串'3'.

为此，我使用了 lambda 迭代器，然后使用 next() 来获取第一项：

next(filter(lambda i: i.startswith('3,'), l))

Out[1]: '3,3,8.9331'

考虑到列表的大小，不幸的是，这个策略对于我必须一遍又一遍地做的过程来说仍然需要相对多的时间。我想知道是否有人可以想出一种更快、更有效的方法。我对替代策略持开放态度。

Answer 1

由于您的实际字符串由相对较短的标记组成（例如 301），在按制表符拆分字符串后，您可以构建一个字典，其中第一个标记的每个可能长度作为键，以便后续查找的平均时间复杂度仅为 O(1)。

以相反顺序使用列表的值构建字典，以便列表中以每个不同字符开头的第一个值将保留在最终字典中：

d = {s[:i + 1]: s for s in reversed(l) for i in range(len(s.split('\t')[0]))}

因此给定：

l = ['301\t301\t51.806763\n', '301\t302\t46.970094\n',
     '301\t303\t39.962393\n', '301\t304\t18.943836\n',
     '301\t305\t11.064584\n', '301\t306\t4.751911\n']

d['3'] 将 return '301\t301\t51.806763'.

如果您只需要将每个第一个标记作为一个整体而不是前缀进行测试，您可以简单地将第一个标记作为键：

d = {s.split('\t')[0]: s for s in reversed(l)}

这样 d['301'] 就会 return '301\t301\t51.806763'。

Answer 2

我自己无法测试它，但如果您将所有字符串与不在任何字符串中的字符连接起来，则有可能：

concat_list = '$'.join(l)

现在使用简单的.find(',')，速度会更快。如果所有字符串都相对较短，则可能会发生这种情况。因为现在所有的字符串都在内存中的一个地方。

如果文本中唯一字母的数量很少，您可以使用 Abrahamson-Kosaraju 方法，实际时间复杂度为 O(n)

另一种方法是使用 joblib，当第 i 个线程正在检查 i + k * n 时创建 n 个线程，当一个线程找到模式时它会停止其他线程。所以时间复杂度是O(naive algorithm / n).

获取以大列表开头的第一个值的最有效方法

Most efficient way to get first value that startswith of large list

python

list

lambda

startswith