高效循环比较字符串列表元素和字符串列表子元素的方法

Question

我目前在寻找一种有效的方法来比较附加到列表中的字符串元素的一部分与另一个字符串元素。当前的代码计算非常耗时（第一个列表中有480万个元素，第二个列表中有5000个元素，需要1小时）。

我需要做的是：如果第一个字符串元素的前8个字符等于完整的第二个元素，则使用第一个元素更新第三个列表。一旦找到，我们测试第一个列表的另一个元素。

以下是代码：

for first_element in first_List :
    for second_element in second_List:
        if first_element[:8] == second_element :
            third_List.append(first_element)
            break

我知道那些循环不是处理非常大的列表的最佳方式。if测试的数量确实非常庞大。 我想知道有没有高效的方法可以解决这个问题。

我认为使用集合的交集可能行不通，因为我需要将第一个元素的一部分与完整的第一个元素进行比较，并且我需要将完整的第一个元素复制到第三个列表中。

如果您有一些建议或想法，请告诉我好吗？

- Codje

---

你可以考虑使用blist包中的sortedlist来处理第二个列表，并通过使用if first_element[:8] in second_sorted_List跳过第二个循环。 - Jan Kuiken

Answer 1

这个有效：

second_set = set(second_list)
third_list = [value for value in first_list if value[:8] in second_set]

例子：

>>> first_list = ['abcdfghij', 'xyzxyzxyz', 'fjgjgggjhhh']
>>> second_list = ['abcdfghi', 'xyzxyzxy', 'xxx']
>>> second_set = set(second_list)
>>> third_list = [value for value in first_list if value[:8] in second_set]
>>> third_list
['abcdfghij', 'xyzxyzxyz']

这应该更加高效。将列表second_list转换为集合的时间复杂度为O(n)。在first_list上只有一个循环，时间复杂度为O(n)。在set中查找，即in second_set的时间复杂度为O(1)。

- Mike Müller

---

在列表推导式中创建set会比仅检查列表更慢。 - Padraic Cunningham

@PadraicCunningham 没错，已经修复了。创建集合只需要一次即可。 ;) - Mike Müller

Answer 2

考虑使用哈希集合，或者在Python中只是Set。 哈希集合的好处是它可以非常快速地检查元素是否在集合中（O（1）），在您的情况下，通过迭代列表来改善运行时间的O（n）解决方案的因子最多可提高5000倍。

- pseudoDust

Answer 3

创建一个新列表，其元素来自于first_List，前提是它的前8个字符存在于second_List中：

third_List = [x for x in first_List if x[:8] in second_List]

这种方法应该优化使用 second_Set 而不是 second_List:

second_Set = set(second_List)

- dlask