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

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

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

concat_list = '$'.join(l)

现在使用 simple .find('$3,')，它会更快。如果所有字符串都相对较短，则可能会发生这种情况。从现在开始，所有字符串都在内存中的一个位置。

---

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

---

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

Answer 2

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']会回来的'301\t301\t51.806763'。

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

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

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