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

Question

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

我需要做什么：如果第一个字符串元素的前 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 测试的数量确实很大。我想知道是否有一种有效的方法来做到这一点。

我认为与集合的交集不起作用，因为我正在将元素的一部分与完整元素进行比较，我需要在第三个列表中复制完整的第一个元素。

请问您有什么建议或想法吗？

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)。

Answer 2

考虑使用哈希集，或仅在 python 中使用 Set。哈希集的好处是它可以非常快地检查元素是否在集合中（O（1）），在您的情况下，运行时间比迭代的 O（n）解决方案提高了 5000 倍每次都是列表。

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)

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

Efficient way to loop on comparing string list element to a string list sub-element

python

string

intersection

list