Python: Finds a public sublist of a given length that exists in two lists
I had to find an efficient python code to do the following:
Find at least one n
consecutive sequence of elements contained in two given lists, if one exists.
For example, n=3
, the result of these two lists will be [‘Tom’, ‘Sam', 'Jill']
:
lst1 = ['John', 'Jim', 'Tom', 'Sam', 'Jill', 'Chris']
lst2 = ['Chris', 'John', 'Tom', 'Sam', 'Jill', 'Jim']
The following sample code does the trick, but if I have to compare hundreds of thousands of rows/lists, I need to do the same thing forever. Any suggestions on how to optimize the performance of this code for handling large amounts of data would be appreciated!
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
Solution
International Confederation of Industry,
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)
Output
('Tom', 'Sam', 'Jill')
Description: You can make a list of tuples
for lst1
, which are hashable objects, and check if they are in the
collection of >
built from tuples
lst2
(it provides O(1) speed).
PS: Although the set is unordered, the order is guaranteed because the loop follows lst1 instead of lst2
order.