拦截heapq

Question

我想使用Python的heapq模块.但是,我需要跟踪每个值设置的索引.

所以我写了

class heap(list):       
    def __init__(self,xs):
        super(heap,self).__init__(xs)
        self._index_table = {x:i for i,x in enumerate(self)}

    def __setitem__(self,i,v):
        print(i,v)
        super(heap,self).__setitem__(i,v)
        self._index_table[v] = i

    def append(self,x):
        super(heap,self).append(x)
        self._index_table[x] = len(self)-1

from heapq import heapify, heappush, heappop, _siftdown, _siftup

h = heap([4,3,2,1])
heapify(h)
heappush(h,12)
print(h)
print(h._index_table)

这打印

[1, 3, 2, 4, 12]
{1: 3, 2: 2, 3: 1, 4: 0}

heapify并heappush修改了我的列表中的条目,绕过了我捕获所有作业的尝试.

为什么会这样？有没有解决的办法？还有一种方法可以使用heapq模块并仍然跟踪每个值对应的索引吗？

编辑:

看起来我的代码有一条heapify(h)我在原帖中没有的行.修正了这一点

Answer 1

在阅读heapq源代码时,我注意到@ math4tots确实是在导入C实现.所以我运行以下代码来证明它是否正在使用python源(它会调用其中的方法list是可重载的),或者它使用的是使用编译方法的C实现:

>>> class heap(list):        
...     def __init__(self,xs):
...         super(heap,self).__init__(xs)
...         self._index_table = {x:i for i,x in enumerate(self)}
...     
...     def __setitem__(self,i,v):
...         print("SETITEM")
...         print(i,v)
...         super(heap,self).__setitem__(i,v)
...         self._index_table[v] = i
...     
...     def append(self,x):
...         print("APPEND")
...         super(heap,self).append(x)
...         self._index_table[x] = len(self)-1
... 
>>> 
>>> 
>>> h = heap([4,3,2,1])
>>> heapify(h)
>>> h
[1, 3, 2, 4]
>>> h._index_table
{1: 3, 2: 2, 3: 1, 4: 0}
>>> heappush(h,42)
>>> h
[1, 3, 2, 4, 42]
>>> h._index_table
{1: 3, 2: 2, 3: 1, 4: 0}

它不打印单个字符串...这意味着它不使用我们正在查看的python源,但绝对是编译版本.

所以你的代码不太可能正常工作......

阅读C源代码heapq module证明我们正确:该_siftup函数PyList_SET_ITEM()用于从列表中获取值,覆盖任何重载方法的尝试.

尽管如此,所有希望都没有丢失,进一步阅读C源代码,让我发现实际上C模块不会导出_sitf*实现heapq算法的函数.所以我看了下面的内容,作为一个双重检查:

>>> heapq.heapify
<built-in function heapify>
>>> heapq._siftup
<function _siftup at 0x10b36ab00>

这证明我是对的!

所以,你总是可以重新实现heapify()和heappush()使用功能,这是约上几个长的线,_siftup()并_siftdown()从heapq模块不是由C代码阴影的功能.

所以这里将重新实现它:

import heapq

class HeapQueue(list):
    def __init__(self,xs):
        super(HeapQueue,self).__init__(xs)
        self._index_table = {x:i for i,x in enumerate(self)}
    def __setitem__(self,i,v):
        super(HeapQueue,self).__setitem__(i,v)
        self._index_table[v] = i
    def append(self,x):
        super(HeapQueue,self).append(x)
        self._index_table[x] = len(self)-1
    def push(self, x):
        self.append(x)
        heapq._siftdown(self, 0, len(self)-1)
    def heapify(self):
        n = len(self)
        for i in reversed(range(n//2)):
            heapq._siftup(self, i)

结果:

>>> h = HeapQueue([4,3,2,1])
>>> print(h._index_table)
{1: 3, 2: 2, 3: 1, 4: 0}
>>> h.heapify()
>>> print(h)
[1, 3, 2, 4]
>>> print(h._index_table)
{1: 0, 2: 2, 3: 1, 4: 3}
>>> h.push(42)
>>> print(h._index_table)
{1: 0, 2: 2, 3: 1, 4: 3, 42: 4}
>>> print(h)
[1, 3, 2, 4, 42]
>>> 

我的猜测是你不想保留那个heapify()方法,而是将它作为构造函数的一部分,并为你自己的Heap Queue类思考一个更好的接口.我只把它作为这个想法的概念证明.

HTH