[Salesforce] Listのintersection(積集合)の高速化 の Python版です。
数万件の要素があるような二つのListでIntersectionを以下のようにループのループで取ってしまうと O(n^2)
になるため、AWS Lambdaの実行時間制限15分に抵触してしまったりしてうまくありません。
list1 = [1, 2, ... , 50000]
list2 = [25001, 25002, ... , 75000]
results = []
for e1 in list1:
for e2 in list2:
if e1 == e2:
results.append(e1)
そこで、片方のListをSet化することで計算量を O(n1 + n2)
にできます。
list1 = [1, 2, ... , 50000]
list2 = [25001, 25002, ... , 75000]
set2 = set(list2) # O(n2)
results = []
for n in list1: # O(n1)
if n in set2: # O(1)
results.append(n) # O(1)