Изобретая класс Counter из коллекции коллекций

Question

Ради интереса я попытался изобрести класс Counter из модуля collections.

Мое намерение было простым.Учитывая список, сопоставьте элемент частоте, с которой он встречается.

Вот что я написал:

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

Просто интересно, насколько это хорошо или плохо?

Answer 1

Давайте сконцентрируемся на единственной релевантной части:

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

Это очень плохо, для каждого члена он вызывает .count(), а .count() охватывает каждого члена, поэтому сложность равна O (n ^2).

Это 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

Answer 2

Ну, это может быть быстрее, вы перебираете список n * n раз; где n - длина списка. Если бы вы вместо этого просто просматривали список и увеличивали значение этого элемента в своей таблице частот каждый раз, когда сталкивались с ним, вы бы выполняли меньше работы (n много раз, поэтому не считая времени, потраченного словарем, которое я держал бы, постоянно .)

С другой стороны, ваша версия концептуально проста и понятна.