heapq.nlargest返回结果在原序列中的索引

Question

如何返回可迭代对象中第n大的元素在原始列表中的索引

heapq.nlargest(2, [100, 2, 400, 500, 400])

output = [(3,500), (2, 400)]

这已经花费了我几个小时的时间，我无法弄清楚。

- Joey

Answer 1

>>> seq = [100, 2, 400, 500, 400]
>>> heapq.nlargest(2, enumerate(seq), key=lambda x: x[1])
[(3, 500), (2, 400)]

- SilentGhost

Answer 2

您可以使用list.index与map相结合，这在小的n时非常快（注意：list.index返回值是第一个值为x的项目的索引）：

>>> iterable = [100, 2, 400, 500, 400]
>>> map(iterable.index, heapq.nlargest(2, iterable))
[3, 2]

要查看相关的值，您可以使用以下命令：

>>> map(lambda n: (n, iterable.index(n)), heapq.nlargest(2, iterable))
[(500, 3), (400, 2)]

对于更大的n，请参考@SilentGhost的帖子。

---

编辑：对一些解决方案进行了基准测试：

#!/usr/bin/env python
import heapq
from timeit import Timer

seq = [100, 2, 400, 500, 400]

def a(seq):
    """returns [(3, 500), (2, 400)]"""
    return heapq.nlargest(2, enumerate(seq), key=lambda x: x[1])

def b(seq):
    """returns [3, 2]"""
    return map(seq.index, heapq.nlargest(2, seq))

def c(seq):
    """returns [(500, 3), (400, 2)]"""
    map(lambda n: (n, seq.index(n)), heapq.nlargest(2, seq))

if __name__ == '__main__':
    _a = Timer("a(seq)", "from __main__ import a, seq")
    _b = Timer("b(seq)", "from __main__ import b, seq")
    _c = Timer("c(seq)", "from __main__ import c, seq") 

    loops = 1000000

    print _a.timeit(number=loops)
    print _b.timeit(number=loops)
    print _c.timeit(number=loops)

    # Core i5, 2.4GHz, Python 2.6, Darwin
    # 8.92712688446
    # 5.64332985878
    # 6.50824809074

- miku

---

@SilentGhost，请解释一下。至少在一个简单的基准测试中，iterable.index 似乎快了近两倍（请参见我的编辑）。 - miku

@Roque：如果你将有效的解决方案（我的）与无效的解决方案（你的）进行比较，那么你的基准测试有什么价值呢？尽管你链接到了“index”文档，但你可能没有注意到其中非常重要的一点：“返回列表中第一个项目的索引[...]”。 - SilentGhost

@Roque：嗯，当 n=2 时你看到了什么，那么当 n=10 时你的“解决方案”表现如何呢？ - SilentGhost

当数组长度为10000时，n = 10 和 n = 100 的性能结果相同。但是当 n = 100 时，你赢了，恭喜 ;) - miku