Efficient way to either create a list, or append to it if one already exists?

Question

I'm going through a whole bunch of tuples with a many-to-many correlation, and I want to make a dictionary where each b of (a,b) has a list of all the a's that correspond to a b. It seems awkward to test for a list at key b in the dictionary, then look for an a, then append a if it's not already there, every single time through the tuple digesting loop; but I haven't found a better way yet. Does one exist? Is there some other way to do this that's a lot prettier?

Answer 1

you can sort your tuples O(n log n) then create your dictionary O(n)

or simplier O(n) but could impose heavy load on memory in case of many tuples:

your_dict = {}
for (a,b) in your_list:
    if b in your_dict:
        your_dict[b].append(a)
    else:
        your_dict[b]=[a]

Hmm it's pretty much the same as you've described. What's awkward about that?

You could also consider using an sql database to do the dirty work.

Answer 2

I am not sure how you will get out of the key test, but once they key/value pair has been initialized it is easy :)

d = {}
if 'b' not in d:
  d['b'] = set()
d['b'].add('a')

The set will ensure that only 1 of 'a' is in the collection. You need to do the initial 'b' check though to make sure the key/value exist.

Answer 3

See the docs for the setdefault() method:

setdefault(key[, default])
If key is in the dictionary, return its value. If not, insert key with a value of default and return default. default defaults to None.

You can use this as a single call that will get b if it exists, or set b to an empty list if it doesn't already exist - and either way, return b:

>>> key = 'b'
>>> val = 'a'
>>> print d
{}
>>> d.setdefault(key, []).append(val)
>>> print d
{'b': ['a']}
>>> d.setdefault(key, []).append('zee')
>>> print d
{'b': ['a', 'zee']}

Combine this with a simple "not in" check and you've done what you're after in three lines:

>>> b = d.setdefault('b', [])
>>> if val not in b:
...   b.append(val)
... 
>>> print d
{'b': ['a', 'zee', 'c']}

Answer 4

Assuming you're not really tied to lists, defaultdict and set are quite handy.

import collections
d = collections.defaultdict(set)
for a, b in mappings:
    d[b].add(a)

If you really want lists instead of sets, you could follow this with a

for k, v in d.iteritems():
    d[k] = list(v)

And if you really want a dict instead of a defaultdict, you can say

d = dict(d)

I don't really see any reason you'd want to, though.

Answer 5

Use collections.defaultdict

your_dict = defaultdict(list)
for (a,b) in your_list:
    your_dict[b].append(a)

Answer 6

Instead of using an if, AFAIK it is more pythonic to use a try block instead.

your_list=[('a',1),('a',3),('b',1),('f',1),('a',2),('z',1)]

your_dict={}
for (a,b) in your_list:
    try:
        your_dict[b].append(a)
    except KeyError:
        your_dict[b]=[a]

print your_dict