Znajdź najpopularniejszy element na liście

Jaki jest skuteczny sposób na znalezienie najbardziej powszechnego elementu na liście w Pythonie?

Moje elementy listy mogą nie podlegać haszowaniu, więc nie można używać słownika. Również w przypadku losowań należy zwrócić pozycję o najniższym indeksie. Przykład:

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

Przy tak wielu proponowanych rozwiązaniach jestem zdumiony, że nikt nie zaproponował tego, co uważam za oczywiste (dla elementów niekasowalnych, ale porównywalnych) - [ itertools.groupby] [1]. itertoolsoferuje szybką funkcjonalność wielokrotnego użytku i pozwala delegować skomplikowaną logikę do dobrze przetestowanych komponentów bibliotek standardowych. Rozważmy na przykład:

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]

Można to oczywiście napisać bardziej zwięźle, ale dążę do maksymalnej jasności. Te dwa printstwierdzenia można pominąć, aby lepiej zobaczyć maszynę w akcji; na przykład z wydrukami bez komentarzy:

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

emituje:

SL: [('duck', 1), ('duck', 2), ('goose', 0), ('goose', 3)]
item 'duck', count 2, minind 1
item 'goose', count 2, minind 0
goose

Jak widać, SLjest to lista par, każda para to element, po którym następuje indeks elementu na pierwotnej liście (aby zaimplementować kluczowy warunek, że jeśli „najczęściej” elementy o tej samej największej liczbie są> 1, wynik musi być najwcześniej występującym).

groupbygrupuje tylko według elementu (przez operator.itemgetter). Funkcja pomocnicza, wywoływana raz na grupę podczas maxobliczania, odbiera i wewnętrznie rozpakowuje grupę - krotkę z dwoma elementami, (item, iterable)gdzie elementy iterowalne są również krotkami dwuelementowymi, (item, original index)[[elementy SL]].

Następnie funkcja pomocnicza używa pętli do określenia zarówno liczby wpisów w iterowalnej grupie, jak i minimalnego pierwotnego indeksu; zwraca je jako połączony „klucz jakości”, ze zmienionym znakiem indeksu min, więc maxoperacja uzna za „lepsze” te elementy, które wystąpiły wcześniej na pierwotnej liście.

Ten kod mógłby być znacznie prostszy, gdyby martwił się trochę mniej problemami z dużymi O w czasie i przestrzeni, np ...:

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]

ta sama podstawowa idea, po prostu wyrażona prościej i zwięźle ... ale, niestety, dodatkowa przestrzeń pomocnicza O (N) (aby ująć iterowalne grupy do list) i O (N do kwadratu) czas (aby uzyskać L.indexz każdej pozycji) . Podczas gdy przedwczesna optymalizacja jest źródłem wszelkiego zła w programowaniu, celowe wybieranie podejścia O (N do kwadratu), gdy dostępne jest O (N log N), jest po prostu zbyt duże wbrew ziarnu skalowalności! -)

Wreszcie dla tych, którzy wolą „oneliner” od przejrzystości i wydajności, bonusowa wersja 1-liniowa z odpowiednio zniekształconymi nazwami :-).

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]

Prostszy, jednoliniowy:

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

Pożyczając stąd , można tego użyć z Pythonem 2.7:

from collections import Counter

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

Działa około 4-6 razy szybciej niż rozwiązania Alexa i jest 50 razy szybszy niż jednolinijkowy proponowany przez newacct.

Aby pobrać element, który występuje jako pierwszy na liście w przypadku remisów:

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

To, czego chcesz, jest znane w statystykach jako tryb, a Python ma oczywiście wbudowaną funkcję, która robi dokładnie to za Ciebie:

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

Zwróć uwagę, że jeśli nie ma „najbardziej powszechnego elementu”, takiego jak przypadki, w których dwie pierwsze są równe , to wzrośnie StatisticsError, ponieważ statystycznie rzecz biorąc, w tym przypadku nie ma trybu .

Jeśli nie można ich haszować, można je posortować i wykonać pojedynczą pętlę po wyniku zliczając elementy (identyczne elementy będą obok siebie). Ale może być szybsze uczynienie ich haszowalnymi i użycie dyktowania.

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

To jest rozwiązanie 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

(odwrócony jest używany, aby upewnić się, że zwraca najniższą pozycję indeksu)

Bez wymogu dotyczącego najniższego indeksu możesz użyć collections.Counterdo tego:

from collections import Counter

a = [1936, 2401, 2916, 4761, 9216, 9216, 9604, 9801] 

c = Counter(a)

print(c.most_common(1)) # the one most common element... 2 would mean the 2 most common
[(9216, 2)] # a set containing the element, and it's count in 'a'

Sortuj kopię listy i znajdź najdłuższy bieg. Możesz ozdobić listę przed posortowaniem jej indeksem każdego elementu, a następnie wybrać przebieg, który w przypadku remisu zaczyna się od najniższego indeksu.

Jednowierszowy:

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'

Proste rozwiązanie w jednej linii

moc= max([(lst.count(chr),chr) for chr in set(lst)])

Zwróci najczęściej występujący element z jego częstotliwością.

Prawdopodobnie już tego nie potrzebujesz, ale to właśnie zrobiłem dla podobnego problemu. (Wygląda na dłuższą niż jest z powodu komentarzy.)

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

Opierając się na odpowiedzi Luiza , ale spełniając warunek „ w przypadku remisów pozycja o najniższym indeksie powinna zostać zwrócona ”:

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

Przykład:

>>> most_common(['a', 'b', 'b'])
'b'
>>> most_common([1, 2])
1
>>> most_common([])
StatisticsError: no mode for empty data

Tutaj:

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

Mam niejasne wrażenie, że gdzieś w standardowej bibliotece jest metoda, która poda liczbę każdego elementu, ale nie mogę jej znaleźć.

Jest to oczywiste powolne rozwiązanie (O (n ^ 2)), jeśli ani sortowanie, ani haszowanie nie są możliwe, ale ==dostępne jest porównanie równości ( ):

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]

Jednak umożliwienie hashowania lub sortowania elementów (zgodnie z zaleceniami innych odpowiedzi) prawie zawsze przyspieszyłoby znalezienie najczęściej używanego elementu, jeśli długość listy (n) jest duża. O (n) średnio z haszowaniem, a O (n * log (n)) w najgorszym przypadku do sortowania.

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

Musiałem to zrobić w ostatnim programie. Przyznaję, nie mogłem zrozumieć odpowiedzi Alexa, więc na tym skończyłem.

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

Zmierzyłem czas z rozwiązaniem Alexa i jest około 10-15% szybszy w przypadku krótkich list, ale gdy przejdziesz ponad 100 elementów lub więcej (przetestowano do 200000), jest około 20% wolniej.

Cześć, to bardzo proste rozwiązanie z dużym 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

Gdzie numerować element na liście, który powtarza się przez większość czasu

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)