Suchen Sie das häufigste Element in einer Liste

174

Was ist ein effizienter Weg, um das häufigste Element in einer Python-Liste zu finden?

Meine Listenelemente sind möglicherweise nicht hashbar und können daher kein Wörterbuch verwenden. Auch bei Ziehungen sollte der Artikel mit dem niedrigsten Index zurückgegeben werden. Beispiel:

>>> most_common(['duck', 'duck', 'goose'])
'duck'
>>> most_common(['goose', 'duck', 'duck', 'goose'])
'goose'
hoju
quelle
2
Wenn die Elemente in der Liste nicht hashbar sind, wie würden Sie feststellen, wann sie "gleich" sind? Der Effizienzverlust bei der Bestimmung der Gleichheit für nicht hashbare Elemente würde wahrscheinlich jede Effizienz zunichte machen, die Sie mit einem guten Algorithmus erzielen möchten :)
HS.
3
Ich denke, er meint, dass die Gegenstände veränderlich und daher nicht elegant sein können, um Schlüssel in einer Hashmap zu sein ...
fortran
1
Ja, das habe ich gemeint - manchmal enthält es Listen
Hoju
Der beste Weg , stackoverflow.com/a/50227350/7918560
BreakBadSP

Antworten:

96

Bei so vielen vorgeschlagenen Lösungen bin ich erstaunt, dass niemand vorgeschlagen hat, was ich für offensichtlich halte (für nicht hashbare, aber vergleichbare Elemente) - [ itertools.groupby] [1]. itertoolsbietet schnelle, wiederverwendbare Funktionen und ermöglicht es Ihnen, einige knifflige Logik an bewährte Standardbibliothekskomponenten zu delegieren. Betrachten Sie zum Beispiel:

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]

Dies könnte natürlich präziser geschrieben werden, aber ich strebe nach maximaler Klarheit. Die beiden printAussagen können unkommentiert werden, um die Maschinerie in Aktion besser zu sehen. Zum Beispiel mit unkommentierten Abzügen:

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

emittiert:

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

Wie Sie sehen, SLhandelt es sich um eine Liste von Paaren, wobei jedes Paar ein Element gefolgt vom Index des Elements in der ursprünglichen Liste ist (um die Schlüsselbedingung zu implementieren, dass das Ergebnis sein muss, wenn die "häufigsten" Elemente mit derselben höchsten Anzahl> 1 sind am frühesten auftreten).

groupbyGruppen nur nach Artikel (via operator.itemgetter). Die Hilfsfunktion, die während der maxBerechnung einmal pro Gruppierung aufgerufen wird , empfängt und entpackt intern eine Gruppe - ein Tupel mit zwei Elementen, (item, iterable)wobei die Elemente des Iterables auch Tupel mit zwei Elementen sind, (item, original index)[[die Elemente von SL]].

Dann verwendet die Hilfsfunktion eine Schleife, um sowohl die Anzahl der Einträge in der iterierbaren Gruppe als auch den minimalen ursprünglichen Index zu bestimmen . Diese werden als kombinierter "Qualitätsschlüssel" zurückgegeben, wobei das Vorzeichen des Min-Index geändert wird, sodass die maxOperation die Elemente berücksichtigt, die zuvor in der ursprünglichen Liste aufgetreten sind.

Dieser Code könnte viel einfacher sein, wenn er sich ein wenig weniger Gedanken über Big-O-Probleme in Zeit und Raum macht, z. B.::

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]

Dieselbe Grundidee, nur einfacher und kompakter ausgedrückt ... aber leider ein zusätzlicher O (N) -Hilfsraum (um die Iterablen der Gruppen in Listen zu verkörpern) und O (N-Quadrat) -Zeit (um die L.indexvon jedem Element zu erhalten) . Während vorzeitige Optimierung die Wurzel allen Übels in der Programmierung ist, widerspricht die bewusste Auswahl eines O (N-Quadrat) -Ansatzes, wenn ein O (N log N) verfügbar ist, einfach zu sehr der Skalierbarkeit! -)

Für diejenigen, die "Oneliners" gegenüber Klarheit und Leistung bevorzugen, eine Bonus-1-Liner-Version mit entsprechend verstümmelten Namen :-).

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]
Alex Martelli
quelle
3
Dies bricht in Python3 ab, wenn Ihre Liste unterschiedliche Typen hat.
AlexLordThorsen
2
groupbyerfordert zuerst eine Sortierung (O (NlogN)); Die Verwendung eines Counter()with most_common()kann dies übertreffen, da ein Heapq verwendet wird, um das Element mit der höchsten Frequenz zu finden (für nur 1 Element entspricht dies der O (N) -Zeit). Da es Counter()jetzt stark optimiert ist (das Zählen erfolgt in einer C-Schleife), kann es diese Lösung auch für kleine Listen leicht übertreffen. Es bläst es für große Listen aus dem Wasser.
Martijn Pieters
Nur die Anforderung des niedrigsten Index für Bindungen macht dies zu einer gültigen Lösung für genau dieses Problem. Für den allgemeineren Fall sollten Sie auf jeden Fall den Counter-Ansatz verwenden.
Martijn Pieters
@MartijnPieters Vielleicht haben Sie den Teil der Frage verpasst, in dem angegeben wurde, dass die Elemente möglicherweise nicht zerlegbar sind.
wim
@wim richtig, und wenn Elemente nicht zerlegbar sind. Umso unpassender sind die Stimmen am Set und der Max-Ansatz.
Martijn Pieters
442

Ein einfacher Einzeiler:

def most_common(lst):
    return max(set(lst), key=lst.count)
newacct
quelle
24
Das OP gab an, dass [..] im Falle von Ziehungen der Artikel mit dem niedrigsten Index zurückgegeben werden sollte. Dieser Code erfüllt diese Anforderung im Allgemeinen nicht.
Stephan202
2
Außerdem gab das OP an, dass die Elemente hashbar sein müssen: Mengen müssen hashbare Objekte enthalten.
Eric O Lebigot
2
Außerdem ist dieser Ansatz algorithmisch langsam (für jedes Element in set(lst)muss die gesamte Liste erneut überprüft werden)… Wahrscheinlich jedoch schnell genug für die meisten Anwendungen…
Eric O Lebigot,
9
Sie können ersetzen set(lst)mit lstund es wird auch mit nicht-hashable Elementen arbeiten; wenn auch langsamer.
Newacct
24
Dies mag attraktiv aussehen , aber aus algorithmischer Sicht ist dies ein schrecklicher Rat. list.count()muss die Liste vollständig durchlaufen , und Sie tun dies für jedes einzelne eindeutige Element in der Liste. Dies macht dies zu einer O (NK) -Lösung (O (N ^ 2) im schlimmsten Fall). Die Verwendung von a Counter()dauert nur O (N)!
Martijn Pieters
185

Ausgeliehen von hier , kann dies mit Python 2.7 verwendet werden:

from collections import Counter

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

Arbeitet ungefähr 4-6 mal schneller als Alex 'Lösungen und ist 50 mal schneller als der von newacct vorgeschlagene Einzeiler.

So rufen Sie das Element ab, das bei Bindungen zuerst in der Liste vorkommt:

def most_common(lst):
    data = Counter(lst)
    return max(lst, key=data.get)
Alex
quelle
3
Dies mag für einige nützlich sein, aber ... leider ist Counter eine Diktat-Unterklasse, und das OP sagte, er könne keine Wörterbücher verwenden (da Elemente möglicherweise nicht hashbar sind).
Danimal
13
Ich liebe das. Der Einzeiler von @newacct oben mag einfach sein, läuft aber in O (n ^ 2); das heißt, wobei n die Länge der Liste ist. Diese Lösung ist O (n).
BoltzmannBrain
5
Wie die Einfachheit und die Geschwindigkeit ... vielleicht nicht ideal für OP. Aber passt mir super!
Thom
gibt nicht das niedrigste indizierte Element zurück. most_common gibt eine ungeordnete Liste zurück, und grabbing (1) gibt nur das zurück, was es möchte.
AgentBawls
@AgentBawls: most_commonist nach Anzahl sortiert, nicht ungeordnet. Das heißt, es wird nicht das erste Element bei Unentschieden auswählen; Ich habe eine andere Möglichkeit hinzugefügt, den Zähler zu verwenden, der das erste Element auswählt.
user2357112 unterstützt Monica
58

Was Sie wollen, wird in der Statistik als Modus bezeichnet, und Python verfügt natürlich über eine integrierte Funktion, die genau das für Sie erledigt:

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

Beachten Sie, dass, wenn es kein "häufigstes Element" gibt, wie z. B. Fälle, in denen die beiden obersten verknüpft sind , dies erhöht wird StatisticsError, da statistisch gesehen in diesem Fall kein Modus vorhanden ist .

Luiz Berti
quelle
8
Dies entspricht nicht der Anforderung des OP, was zurückzugeben ist, wenn es mehr als einen der häufigsten Werte gibt - eine Statistik. Statistikfehler wird ausgelöst
Keith Hall
5
Hoppla, ich habe die Anforderung beim Lesen verpasst. Ich glaube jedoch immer noch, dass diese Antwort wertvoll ist, wie niemand in dieser Frage vorgeschlagen hat, und sie ist eine gute Lösung für das Problem für Menschen mit am wenigsten restriktiven Anforderungen. Dies ist eines der Top-Ergebnisse für "am häufigsten in List Python"
Luiz Berti
1
Verwenden Sie in diesem Fall die Modusfunktion in pandas DataFrames.
Elmex80s
1
Up-Vote, dieser sollte höher sein. Und es ist nicht so schwer, die Anforderungen des OP mit einem einfachen Versuch zu erfüllen - außer (siehe meine stackoverflow.com/a/52952300/6646912 )
krassowski
1
@BreakBadSP Ihre Antwort verbraucht aufgrund des zusätzlichen Speicherplatzes mehr setund ist plausibel O(n^3).
Luiz Berti
9

Wenn sie nicht hashbar sind, können Sie sie sortieren und eine einzelne Schleife über das Ergebnis durchführen, wobei die Elemente gezählt werden (identische Elemente werden nebeneinander angezeigt). Aber es könnte schneller sein, sie hashbar zu machen und ein Diktat zu verwenden.

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
Lukáš Lalinský
quelle
Hier ist ein einfacherer Weg ideone.com/Nq81vf im Vergleich zu Alex ' Counter()Lösung
Miguel
6

Dies ist eine O (n) -Lösung.

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

(Umgekehrt wird verwendet, um sicherzustellen, dass das niedrigste Indexelement zurückgegeben wird.)

ThisIsMeMoony
quelle
5

Sortieren Sie eine Kopie der Liste und finden Sie die längste Laufzeit. Sie können die Liste dekorieren, bevor Sie sie mit dem Index jedes Elements sortieren, und dann den Lauf auswählen, der bei einem Gleichstand mit dem niedrigsten Index beginnt.

Boojum
quelle
Die Artikel sind möglicherweise nicht vergleichbar.
Pawel Furmaniak
5

Ohne die Anforderung des niedrigsten Index können Sie Folgendes verwenden collections.Counter:

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'
Der Pate
quelle
Einfach und schnell. Du bist mein Pate chain
Kettentreppe
Diese Antwort erfordert mehr Upvotes, da sie die allgemeine Aufgabe des Zählens von Elementvorkommen in einer Liste unter Verwendung eines Standardmoduls und 2 Codezeilen behandelt
pcko1
4

Ein Einzeiler:

def most_common (lst):
    return max(((item, lst.count(item)) for item in set(lst)), key=lambda a: a[1])[0]
Willurd
quelle
3
# 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'
steveha
quelle
3

Einfache einzeilige Lösung

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

Es wird das häufigste Element mit seiner Frequenz zurückgeben.

Shivam Agrawal
quelle
2

Sie brauchen das wahrscheinlich nicht mehr, aber das habe ich für ein ähnliches Problem getan. (Es sieht länger aus als es wegen der Kommentare ist.)

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
Ed Holden
quelle
1
Sie könnten counter [item] = counter.get (item, 0) + 1 verwenden, um den Versuch / Ausnahme-Teil zu ersetzen
XueYu
1

Aufbauend auf Luiz 'Antwort , aber erfüllt die Bedingung " Im Falle von Ziehungen sollte der Artikel mit dem niedrigsten Index zurückgegeben werden ":

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

Beispiel:

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

Hier:

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

Ich habe das vage Gefühl, dass es irgendwo in der Standardbibliothek eine Methode gibt, mit der Sie die Anzahl der einzelnen Elemente angeben können, aber ich kann sie nicht finden.

Lennart Regebro
quelle
3
'max' ist eine Methode. Würden Sie den Namen der Variablen ändern?
Pratik Deoghare
1
Beachten Sie, dass set () auch hashbare Elemente erfordert, da die Lösung in diesem Fall nicht funktionieren würde.
Lukáš Lalinský
Warten Sie, ich habe diesen Teil verpasst, nicht hashbar zu sein. Wenn die Objekte jedoch gleich sind, sollte es einfach sein, sie hashbar zu machen.
Lennart Regebro
0

Dies ist die offensichtlich langsame Lösung (O (n ^ 2)), wenn weder Sortieren noch Hashing möglich sind, aber ein Gleichheitsvergleich ( ==) verfügbar ist:

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]

Wenn Sie Ihre Elemente jedoch hashbar oder sortierbar machen (wie in anderen Antworten empfohlen), wird das häufigste Element fast immer schneller gefunden, wenn die Länge Ihrer Liste (n) groß ist. O (n) im Durchschnitt mit Hashing und O (n * log (n)) im schlimmsten Fall zum Sortieren.

pts
quelle
An den Downvoter: Was ist falsch an dieser Antwort? Bietet eine der anderen Antworten eine Lösung, wenn weder Sortieren noch Hashing möglich sind?
Punkte
0
>>> 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'
Pratik Deoghare
quelle
Dies hat schreckliche Leistungsmerkmale, wenn n groß ist und die Anzahl der eindeutigen Elemente ebenfalls groß ist: O (n) für die Umwandlung in eine Menge und O (m * n) = O (n ^ 2) für die Anzahl (wobei m ist die Anzahl der Unikate). Sortieren und Gehen ist O (n log n) für das Sortieren und 0 (n) für das Gehen.
jmucchiello
1
Ja, du hast recht. Jetzt weiß ich, dass dies eine schreckliche Lösung ist und warum. Danke für den Kommentar!! :-)
Pratik Deoghare
0

Ich musste dies in einem kürzlich durchgeführten Programm tun. Ich gebe es zu, ich konnte Alex 'Antwort nicht verstehen, also habe ich das erreicht.

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

Ich habe es mit Alex 'Lösung verglichen und es ist ungefähr 10-15% schneller für kurze Listen, aber sobald Sie über 100 Elemente oder mehr gehen (getestet bis 200000), ist es ungefähr 20% langsamer.

pauleohare
quelle
-1

Hallo, das ist eine sehr einfache Lösung mit großem 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

Wobei das Element in der Liste nummeriert wird, das sich die meiste Zeit wiederholt

Szene
quelle
-2
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"

Israel Manzo
quelle
alle anderen Antworten. Soll ich sie verlinken?
12 Rauten im Raster ohne Ecken
-3
 def most_common(lst):
    if max([lst.count(i)for i in lst]) == 1:
        return False
    else:
        return max(set(lst), key=lst.count)
Ecanales
quelle
6
Bitte geben Sie einige Informationen zu Ihrem Code an, nur die Veröffentlichung des Codes ist keine vollständige Antwort
jhhoff02
1
Gibt es einen Grund, warum jemand dies gegenüber den 15 anderen Antworten verwenden sollte?
Alle Arbeiter sind wesentlich
-5
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)
Pronoy
quelle