python compare a list of lists efficiently

Question

I have a long list of long lists so efficiency is an issue for me. I wondered if there was a neater way of comparing a list of lists other than looping over a list within a loop of the same list (easier to see by example)

matchList=[]
myList = [ ('a',[1,2,3]), ('b', [2,3,4]), ('c', [3,4,5]), ('d', [4,5,6]) ]

tup_num=1
for tup in myList:
    for tup2 in myList[tup_num:]:
        id=str(tup[0])+':'+str(tup2[0])
        matches=set(tup[1]) & set(tup2[1])
        matchList.append((id,matches))
    tup_num+=1

print matchList

Output:

[('a:b', set([2, 3])), ('a:c', set([3])), ('a:d', set([])), ('b:c', set([3, 4])), ('b:d', set([4])), ('c:d', set([4, 5]))]

This works and doesn't repeat comparisons but I'm sure there must be a better way of doing it.

Cheers

why are you sure that there is another way? you need to compare all elements. How can you do it without looking at each if they all match? — akonsu
– akonsu, Commented Nov 5, 2013 at 13:38

falsetru · Accepted Answer · 2013-11-05 13:39:44Z

1

Using itertools.combinations:

>>> import itertools
>>> matchList = []
>>> myList = [('a',[1,2,3]), ('b', [2,3,4]), ('c', [3,4,5]), ('d', [6,7,8])]
>>> matchList = [
...     ('{}:{}'.format(key1, key2), set(lst1) & set(lst2))
...     for (key1, lst1), (key2, lst2) in itertools.combinations(myList, 2)
... ]
>>> matchList
[('a:b', set([2, 3])), ('a:c', set([3])), ('a:d', set([])), ('b:c', set([3, 4])), ('b:d', set([])), ('c:d', set([]))]

answered Nov 5, 2013 at 13:39

falsetru

371k69 gold badges768 silver badges659 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

utdemir · Accepted Answer · 2013-11-05 13:46:13Z

Convert those list to sets at first. That's an O(n) operation, which better avoided.
itertools.combinations is faster and easier.

Like this:

>>> from itertools import combinations
>>> l
[('a', [1, 2, 3]), ('b', [2, 3, 4]), ('c', [3, 4, 5]), ('d', [6, 7, 8])]
>>> l = [(i, set(j)) for i, j in l]
>>> l
[('a', {1, 2, 3}), ('b', {2, 3, 4}), ('c', {3, 4, 5}), ('d', {8, 6, 7})]
>>> [("%s:%s" % (l1[0], l2[0]), l1[1] & l2[1]) for l1, l2 in combinations(l, 2)]
[('a:b', {2, 3}), ('a:c', {3}), ('a:d', set()), ('b:c', {3, 4}), ('b:d', set()), ('c:d', set())]

Kenan Banks · Accepted Answer · 2013-11-05 13:51:09Z

Using composition and generators makes it clear:

from itertools import combinations

matchList = []
myList = [ ('a',[1,2,3]), ('b', [2,3,4]), ('c', [3,4,5]), ('d', [4,5,6]) ]

def sets(items):
  for name, tuple in items:
    yield name, set(tuple)

def matches(sets):
  for a, b in combinations(sets, 2):
    yield ':'.join([a[0], b[0]]), a[1] & b[1]

print list(matches(sets(myList)))


>>> [('a:b', set([2, 3])), ('a:c', set([3])), ('a:d', set([])), ('b:c', set([3, 4])), ('b:d', set([4])), ('c:d', set([4, 5]))]

Collectives™ on Stack Overflow

python compare a list of lists efficiently

3 Answers 3

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Linked

Related