查找Python列表中最常见元素的有效方法是什么?
我的列表项可能不具有哈希值,因此无法使用字典.
同样在绘制的情况下,应返回具有最低索引的项目.例:
>>> most_common(['duck', 'duck', 'goose'])'duck'>>> most_common(['goose', 'duck', 'duck', 'goose'])'goose'
解决方法:
有了这么多解决方案,我很惊讶没有人提出我认为是明显的解决方案(对于不可拆解但可比较的元素) – [itertools.groupby] [1]. itertools提供快速,可重用的功能,并允许您将一些棘手的逻辑委托给经过充分测试的标准库组件.考虑例如:
import itertoolsimport operatordef 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 most_common(['goose', 'duck', 'duck', 'goose'])
发出:
SL: [('duck', 1), ('duck', 2), ('goose', 0), ('goose', 3)]item 'duck', count 2, minind 1item 'goose', count 2, minind 0goose
如您所见,SL是一对配对列表,每一对都是一个项目,后跟原始列表中的项目索引(以实现关键条件,即如果具有相同最高计数的“最常见”项目> 1,则结果必须是最早发生的结果.
groupby仅按项目分组(通过operator.itemgetter).辅助函数,在最大计算期间每个分组调用一次,接收并在内部解包一个组 – 一个包含两个项目的元组(item,iterable),其中iterable的项目也是两项元组,(item,original index)[[the SL的项目]].
然后辅助函数使用循环来确定组的可迭代条目数和最小原始索引;它返回那些组合的“质量密钥”,最小索引符号已更改,因此最大操作将考虑“更好”那些在原始列表中较早发生的项目.
如果它对时间和空间上的大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平方)方法对于可扩展性的粒度而言太过分了! – )
最后,对于那些喜欢“oneliners”以获得清晰度和性能的人来说,奖励的1-liner版本具有适当的错误名称:-).
from itertools import groupby as gdef most_common_oneliner(L): return max(g(sorted(L)), key=lambda(x, v):(len(list(v)),-L.index(x)))[0]
来源:https://www.icode9.com/content-1-452551.html
联系客服