0

我想从时间序列中梳理出 n 个最大的极端。heapq 非常适合 nlargest

def nlargest(series, n):
    count = 0
    heap = []
    for e in series:
        if count < n:
            count+=1
            hp.heappush(heap, e)
        else:
            # keeps heap size fixed 
            hp.heappushpop(heap,e)  
    ''' note: heap[0] is smallest '''
    return heap

但是最小的 n 个呢？请注意，我想要原始系列的一个子集，因此 heapify 和反转顺序将不起作用。我想要的本质上是将比较运算符从 gt 重载到 lt。对python中的重载不太熟悉。

一个不太吸引人的选项（假设数值）是在插入之前否定项目，然后否定整个返回堆（返回列表或重新堆否定列表）但这似乎很笨拙，它不再适用于非数字确实有gt和lt。任何优雅的解决方案？

4

2 回答 2

3

您可以通过将项目的优先级乘以 -1 轻松“创建”一个倒置堆。

因此，您nsmallest只需要被告知如何“反转”优先级，根据需要装饰每个值：

def nsmallest(series, n, invert=lambda x: -1 * x):
    count = 0
    heap = []
    for e in series:
        if count < n:
            count += 1
            hp.heappush(heap, (invert(e), e))
        else:
            # keeps heap size fixed
            hp.heappushpop(heap, (invert(e), e))  
    # note: heap[0][1] is largest, remove inverted priorities
    return [h[1] for h in heap]

请注意，我们使用(invertedpriority, value)元组来保持堆倒置。

对于非数字，您必须简单地提供一个颠倒优先级的反转函数，它只需要一个简单的键，而不是可读的东西或任何东西：

alphanumeric_invert = lambda x: [(ord(c) * -1) for c in x]

但是，与其自己编写，不如使用heapq.nsmallest()函数，它使用优化的最大堆实现（_heappop_max()它使用了一个内部函数），它还添加了一个 tie-breaker 计数值以保持排序稳定。并且有匹配heapq.nlargest()功能。

于 2012-09-10T17:24:03.833 回答
0

heapq.nsmallest从 Python 标准库中使用：

heapq.nsmallest(n, iterable[, key])

从定义的数据集中返回一个包含n最小元素的列表iterable。相当于：sorted(iterable, key=key)[:n]

于 2013-02-27T16:42:11.690 回答