Quickly remove tuples that contain tuples of other list

user_4803006 0
Viewed 102

I would like to remove all the tuples in List A that contain a tuple in List B.

This is normally a trivial matter, but I have 10 million records in List A and 200K in List B. My current script (see below) is very slow (~10 seconds for each scan of List A).

Example:

# 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),...]

Current script that is slow:

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= []
data-transform subset tuples for-loop python
1 Answers

Using itertools.combinations and 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))]

Or assuming every tuple is sorted (if not, you could of course sort them first):

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