Idiomatic, Linear-time, Dictionary of Counts in Python

Question

I have some list:

list =  ["apple", "orange", "orange", "apple", "grape"]

I want to turn this into a dictionary where the key is the fruit, and the value is the number of times it occurs in the list. The list could be rather large, so it would be good for it to be linear time.

This is rather easy to do in a verbose way:

from collections import DefaultDict
dict_of_counts = DefaultDict(int)
for item in list:
    dict_of_counts[item] += 1

This is clearly O(n) time, but it feels like I should be able to do it via a dictionary comprehension. The only things I can think of though involve multiple calls to len or count, so it would be O(kn) time (where k is the distinct number of keys in my list).

Can someone point to a more "pythonic" way to do this (which I'd imagine involves the comprehension), or should I keep the above, verbose, implementation?

@user3483203 I don't plan to, nor do my lists truly contain fruit. — Mark, Sep 09 '18 at 05:09
Try using a [defaultdict](https://stackoverflow.com/questions/26731675/python-count-occurrences-in-a-list-using-dict-comprehension-generator) — Miraj50, Sep 09 '18 at 05:12
@U9-Forward Check out the link. The answer is there most probably. Its faster, I guess. — Miraj50, Sep 09 '18 at 05:19
@Miraj50 Yeah, not always, Btw it's not efficient at all, and the ashwini doesn't recommend this at all, says "(not recommended at all :-))" — U13-Forward, Sep 09 '18 at 05:25
@U9-Forward I believe, you didn't read the whole answer. Jump to the `defauldict` part. — Miraj50, Sep 09 '18 at 06:02

U13-Forward · Answer 1 · 2018-09-09T05:05:54.683

1

Use Counter:

>>> from collections import Counter
>>> l =  ["apple", "orange", "orange", "apple", "grape"]
>>> Counter(l)
Counter({'apple': 2, 'orange': 2, 'grape': 1})
>>>

And also easy to convert back:

>>> c=Counter(l)
>>> list(c.elements())
['apple', 'apple', 'orange', 'orange', 'grape']
>>>

And if want a dict:

>>> dict(c)
{'apple': 2, 'orange': 2, 'grape': 1}
>>>

BTW don't name variables any existing object (now list)

Or another way is:

>>> {i:l.count(i) for i in l}
{'apple': 2, 'orange': 2, 'grape': 1}
>>>

edited Sep 09 '18 at 05:05

answered Sep 09 '18 at 04:59

U13-Forward

69,221
14
89
114

Is {i:l.count(i) for i in l} O(n), or is it O(kn) as my post initially implied? I would expect the later, but haven't looked into the implementation of count. – Mark Sep 09 '18 at 05:10
@Mark I am not sure, but anyway use `Counter` don't really use the other – U13-Forward Sep 09 '18 at 05:12
2

@Mark it is not linear, as you search the entire list each time for each element – user3483203 Sep 09 '18 at 05:33

score 0 · Answer 2 · answered Sep 09 '18 at 05:00

0

You can use collections.Counter:

from collections import Counter
l = ["apple", "orange", "orange", "apple", "grape"]
print(dict(Counter(l)))

This outputs:

{'apple': 2, 'orange': 2, 'grape': 1}

answered Sep 09 '18 at 05:00

blhsing

91,368
6
71
106

Idiomatic, Linear-time, Dictionary of Counts in Python

2 Answers2