gpt4 book ai didi

python - 使用 heapq 降序

转载 作者:太空狗 更新时间:2023-10-30 00:09:22 24 4
gpt4 key购买 nike

我正在使用 Python 的 heapq 模块按升序和降序获取数据。

对于升序,我使用的是最小堆,它运行良好,如下所示:

>>> from heapq import heapify, heappop
>>> heap = [9, 3, 1, 5, 6, 2, 7]
>>> heapify(heap)
>>> heappop(heap)
1
>>> heappop(heap)
2
>>> heappop(heap)
3

对于降序,我尝试了以下不同的方法,但它们都有一些缺点:

  1. 使用负值作为优先级进行反向排序。我必须使用单独的列表来使数据可重用。如果原始列表很大,则复制列表的成本很高。

    >>> from heapq import heapify, heappop
    >>> heap = [9, 3, 1, 5, 6, 2, 7]
    >>> heap_neg = [-x for x in heap]
    >>> heapify(heap_neg)
    >>> -heappop(heap_neg)
    9
    >>> -heappop(heap_neg)
    7
    >>> -heappop(heap_neg)
    6
  2. 优先使用负值元组,这也是浪费空间。我不想将整数列表存储为元组列表。

    >>> from heapq import heapify, heappop
    >>> heap = [(-9, 9), (-3, 3), (-1, 1), (-5, 5), (-6, 6), (-2,2), (-7,7)]
    >>> heapify(heap)
    >>> heappop(heap)[1]
    9
    >>> heappop(heap)[1]
    7
    >>> heappop(heap)[1]
    6
  3. 在 heapify 中缺少使用键排序。像这样的东西:

    >>> from heapq import heapify, heappop
    >>> heap = [9, 3, 1, 5, 6, 2, 7]
    >>> heapify(heap, key=lambda x:-x) # This doesn't work as heapify don't have key parameter
  4. 如果我使用 heapq._heapify_max(heap),我将必须在每个元素弹出后进行 _heapify_max。喜欢:

    >>> from heapq import _heapify_max, heappop
    >>> heap = [9, 3, 1, 5, 6, 2, 7]
    >>> _heapify_max(heap)
    >>> heappop(heap)
    9
    >>> heappop(heap) # popping without _heapify_max gives wrong result
    1
    >>> _heapify_max(heap)
    >>> heappop(heap) # popping after _heapify_max gives correct result
    7

有什么方法可以获得与升序订单类似的降序订单吗? :)

最佳答案

正如我们在评论中所讨论的那样,当您从空堆开始并在进行中添加值时,您对使用负值将最小堆翻转为最大堆时复制数据的担忧无关紧要.由于这是查找值流的运行中位数的用例,因此在添加值时取反值应该可以正常工作。

这是我编写的运行中值生成器,只是为了仔细检查它是否按我预期的方式工作:

def running_median(iterable):
left_q = [] # heap of smaller-than-median elements, stored negated
right_q = [] # heap of larger-than-median elements

for value in iterable:
if len(left_q) == len(right_q): # push to left_q when they're equal size
if len(right_q) > 0 and value > right_q[0]:
value = heapq.heapreplace(right_q, value)
heapq.heappush(left_q, -value)
else: # push to right_q only when it's (strictly) smaller
if value < -left_q[0]:
value = -heapq.heapreplace(left_q, -value)
heapq.heappush(right_q, value)

# len(left_q) is always >= len(right_q) so we never yield right_q[0]
if len(left_q) > len(right_q):
yield -left_q[0]
else:
yield (-left_q[0] + right_q[0]) / 2

left_q 堆存储小于或等于中值的值。每个值在被压入时都会被取反,因此对它使用正常的最小堆操作可以使它像最大堆一样工作。我们只需要记住重新否定我们从中取出的任何值,回到原来的符号。

关于python - 使用 heapq 降序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44792566/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com