Python:找到两个列表中存在的给定长度的公共(public)子列表

Question

我必须找到一个高效的 p​​ython 代码来执行以下操作:

至少找到一个包含在两个给定列表中的 n 连续元素序列(如果存在)。

例如，n=3，这两个列表的结果将是 ['Tom', 'Sam', 'Jill']:

lst1 = ['John', 'Jim', 'Tom', 'Sam', 'Jill', 'Chris']
lst2 = ['Chris', 'John', 'Tom', 'Sam', 'Jill', 'Jim']

下面的示例代码可以解决问题，但如果我必须比较数十万行/列表，则需要永远执行相同的操作。对于如何优化此代码处理大量数据的性能的任何建议，我们将不胜感激!

lst1 = ['John', 'Jim', 'Tom', 'Sam', 'Jill', 'Chris']
lst2 = ['Chris', 'John', 'Tom', 'Sam', 'Jill', 'Jim']
strNum = 3 #represents number of consecutive strings to search for
common_element_found = 'False'
common_elements = []

lst1length = len(lst1) - (strNum - 1)
lst2length = len(lst2) - (strNum - 1)
for x in range(lst1length):
    ConsecutiveStringX = lst1[x] + ' ' + lst1[x + 1] + ' ' + lst1[x + 2]
    for y in range(lst2length):
        ConsecutiveStringY = lst2[y] + ' ' + lst2[y + 1] + ' ' + lst2[y + 2]
        if ConsecutiveStringY == ConsecutiveStringX:
            common_element_found = 'True'
            common_elements.append(ConsecutiveStringY)
            print('Match found: ' + str(common_elements)) 
            break
    if common_element_found == 'True':
        common_element_found = 'False'
        break

Answer 1

国际工业联合会，

consecs1 = [ tuple(lst1[i:i+3]) for i in range(0, len(lst1)-2)]
consecs2 = { tuple(lst2[i:i+3]) for i in range(0, len(lst2)-2)}

for c in consecs1: 
    if c in consecs2:
         print(c)

输出

('Tom', 'Sam', 'Jill')

---

说明:您可以为 lst1 制作一个 tuples 列表，它们是可散列对象，并检查它们是否在 中>元组 的集合 从 lst2 构建(它提供 O(1) 速度)。

PS:尽管集合是无序的，但顺序是有保证的，因为循环遵循 lst1 而不是 lst2 顺序。