목록에서 가장 일반적인 요소 찾기

목록에서 가장 일반적인 요소 찾기

---

파이썬 목록에서 가장 일반적인 요소를 찾는 효율적인 방법은 무엇입니까?

내 목록 항목을 해시 할 수 없으므로 사전을 사용할 수 없습니다. 또한 추첨의 경우 가장 낮은 색인을 가진 항목을 반환해야합니다. 예:

>>> 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]] 두 항목이있는 튜플 입니다.

그런 다음 보조 함수는 루프를 사용하여 그룹의 반복 가능한 항목 수 와 최소 원본 인덱스를 결정합니다. 최소 인덱스가 변경되어 조합 된 "품질 키"로 이들을 리턴하므로 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 log N)를 사용할 수있을 때 의도적으로 O (N 제곱) 접근 방식을 선택하면 확장 성 수준에 비해 너무 많이 진행됩니다!-)

마지막으로, 명확성과 성능보다 "oneliners"를 선호하는 사람들을 위해 적절하게 엉망인 이름을 가진 보너스 1-liner 버전 :-).

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)

---

here 에서 빌리면 Python 2.7에서 사용할 수 있습니다.

from collections import Counter

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

Alex의 솔루션보다 약 4-6 배 더 빠르게 작동하며 newacct에서 제안한 1- 라이너보다 50 배 더 빠릅니다.

관계가있는 경우 목록에서 처음 나타나는 요소를 검색하려면 다음을 수행하십시오.

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

상위 2 개가 묶인 경우와 같이 "가장 일반적인 요소"가없는 경우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's 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

대부분의 시간에 반복되는 목록의 요소 번호

---

여기:

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

표준 라이브러리 어딘가에 각 요소의 수를 알려주는 방법이 있지만 모호한 느낌이 들지만 찾을 수 없습니다.

---

정렬이나 해싱이 가능하지 않지만 동등 비교 ( ==)를 사용할 수있는 경우 이는 명백한 느린 해결책 (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]

But making your items hashable or sortable (as recommended by other answers) would almost always make finding the most common element faster if the length of your list (n) is large. O(n) on average with hashing, and O(n*log(n)) at worst for sorting.

---

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

---

I needed to do this in a recent program. I'll admit it, I couldn't understand Alex's answer, so this is what I ended up with.

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

I timed it against Alex's solution and it's about 10-15% faster for short lists, but once you go over 100 elements or more (tested up to 200000) it's about 20% slower.

---

 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)

참고URL : https://stackoverflow.com/questions/1518522/find-the-most-common-element-in-a-list