CODEWITHSUNDEEP
pythonlistpython-2.7dictionary
DBWeinstein
DBWeinstein

Reputation: 9519

How to count size of lists with a dict?

If I have a dict of lists like:

{
    'id1': ['a', 'b', 'c'],
    'id2': ['a', 'b'],
    # etc.
}

and I want to tally the size of the lists, i.e.. the number of ids >0, >1, >2...etc

Is there an easier way than nested for loops like this:

dictOfOutputs = {}
for x in range(1,11):
    count = 0
    for agentId in userIdDict:
        if len(userIdDict[agentId]) > x:
            count += 1
    dictOfOutputs[x] = count        
return dictOfOutputs

Upvotes: 6

Views: 568

Answers (2)

taleinat
taleinat

Reputation: 8721

Yes, there is a better way.

First, index the ids by the length of their data:

my_dict = {
    'id1': ['a', 'b', 'c'],
    'id2': ['a', 'b'],
}

from collections import defaultdict
ids_by_data_len = defaultdict(list)

for id, data in my_dict.items():
    my_dict[len(data)].append(id)

Now, create your dict:

output_dict = {}
accumulator = 0
# note: the end of a range is non-inclusive!
for data_len in reversed(range(1, max(ids_by_data_len.keys()) + 1):
    accumulator += len(ids_by_data_len.get(data_len, []))
    output_dict[data_len-1] = accumulator

This has O(n) complexity rather than O(n²), so it's also much faster for large sets of data.

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1124238

I'd use a collections.Counter() object to collect lengths, then accumulate the sums:

from collections import Counter

lengths = Counter(len(v) for v in userIdDict.values())
total = 0
accumulated = {}
for length in range(max(lengths), -1, -1):
    count = lengths.get(length, 0)
    total += count
    accumulated[length] = total

So this collects counts for each length, then builds a dictionary with accumulative lengths. This is a O(N) algorithm; you loop over all values once, then add on some smaller straight loops (for max() and the accumulation loop):

>>> from collections import Counter
>>> import random
>>> testdata = {''.join(random.choice('abcdefghijklmnopqrstuvwxyz') for _ in range(5)): [None] * random.randint(1, 10) for _ in range(100)}
>>> lengths = Counter(len(v) for v in testdata.values())
>>> lengths
Counter({8: 14, 7: 13, 2: 11, 3: 10, 4: 9, 5: 9, 9: 9, 10: 9, 1: 8, 6: 8})
>>> total = 0
>>> accumulated = {}
>>> for length in range(max(lengths), -1, -1):
...     count = lengths.get(length, 0)
...     total += count
...     accumulated[length] = total
... 
>>> accumulated
{0: 100, 1: 100, 2: 92, 3: 81, 4: 71, 5: 62, 6: 53, 7: 45, 8: 32, 9: 18, 10: 9}

Upvotes: 2

Related Questions