Что такое эффективный способ найти наиболее распространенный элемент в списке Python?
Элементы моего списка могут не быть хешируемыми, поэтому нельзя использовать словарь. Также в случае жеребьевки элемент с наименьшим индексом должен быть возвращен. Пример:
>>> most_common(['duck', 'duck', 'goose'])
'duck'
>>> most_common(['goose', 'duck', 'duck', 'goose'])
'goose'
С таким количеством предлагаемых решений я поражен, что никто не предложил то, что я считаю очевидным (для не-хэшируемых, но сопоставимых элементов) - [ itertools.groupby] [1]. itertools предлагает быструю, многоразовую функциональность и позволяет делегировать некоторую сложную логику для хорошо протестированных стандартных компонентов библиотеки. Рассмотрим, например:
import itertools
import operator
def most_common(L):
# get an iterable of (item, iterable) pairs
SL = sorted((x, i) for i, x in enumerate(L))
# print 'SL:', SL
groups = itertools.groupby(SL, key=operator.itemgetter(0))
# auxiliary function to get "quality" for an item
def _auxfun(g):
item, iterable = g
count = 0
min_index = len(L)
for _, where in iterable:
count += 1
min_index = min(min_index, where)
# print 'item %r, count %r, minind %r' % (item, count, min_index)
return count, -min_index
# pick the highest-count/earliest item
return max(groups, key=_auxfun)[0]
Это может быть написано более кратко, конечно, но я нацелен на максимальную ясность. Два оператора print могут быть раскоментированы, чтобы лучше видеть механизм в действии; например, при печати без комментариев:
print most_common(['goose', 'duck', 'duck', 'goose'])
испускает:
SL: [('duck', 1), ('duck', 2), ('goose', 0), ('goose', 3)]
item 'duck', count 2, minind 1
item 'goose', count 2, minind 0
goose
Как вы видите, SL - это список пар, каждая пара - элемент, за которым следует индекс элемента в исходном списке (для реализации ключевого условия, которое, если "наиболее распространенные" элементы с одинаковым самым высоким счетом > 1, результат должен быть самым ранним из них).
groupby только по элементу (через operator.itemgetter). Вспомогательная функция, называемая один раз для группировки во время вычисления max, получает и внутренне распаковывает группу - кортеж с двумя элементами (item, iterable), где итерируемые элементы также являются корнями двух элементов, (item, original index) [[элементы SL]].
Затем вспомогательная функция использует цикл для определения как количества записей в итерабельной группе, так и минимального исходного индекса; он возвращает их как комбинированный "ключ качества" с изменением знака индекса min, поэтому операция max будет рассматривать "лучше" те элементы, которые произошли ранее в исходном списке.
Этот код может быть намного проще, если он немного беспокоится о проблемах с большими-O во времени и пространстве, например....:
def most_common(L):
groups = itertools.groupby(sorted(L))
def _auxfun((item, iterable)):
return len(list(iterable)), -L.index(item)
return max(groups, key=_auxfun)[0]
та же основная идея, просто выраженная более просто и компактно... но, увы, дополнительное O (N) вспомогательное пространство (для воплощения итераций групп в списки) и O (N квадратов) времени (для получения L.index каждого элемента). В то время как преждевременная оптимизация является корнем всего зла в программировании, сознательно выбирает подход O (N квадрат), когда доступен O (N log N), просто слишком сильно влияет на зерно масштабируемости! -)
Наконец, для тех, кто предпочитает "oneliners" для ясности и производительности, бонусная версия с одним лайнером с подходящими искаженными именами: -).
from itertools import groupby as g
def most_common_oneliner(L):
return max(g(sorted(L)), key=lambda(x, v):(len(list(v)),-L.index(x)))[0]
Простейший однострочный:
def most_common(lst):
return max(set(lst), key=lst.count)
Заимствование из здесь, это можно использовать с Python 2.7:
from collections import Counter
def Most_Common(lst):
data = Counter(lst)
return data.most_common(1)[0][0]
Работает в 4-6 раз быстрее, чем решения Alex, и в 50 раз быстрее, чем однострочный, предложенный newacct.
Чтобы получить элемент, который встречается первым в списке в случае связей:
def most_common(lst):
data = Counter(lst)
return max(lst, key=data.get)
То, что вы хотите, в статистике называется режимом, и, конечно, в Python есть встроенная функция, которая сделает это именно за вас:
>>> from statistics import mode
>>> mode([1, 2, 2, 3, 3, 3, 3, 3, 4, 5, 6, 6, 6])
3
Обратите внимание, что если не существует "самого распространенного элемента", например, случаев, когда верхние два связаны, это вызовет StatisticsError, поскольку, по статистике, в этом случае режима нет.
Если они не являются хешируемыми, вы можете отсортировать их и выполнить один цикл по результату, подсчитывая элементы (идентичные элементы будут рядом друг с другом). Но это может быть быстрее сделать их хешируемыми и использовать dict.
def most_common(lst):
cur_length = 0
max_length = 0
cur_i = 0
max_i = 0
cur_item = None
max_item = None
for i, item in sorted(enumerate(lst), key=lambda x: x[1]):
if cur_item is None or cur_item != item:
if cur_length > max_length or (cur_length == max_length and cur_i < max_i):
max_length = cur_length
max_i = cur_i
max_item = cur_item
cur_length = 1
cur_i = i
cur_item = item
else:
cur_length += 1
if cur_length > max_length or (cur_length == max_length and cur_i < max_i):
return cur_item
return max_item
Это решение O (n).
mydict = {}
cnt, itm = 0, ''
for item in reversed(lst):
mydict[item] = mydict.get(item, 0) + 1
if mydict[item] >= cnt :
cnt, itm = mydict[item], item
print itm
(обратное используется, чтобы убедиться, что оно возвращает наименьший индексный элемент)
Отсортируйте копию списка и найдите самый длинный пробег. Вы можете украсить список, прежде чем сортировать его с индексом каждого элемента, а затем выбрать прогон, начинающийся с самого низкого индекса в случае привязки.
Однострочный:
def most_common (lst):
return max(((item, lst.count(item)) for item in set(lst)), key=lambda a: a[1])[0]# use Decorate, Sort, Undecorate to solve the problem
def most_common(iterable):
# Make a list with tuples: (item, index)
# The index will be used later to break ties for most common item.
lst = [(x, i) for i, x in enumerate(iterable)]
lst.sort()
# lst_final will also be a list of tuples: (count, index, item)
# Sorting on this list will find us the most common item, and the index
# will break ties so the one listed first wins. Count is negative so
# largest count will have lowest value and sort first.
lst_final = []
# Get an iterator for our new list...
itr = iter(lst)
# ...and pop the first tuple off. Setup current state vars for loop.
count = 1
tup = next(itr)
x_cur, i_cur = tup
# Loop over sorted list of tuples, counting occurrences of item.
for tup in itr:
# Same item again?
if x_cur == tup[0]:
# Yes, same item; increment count
count += 1
else:
# No, new item, so write previous current item to lst_final...
t = (-count, i_cur, x_cur)
lst_final.append(t)
# ...and reset current state vars for loop.
x_cur, i_cur = tup
count = 1
# Write final item after loop ends
t = (-count, i_cur, x_cur)
lst_final.append(t)
lst_final.sort()
answer = lst_final[0][2]
return answer
print most_common(['x', 'e', 'a', 'e', 'a', 'e', 'e']) # prints 'e'
print most_common(['goose', 'duck', 'duck', 'goose']) # prints 'goose'
Вероятно, вам это больше не нужно, но это то, что я сделал для аналогичной проблемы. (Он выглядит длиннее, чем из-за комментариев.)
itemList = ['hi', 'hi', 'hello', 'bye']
counter = {}
maxItemCount = 0
for item in itemList:
try:
# Referencing this will cause a KeyError exception
# if it doesn't already exist
counter[item]
# ... meaning if we get this far it didn't happen so
# we'll increment
counter[item] += 1
except KeyError:
# If we got a KeyError we need to create the
# dictionary key
counter[item] = 1
# Keep overwriting maxItemCount with the latest number,
# if it higher than the existing itemCount
if counter[item] > maxItemCount:
maxItemCount = counter[item]
mostPopularItem = item
print mostPopularItem
Основываясь на ответе Луиса, но удовлетворяя условию "в случае ничьих, должен быть возвращен элемент с наименьшим индексом":
from statistics import mode, StatisticsError
def most_common(l):
try:
return mode(l)
except StatisticsError as e:
# will only return the first element if no unique mode found
if 'no unique mode' in e.args[0]:
return l[0]
# this is for "StatisticsError: no mode for empty data"
# after calling mode([])
raise
Пример:
>>> most_common(['a', 'b', 'b'])
'b'
>>> most_common([1, 2])
1
>>> most_common([])
StatisticsError: no mode for empty data
Простое решение в одну строку
moc= max([(lst.count(chr),chr) for chr in set(lst)])
Он вернет наиболее частый элемент с его частотой.
Привет, это очень простое решение с большим O (n)
L = [1, 4, 7, 5, 5, 4, 5]
def mode_f(L):
# your code here
counter = 0
number = L[0]
for i in L:
amount_times = L.count(i)
if amount_times > counter:
counter = amount_times
number = i
return number
Где нумеровать элемент в списке, который повторяется большую часть времени
Это очевидное медленное решение (O (n ^ 2)), если ни сортировка, ни хеширование невозможны, но сравнение равенства (==) доступно:
def most_common(items):
if not items:
raise ValueError
fitems = []
best_idx = 0
for item in items:
item_missing = True
i = 0
for fitem in fitems:
if fitem[0] == item:
fitem[1] += 1
d = fitem[1] - fitems[best_idx][1]
if d > 0 or (d == 0 and fitems[best_idx][2] > fitem[2]):
best_idx = i
item_missing = False
break
i += 1
if item_missing:
fitems.append([item, 1, i])
return items[best_idx]
Но создание ваших элементов хешируемыми или сортируемыми (как рекомендовано другими ответами) почти всегда заставит поиск наиболее распространенного элемента быстрее, если длина вашего списка (n) велика. O (n) в среднем с хешированием и O (n * log (n)) в худшем случае для сортировки.
Здесь:
def most_common(l):
max = 0
maxitem = None
for x in set(l):
count = l.count(x)
if count > max:
max = count
maxitem = x
return maxitem
У меня смутное чувство, что есть метод где-то в стандартной библиотеке, который даст вам счет каждого элемента, но я не могу его найти.
>>> li = ['goose', 'duck', 'duck']
>>> def foo(li):
st = set(li)
mx = -1
for each in st:
temp = li.count(each):
if mx < temp:
mx = temp
h = each
return h
>>> foo(li)
'duck'
def mostCommon(lst):
# Finds the element of highest value & occurrence
table = {}
# Counts the number of occurences for each number
for ele in lst:
if ele in table:
table[ele] = table[ele] + 1
else:
table.update( {ele : 1} )
# Inverts the keys & values
invert = lambda mydict: {v:k for k, v in mydict.items()}
table = invert(table) # Inverting is necessary to access values
# Returns highest value in dictionary
return table[ max(table.keys()) ]
Мне нужно было сделать это в недавней программе. Я признаю это, я не мог понять ответ Алекс, так что это то, с чем я закончил.
def mostPopular(l):
mpEl=None
mpIndex=0
mpCount=0
curEl=None
curCount=0
for i, el in sorted(enumerate(l), key=lambda x: (x[1], x[0]), reverse=True):
curCount=curCount+1 if el==curEl else 1
curEl=el
if curCount>mpCount \
or (curCount==mpCount and i<mpIndex):
mpEl=curEl
mpIndex=i
mpCount=curCount
return mpEl, mpCount, mpIndex
Я приурочил его к решению Alex и примерно на 10-15% быстрее для коротких списков, но как только вы переходите более чем на 100 элементов или больше (проверено до 200000), он примерно на 20% медленнее.
def mostCommonElement(list):
count = {} // dict holder
max = 0 // keep track of the count by key
result = None // holder when count is greater than max
for i in list:
if i not in count:
count[i] = 1
else:
count[i] += 1
if count[i] > max:
max = count[i]
result = i
return result
mostCommonElement(["a","b","a","c"]) → "a"
def most_common(lst):
if max([lst.count(i)for i in lst]) == 1:
return False
else:
return max(set(lst), key=lst.count)
def popular(L):
C={}
for a in L:
C[a]=L.count(a)
for b in C.keys():
if C[b]==max(C.values()):
return b
L=[2,3,5,3,6,3,6,3,6,3,7,467,4,7,4]
print popular(L)