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

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

我试过这样做:
  • 首先将元组列表转换为字典
  • 将 dict 转换为 Counter
  • 然后从 [-n:]
  • 中找到元组的 Counter.most_common() 列表
  • 将元组列表从 [-n:] 转换为字典
  • 获取 key ,然后将其转换为列表

  • 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_commonsorted 换掉了 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 指出的那样,nlargestnsmallest 也是稳定的,文档确实这么说,但隐含办法)。特别是如果您必须处理的实际列表很大(对于小的 nsorted 应该比 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/

    10-11 19:42
    查看更多