查找列表中最常见的元素

2024-12-26 08:43:00
admin
原创
120
摘要:问题描述:在 Python 列表中查找最常见元素的有效方法是什么?我的列表项可能不可哈希,因此无法使用字典。此外,在绘制时应返回索引最低的项目。示例:>>> most_common(['duck', 'duck', 'goose']) 'duck' >>> most_com...

问题描述:

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

我的列表项可能不可哈希,因此无法使用字典。此外,在绘制时应返回索引最低的项目。示例:

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

解决方案 1:

更简单的一行:

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

解决方案 2:

借用这里,它可以与 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 提出的单行代码快 50 倍。

在 CPython 3.6+(任何 Python 3.7+)上,如果出现平局,上述操作将选择第一个看到的元素。如果您在较旧的 Python 上运行,则要在出现平局的情况下检索列表中首先出现的元素,您需要执行两次传递以保持顺序:

# Only needed pre-3.6!
def most_common(lst):
    data = Counter(lst)
    return max(lst, key=data.get)

解决方案 3:

有这么多的解决方案被提出,我很惊讶没有人提出我认为显而易见的解决方案(对于不可哈希但可比较的元素)—— itertools.groupbyitertools提供快速、可重用的功能,并允许您将一些棘手的逻辑委托给经过充分测试的标准库组件。例如:

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可以取消注释这两个语句,以便更好地查看机器的运行情况;例如,取消注释 prints:

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 log N) 方法可用时故意选择 O(N 平方) 方法,这太违背可扩展性了!-)

最后,对于那些更喜欢“单行代码”而不是清晰度和性能的人来说,还有一个带有适当混乱名称的额外单行版本:-)。

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]

解决方案 4:

您想要的在统计学中称为模式,Python 当然有一个内置函数可以为您完成这一点:

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

请注意,如果没有“最常见的元素”,例如前两个元素并列的情况,则在 Python <=3.7 中会引发此问题StatisticsError,而在 3.8 及更高版本中,它将返回遇到的第一个元素。

解决方案 5:

如果没有关于最低索引的要求,您可以使用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'

解决方案 6:

如果它们不可散列,您可以对它们进行排序,然后对结果进行一次循环,计算项目数(相同的项目将彼此相邻)。但使它们可散列并使用字典可能会更快。

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

解决方案 7:

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

(使用反转来确保返回最低索引项)

解决方案 8:

单行:

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

解决方案 9:

对列表副本进行排序并找出最长的运行。您可以在使用每个元素的索引对列表进行排序之前对其进行修饰,然后在出现平局的情况下选择以最低索引开始的运行。

解决方案 10:

我使用 scipy stat 模块和 lambda 来执行此操作:

import scipy.stats
lst = [1,2,3,4,5,6,7,5]
most_freq_val = lambda x: scipy.stats.mode(x)[0][0]
print(most_freq_val(lst))

结果:

 most_freq_val = 5

解决方案 11:

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

解决方案 12:

基于Luiz 的回答,但满足“在抽取的情况下,应返回索引最低的项目”条件:

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

解决方案 13:

简单的一行解决方案

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

它将返回出现频率最高的元素及其频率。

解决方案 14:

你可能不再需要这个了,但这是我为类似问题所做的。(由于有评论,它看起来比实际要长。)

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

解决方案 15:

ans  = [1, 1, 0, 0, 1, 1]
all_ans = {ans.count(ans[i]): ans[i] for i in range(len(ans))}
print(all_ans)
all_ans={4: 1, 2: 0}
max_key = max(all_ans.keys())

4

print(all_ans[max_key])

1

解决方案 16:

这里:

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

我隐约觉得标准库中某处有一种方法可以给出每个元素的数量,但我找不到它。

解决方案 17:

如果排序和散列都不可行,但==可以进行相等性比较(),则这显然是一个缓慢的解决方案(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))。

解决方案 18:

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

解决方案 19:

我需要在最近的程序中执行此操作。我承认,我无法理解 Alex 的答案,所以这就是我最终的结果。

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 \n        or (curCount==mpCount and i<mpIndex):
            mpEl=curEl
            mpIndex=i
            mpCount=curCount
    return mpEl, mpCount, mpIndex

我将其与 Alex 的解决方案进行了计时,对于短列表,它大约快 10-15%,但是一旦超过 100 个元素或更多(测试多达 200000 个),它就会慢 20% 左右。

解决方案 20:

#This will return the list sorted by frequency:

def orderByFrequency(list):

    listUniqueValues = np.unique(list)
    listQty = []
    listOrderedByFrequency = []
    
    for i in range(len(listUniqueValues)):
        listQty.append(list.count(listUniqueValues[i]))
    for i in range(len(listQty)):
        index_bigger = np.argmax(listQty)
        for j in range(listQty[index_bigger]):
            listOrderedByFrequency.append(listUniqueValues[index_bigger])
        listQty[index_bigger] = -1
    return listOrderedByFrequency

#And this will return a list with the most frequent values in a list:

def getMostFrequentValues(list):
    
    if (len(list) <= 1):
        return list
    
    list_most_frequent = []
    list_ordered_by_frequency = orderByFrequency(list)
    
    list_most_frequent.append(list_ordered_by_frequency[0])
    frequency = list_ordered_by_frequency.count(list_ordered_by_frequency[0])
    
    index = 0
    while(index < len(list_ordered_by_frequency)):
        index = index + frequency
        
        if(index < len(list_ordered_by_frequency)):
            testValue = list_ordered_by_frequency[index]
            testValueFrequency = list_ordered_by_frequency.count(testValue)
            
            if (testValueFrequency == frequency):
                list_most_frequent.append(testValue)
            else:
                break    
    
    return list_most_frequent

#tests:
print(getMostFrequentValues([]))
print(getMostFrequentValues([1]))
print(getMostFrequentValues([1,1]))
print(getMostFrequentValues([2,1]))
print(getMostFrequentValues([2,2,1]))
print(getMostFrequentValues([1,2,1,2]))
print(getMostFrequentValues([1,2,1,2,2]))
print(getMostFrequentValues([3,2,3,5,6,3,2,2]))
print(getMostFrequentValues([1,2,2,60,50,3,3,50,3,4,50,4,4,60,60]))

Results:
[]
[1]
[1]
[1, 2]
[2]
[1, 2]
[2]
[2, 3]
[3, 4, 50, 60]

解决方案 21:

def most_frequent(List):

    counter = 0

    num = List[0]

 

    for i in List:

        curr_frequency = List.count(i)

        if(curr_frequency> counter):

            counter = curr_frequency

            num = i


    return num


List = [2, 1, 2, 2, 1, 3]

print(most_frequent(List))

解决方案 22:

嗨,这是一个非常简单的解决方案,具有线性时间复杂度

L = ['鹅', '鸭子', '鸭子']

def most_common(L):

current_winner = 0
max_repeated = None
for i in L:
    amount_times = L.count(i)
    if amount_times > current_winner:
        current_winner = amount_times
        max_repeated = i

return max_repeated

打印(most_common(L))

“鸭子”

其中 number 是列表中重复次数最多的元素

解决方案 23:

numbers = [1, 3, 7, 4, 3, 0, 3, 6, 3]
max_repeat_num = max(numbers, key=numbers.count)     *# which number most* frequently
max_repeat = numbers.count(max_repeat_num)           *#how many times*
print(f" the number {max_repeat_num} is repeated{max_repeat} times")

解决方案 24:

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"

解决方案 25:

N/2最常见的元素应该是在数组中出现次数超过的元素,其中Nlen(array)。下面的技术将在O(n)时间复杂度内完成此操作,仅消耗O(1)辅助空间。

from collections import Counter

def majorityElement(arr):        
    majority_elem = Counter(arr)
    size = len(arr)
    for key, val in majority_elem.items():
        if val > size/2:
            return key
    return -1

解决方案 26:

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

解决方案 27:

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)
相关推荐
  政府信创国产化的10大政策解读一、信创国产化的背景与意义信创国产化,即信息技术应用创新国产化,是当前中国信息技术领域的一个重要发展方向。其核心在于通过自主研发和创新,实现信息技术应用的自主可控,减少对外部技术的依赖,并规避潜在的技术制裁和风险。随着全球信息技术竞争的加剧,以及某些国家对中国在科技领域的打压,信创国产化显...
工程项目管理   1579  
  为什么项目管理通常仍然耗时且低效?您是否还在反复更新电子表格、淹没在便利贴中并参加每周更新会议?这确实是耗费时间和精力。借助软件工具的帮助,您可以一目了然地全面了解您的项目。如今,国内外有足够多优秀的项目管理软件可以帮助您掌控每个项目。什么是项目管理软件?项目管理软件是广泛行业用于项目规划、资源分配和调度的软件。它使项...
项目管理软件   1355  
  信创产品在政府采购中的占比分析随着信息技术的飞速发展以及国家对信息安全重视程度的不断提高,信创产业应运而生并迅速崛起。信创,即信息技术应用创新,旨在实现信息技术领域的自主可控,减少对国外技术的依赖,保障国家信息安全。政府采购作为推动信创产业发展的重要力量,其对信创产品的采购占比情况备受关注。这不仅关系到信创产业的发展前...
信创和国产化的区别   8  
  信创,即信息技术应用创新产业,旨在实现信息技术领域的自主可控,摆脱对国外技术的依赖。近年来,国货国用信创发展势头迅猛,在诸多领域取得了显著成果。这一发展趋势对科技创新产生了深远的推动作用,不仅提升了我国在信息技术领域的自主创新能力,还为经济社会的数字化转型提供了坚实支撑。信创推动核心技术突破信创产业的发展促使企业和科研...
信创工作   9  
  信创技术,即信息技术应用创新产业,旨在实现信息技术领域的自主可控与安全可靠。近年来,信创技术发展迅猛,对中小企业产生了深远的影响,带来了诸多不可忽视的价值。在数字化转型的浪潮中,中小企业面临着激烈的市场竞争和复杂多变的环境,信创技术的出现为它们提供了新的发展机遇和支撑。信创技术对中小企业的影响技术架构变革信创技术促使中...
信创国产化   8  
热门文章
项目管理软件有哪些?
云禅道AD
禅道项目管理软件

云端的项目管理软件

尊享禅道项目软件收费版功能

无需维护,随时随地协同办公

内置subversion和git源码管理

每天备份,随时转为私有部署

免费试用