Быстрое удаление кортежей, содержащих кортежи из другого списка - PullRequest
Новая
       112

Быстрое удаление кортежей, содержащих кортежи из другого списка

2 голосов
/ 01 августа 2020

Я хотел бы удалить все кортежи в списке A, которые содержат кортеж в списке B.

Обычно это тривиальный вопрос, но у меня 10 миллионов записей в списке A и 200 КБ в списке B. Мой текущий сценарий (см. Ниже) очень медленный (~ 10 секунд на каждое сканирование списка A).

Пример: 

# Input:
listA = [(1,2,3,4,5),(1,2,4,5,6),(1,2,3,7,55),(8,21,22,24,37),...]  # 10 million records
listB = [(1,2,4),(1,4,6),(21,24,37),...]  # 200K records

# Desired Output (filtered listA):
listA = [(1,2,3,7,55),...]

Текущий медленный сценарий: 

listA=[(1,2,3,4,5),(1,2,4,5,6),(1,2,3,7,55),(8,21,22,24,37)]
listB=[(1,2,4),(1,4,6),(21,24,37)]
listATemp=[]

for b in listB:
  for a in listA:
    if not set(b).issubset(a) :
      listATemp.append(a)
  listA= listATemp
  listATemp= []

1 Ответ

2 голосов
/ 02 августа 2020

Использование itertools.combinations и frozenset: 

setB = set(map(frozenset, listB))
n = len(listB[0])
listA = [a for a in listA if not any(frozenset(c) in setB for c in combinations(a, n))]

Или при условии, что каждый кортеж отсортирован (если нет, вы, конечно, можете сначала отсортировать их): 

setB = set(listB)
n = len(listB[0])
listA = [a for a in listA if setB.isdisjoint(combinations(a, n))]
...