+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

暂无数据

在列表中找到最常见的元素

发布于2020-09-24 11:59     阅读(1039)     评论(0)     点赞(6)     收藏(3)


0

1

2

3

4

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

我的列表项可能无法散列,因此不能使用字典。同样在绘制的情况下,应返回索引最低的项目。例:

>>> 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操作将考虑“更好”那些在原始列表中较早出现的项目。

此代码可能是更简单的,如果它担心一点点时间和空间,少谈大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]

相同的基本思想,只是表达得更简单,紧凑...但是,las,额外的O(N)辅助空间(将组的可迭代对象体现到列表中)和O(N平方)时间(获取L.index每个项目的总和) 。尽管过早的优化是编程中所有弊端的根源,但在有O(N log N)个可用的情况下,故意选择O(N平方)的方法与可扩展性背道而驰!

最后,对于那些更喜欢“单线”而不是清晰度和性能的人,可以使用名称经过适当修饰的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]

0

1

2

3

4

5

6

7

8

9



所属网站分类: 技术文章 > 问答

作者:黑洞官方问答小能手

链接: https://www.pythonheidong.com/blog/article/542441/c6cbe292cc44952a727a/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

6 0
收藏该文
已收藏

评论内容:(最多支持255个字符)