Найти самый распространенный элемент в списке

Question

Какой эффективный способ найти наиболее распространенный элемент в списке Python?

Элементы моего списка не могут быть хэшируемыми, поэтому не могут использовать словарь. Также в случае розыгрышей должен быть возвращен предмет с самым низким индексом. Пример:

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

Answer 1

Более простой однострочный:

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

Answer 2

Заимствование из здесь , это можно использовать с 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)

Answer 3

С таким количеством предложенных решений я удивлен, что никто не предложил то, что я считаю очевидным (для не хэшируемых, но сопоставимых элементов) - [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) [[items of SL]].

Затем вспомогательная функция использует цикл для определения количества записей в итерируемой группе, и минимального исходного индекса; он возвращает их как объединенный «ключ качества» с измененным знаком мин индекса, поэтому операция max будет считать «лучше» те элементы, которые встречались ранее в исходном списке.

Этот код мог бы быть намного проще, если бы он немного меньше беспокоился о проблемах большого-большого во времени и пространстве, например ....:

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" ясности и производительности, бонусная версия с 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 4

То, что вы хотите, в статистике называется режимом, и, конечно, в Python есть встроенная функция, которая сделает это именно за вас:

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

Обратите внимание, что если не существует "самого распространенного элемента", например, в случаях, когда два верхних элемента связаны , это повысит StatisticsError, поскольку, по статистике, режима в этом случае.

Answer 5

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

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 6

Это решение 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 7

Сортируйте копию списка и найдите самый длинный пробег. Вы можете украсить список перед сортировкой по индексу каждого элемента, а затем выбрать прогон, который начинается с самого низкого индекса в случае привязки.

Answer 8

Однострочник:

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

Answer 9

Возможно, вам это больше не нужно, но это то, что я сделал для аналогичной проблемы (Это выглядит длиннее, чем из-за комментариев.)

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 10

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