Reinventing the Counter class from collections module

Just for fun, I tried reinventing the Counter class from the collections module.

My intent was simple. Given a list, map the element to frequency in which it occurs.

Here is what I wrote:

>>> l
['a', 'a', 'b', 'c']
>>> d = {}
>>> for a in l:
    d[a] = l.count(a)
>>> d
{'a': 2开发者_StackOverflow, 'c': 1, 'b': 1}

Just wondering, how good or bad is this?

---

Let's concentrate on the only relevant part:

for a in l:
    d[a] = l.count(a)

This is pretty bad, it calls .count() for EVERY member and .count() goes over every member itself so this complexity is O(n^2).

This is O(n):

l = ['a', 'a', 'b', 'c']
d = {}
for a in l:
    if a in d: # we saw a before
        d[a] += 1
    else:
        d[a] = 1

---

Well it could be quicker, you are iterating over the list n * n times; where n is the length of the list. If you instead just went over the list and incremented that element's value in your frequency table whenever you encounter it, you would do less work (n many times so, not counting any time spent by the dictionary which I'd wager is constant.)

On the other hand, your version is conceptually simple and clear.