列表中最常见的Python元素

Question

什么是在Python列表中查找最常见元素的有效方法？

我的列表项可能不可排列，因此不能使用字典。 同样在绘制的情况下，应返回索引最低的项目。例如：

>>> most_common(['duck', 'duck', 'goose']) 
'duck' 
>>> most_common(['goose', 'duck', 'duck', 'goose']) 
'goose' 

Answer 1

随着提议，我很惊讶，没有人提出这么多的解决方案，我会考虑一个明显的例子（用于非可排除但可比的元素） - [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]的项目]的元组。

然后辅助功能使用一个循环，以确定该组的可迭代，和最小原始索引条目的两个计数;它会将它们作为组合“质量关键点”返回，并且最小索引符号发生变化，因此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日志N）的方法之一是使用只是去太多对可扩展性的粮食 - ！）

最后，对于那些喜欢“清晰度和性能”的人来说，奖金1班轮版本适当地修改了名字:-)。

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] 

Answer 2

如果他们不哈希的，可以对它们进行排序，并做一个遍历结果计数的项目（同一项目将彼此相邻）。但是使它们可以被哈希和使用字典可能会更快。

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 

Answer 3

排序列表的副本，发现最长的运行。您可以在使用每个元素的索引对其进行排序之前修饰列表，然后选择以平局为单位从最低索引开始的运行。

Answer 4

这是明显慢溶液（为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））最差排序。

Answer 5

这里：

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 

我有一个模糊的感觉存在于某处，这将使你的每个元素的计数标准库的方法，但我不能找到它。

Answer 6

>>> 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' 

Answer 7

一个班轮：

def most_common (lst): 
    return max(((item, lst.count(item)) for item in set(lst)), key=lambda a: a[1])[0]

Answer 8

一个更简单的一行：

def most_common(lst): 
    return max(set(lst), key=lst.count) 

Answer 9

# 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' 

Answer 10

这是一个为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 

（逆转的使用，以确保它返回最低的索引项）

Answer 11

您可能不需要这个了，但这是我为类似问题所做的。 （它看起来长于这是因为评论。）

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's higher than the existing itemCount 
    if counter[item] > maxItemCount: 
     maxItemCount = counter[item] 
     mostPopularItem = item 

print mostPopularItem 

Answer 12

借用here，这可以使用Python 2.7使用：比Alex的解决方案快

from collections import Counter 

def Most_Common(lst): 
    data = Counter(lst) 
    return data.most_common(1)[0][0] 

作品约4-6倍，比newacct提出的单线快50倍。

要检索第一次出现在列表中关系的情况下，元素：

def most_common(lst): 
    data = Counter(lst) 
    return max(lst, key=data.get) 

Answer 13

要在统计数据模式是已知的，当然Python有一个内置函数来完成这一功能是什么为您提供：

>>> from statistics import mode 
>>> mode([1, 2, 2, 3, 3, 3, 3, 3, 4, 5, 6, 6, 6]) 
3 

Answer 14

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) 

Answer 15

def most_common(lst): 
    if max([lst.count(i)for i in lst]) == 1: 
     return False 
    else: 
     return max(set(lst), key=lst.count) 

Answer 16

我需要做这在最近的节目。我承认，我无法理解亚历克斯的答案，所以这就是我最终的结果。

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元以上（经测试可达200​​000）是慢约20％。