I have a counter like below:

counter = Counter({'a': 2, 'b': 1, 'c': 1, 'd':1, 'e':1})

I want to update its count based on lookup from another dictionary, dict1, which stores compatibility information of keys in the counter. For example, in dict1,

'a': ['b','d']

'a' is compatible with 'b' and 'd', so I want to update a's count from 2 to 4, because it is both compatible with b and d.

I wrote this piece of code, but it uses two loops. Is it possible to use one loop to achieve the same effect?

counter = Counter({'a': 2, 'b': 1, 'c': 1, 'd':1, 'e':1})
dict1 = {'a': ['b','d'], 'b':['a','d'], 'd':['a','b'], 'c':['e'], 'e':['c']}

keys = list(counter.keys())
count = len(keys)
for i in range(count):
    current = keys[i]
    for j in range(i 1, count):
        next = keys[j]
        comps = dict1.get(current, None)
        if comps and next in comps:
            counter[current]  = 1

CodePudding user response：

No, you can't do better than quadratic.

Let n be the number of keys in the counter. Then, each key can be compatible with O(n) other keys, for which we must do linear work in order to enumerate. There are n keys, so we have an operation that must take at least O(n) time, repeated across n keys, meaning that the best we can do is O(n^2).

CodePudding user response：

I don't think it can be done in linear time since you need to sum over all compatible values for all keys in counter. You can do this much more cleanly though:

In [3]: {k: sum(map(counter.get, dict1[k]), v) for k, v in counter.items()}
Out[3]: {'a': 4, 'b': 4, 'c': 2, 'd': 4, 'e': 2}

BTW I don't think your result is correct, unless I'm misunderstanding your logic.