python - 从键值对元组列表中获取计数最少的项的键 - Python

Question

输入是一个未排序的元组列表:

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

我试过这样做:

• 首先将元组列表转换为字典
• 将字典放入计数器
• 然后从 Counter.most_common()
中找到 [-n:] 元组列表
• 将 [-n:] 中的元组列表转换为字典
• 获取key，然后将其转化为list

即

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 个。

Answer 1

The goal is to find the last n keys with the least counts

鉴于此目标的定义，您的两个解决方案都不合适。在使用 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 as 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 值最小的键.为此，您需要保留一个“heapified”列表并将其用作您的内部数据结构，而不是普通的 list (如果您不更改列表并且只需要 bottom-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