В вашем вопросе вы попросили самый быстрый способ сделать это.Как уже неоднократно демонстрировалось, особенно с Python, интуиция не является надежным руководством: вам нужно измерять.
Вот простой тест нескольких различных реализаций:
import sys
from collections import Counter, defaultdict
from itertools import groupby
from operator import itemgetter
from timeit import timeit
L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
def max_occurrences_1a(seq=L):
"dict iteritems"
c = dict()
for item in seq:
c[item] = c.get(item, 0) + 1
return max(c.iteritems(), key=itemgetter(1))
def max_occurrences_1b(seq=L):
"dict items"
c = dict()
for item in seq:
c[item] = c.get(item, 0) + 1
return max(c.items(), key=itemgetter(1))
def max_occurrences_2(seq=L):
"defaultdict iteritems"
c = defaultdict(int)
for item in seq:
c[item] += 1
return max(c.iteritems(), key=itemgetter(1))
def max_occurrences_3a(seq=L):
"sort groupby generator expression"
return max(((k, sum(1 for i in g)) for k, g in groupby(sorted(seq))), key=itemgetter(1))
def max_occurrences_3b(seq=L):
"sort groupby list comprehension"
return max([(k, sum(1 for i in g)) for k, g in groupby(sorted(seq))], key=itemgetter(1))
def max_occurrences_4(seq=L):
"counter"
return Counter(L).most_common(1)[0]
versions = [max_occurrences_1a, max_occurrences_1b, max_occurrences_2, max_occurrences_3a, max_occurrences_3b, max_occurrences_4]
print sys.version, "\n"
for vers in versions:
print vers.__doc__, vers(), timeit(vers, number=20000)
Результаты на моей машине:
2.7.2 (v2.7.2:8527427914a2, Jun 11 2011, 15:22:34)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)]
dict iteritems (4, 6) 0.202214956284
dict items (4, 6) 0.208412885666
defaultdict iteritems (4, 6) 0.221301078796
sort groupby generator expression (4, 6) 0.383440971375
sort groupby list comprehension (4, 6) 0.402786016464
counter (4, 6) 0.564319133759
Итак, похоже, что решение Counter несамый быстрый.И, по крайней мере, в этом случае groupby быстрее.defaultdict это хорошо, но вы платите немного за его удобство;немного быстрее использовать обычный dict с get.
Что произойдет, если список будет намного больше?Добавление L *= 10000 к тесту выше и уменьшение числа повторений до 200:
dict iteritems (4, 60000) 10.3451900482
dict items (4, 60000) 10.2988479137
defaultdict iteritems (4, 60000) 5.52838587761
sort groupby generator expression (4, 60000) 11.9538850784
sort groupby list comprehension (4, 60000) 12.1327362061
counter (4, 60000) 14.7495789528
Теперь defaultdict - явный победитель.Так что, возможно, стоимость метода «get» и потеря добавления на месте складываются (проверка сгенерированного кода оставлена в качестве упражнения).
Но с измененными тестовыми данными число уникальныхзначения элемента не изменились, так что предположительно dict и defaultdict имеют преимущество перед другими реализациями.Так что же произойдет, если мы воспользуемся большим списком, но существенно увеличим количество уникальных предметов?Замена инициализации L на:
LL = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
L = []
for i in xrange(1,10001):
L.extend(l * i for l in LL)
dict iteritems (2520, 13) 17.9935798645
dict items (2520, 13) 21.8974409103
defaultdict iteritems (2520, 13) 16.8289561272
sort groupby generator expression (2520, 13) 33.853593111
sort groupby list comprehension (2520, 13) 36.1303369999
counter (2520, 13) 22.626899004
Так что теперь Counter явно быстрее, чем решения groupby, но все же медленнее, чем iteritems версии dict и defaultdict. * 1033.*
Смысл этих примеров не в том, чтобы найти оптимальное решение.Дело в том, что зачастую не существует одного оптимального общего решения.Плюс есть и другие критерии эффективности.Требования к памяти в разных решениях будут существенно различаться, и при увеличении размера входных данных требования к памяти могут стать определяющим фактором при выборе алгоритма.
Итог: все зависит от ситуации, которую необходимо измерить.