输入是未排序的元组列表:
x = [('herr', 1),
('dapao', 1),
('cino', 1),
('o', 38),
('tiao', 2),
('tut', 1),
('poh', 6),
('micheal', 1),
('orh', 1),
('horlick', 3),
('si', 1),
('tai', 1),
('titlo', 1),
('siew', 17),
('da', 1),
('halia', 2)]
目标是找到计数最少的最后一个
n
键,即所需的输出:['orh', 'si', 'tai', 'titlo', 'da']
我试过这样做:
[-n:]
Counter.most_common()
列表[-n:]
转换为字典 IE。
n = 5
list(dict(Counter(dict(x)).most_common()[-n:]).keys())
有没有更简单的方法来获得相同的输出?
我也可以这样做:
from operator import itemgetter
output, *_ = zip(*sorted(x, key=itemgetter(1))[n:])
list(output)
但现在我只是用
Counter.most_common
和 sorted
换掉了 itemgetter
。然后我仍然需要 zip(*list)
通过从压缩后的每个元组列表中解压缩第一个值来提取键。一定有更简单的方法。
笔记
请注意,问题不是要求排序,而是提取给定的原始元组列表中的列表第一个元素。提取的标准基于第二个元素中具有最低值的最后 n 个项目。
answers from the possible duplicate linked 仍然需要解包已排序元组列表并提取第一个元素列表的前 n 个的步骤。
最佳答案
鉴于此目标的定义,您的两个解决方案都不适合。在使用 Counter
的一个中,您使用 dict
这将使键的顺序未定义,并且您不会获得最后一个键,而是一些具有最小值的 n
键。第二个解决方案有不正确的切片,如果它被修复,它返回第一个具有最小值的 n
键。
考虑到 sorted
实现是 stable 可以像这样重写以适应目标:
def author_2():
output, *_ = zip(*sorted(reversed(l), key=lambda v: v[1])[:n])
return list(reversed(output))
但是使用
heapq
是一个更好的主意,它是诸如“来自可迭代的 n 个最小/最大值”之类的问题的 stdlib 工具(正如 Martijn Pieters 指出的那样,nlargest
和 nsmallest
也是稳定的,文档确实这么说,但隐含办法)。特别是如果您必须处理的实际列表很大(对于小的 n
, sorted
应该比 docs describe 更快)。def prop_1():
rev_result = heapq.nsmallest(n, reversed(l), key=lambda v: v[1])
return [item[0] for item in rev_result][::-1]
您可以进一步提高性能,但以牺牲顺序(排序稳定性)为代价,即一些具有最小值的
n
键而不是具有最小值的最后 n
键。为此,您需要保留一个“堆化”列表并将其用作内部数据结构而不是普通的 list
(如果您不更改列表并且只需要底部 n 一次,则不会带来性能优势) .您可以从列表中推送和弹出,例如:_p2_heap = None
def prop_2():
global _p2_heap
if not _p2_heap:
_p2_heap = []
for item in l:
heapq.heappush(_p2_heap, item[::-1])
return [item[1] for item in heapq.nsmallest(n, _p2_heap)]
这是您可以用来对解决方案进行基准测试的完整模块。
import heapq
from collections import Counter
l = [
('herr', 1), ('dapao', 1),
('cino', 1), ('o', 38),
('tiao', 2), ('tut', 1),
('poh', 6), ('micheal', 1),
('orh', 1), ('horlick', 3),
('si', 1), ('tai', 1),
('titlo', 1), ('siew', 17),
('da', 1), ('halia', 2)
]
n = 5
def author_1():
return list(dict(Counter(dict(l)).most_common()[-n:]).keys())
def author_2():
output, *_ = zip(*sorted(reversed(l), key=lambda v: v[1])[:n])
return list(reversed(output))
def prop_1():
rev_result = heapq.nsmallest(n, reversed(l), key=lambda v: v[1])
return [item[0] for item in rev_result][::-1]
_p2_heap = None
def prop_2():
global _p2_heap
if not _p2_heap:
_p2_heap = []
for item in l:
heapq.heappush(_p2_heap, item[::-1])
return [item[1] for item in heapq.nsmallest(n, _p2_heap)][::-1]
这是
timeit
结果:$ python -m timeit -s "import tst" "tst.author_1()"
100000 loops, best of 3: 7.72 usec per loop
$ python -m timeit -s "import tst" "tst.author_2()"
100000 loops, best of 3: 3.7 usec per loop
$ python -m timeit -s "import tst" "tst.prop_1()"
100000 loops, best of 3: 5.51 usec per loop
$ python -m timeit -s "import tst" "tst.prop_2()"
100000 loops, best of 3: 3.96 usec per loop
但是如果我们制作
l = l * 1000
,差异就会变得明显:$ python -m timeit -s "import tst" "tst.author_1()"
1000 loops, best of 3: 263 usec per loop
$ python -m timeit -s "import tst" "tst.author_2()"
100 loops, best of 3: 2.72 msec per loop
$ python -m timeit -s "import tst" "tst.prop_1()"
1000 loops, best of 3: 1.65 msec per loop
$ python -m timeit -s "import tst" "tst.prop_2()"
1000 loops, best of 3: 767 usec per loop
关于python - 从键值对的元组列表中获取计数最少的项目的键 - Python,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/48745169/