3

我希望每次heapq.heapify函数更改堆列表中的元素时都收到回调通知（顺便说一句，需要跟踪列表中的对象以及它们的索引如何更改）。

我的计划是继承list并覆盖__setitem__我将跟踪列表中更改的方法。所以这是子类： 

class List2(list):

    def __setitem__(self, key, value):
        print 'setitem: key=',key,' value=',value
        list.__setitem__(self, key, value)

    def __getitem__(self, key):
        print 'getitem: key=',key
        return list.__getitem__(self, key)

然后我创建一个实例List2并为它调用 heapify：

h = List2([12, -3, 0, 5, 1, 7])
heapq.heapify(h)

问题是覆盖__setitem__的不是从内部调用的heapq.heapify。看起来heapq.heapify将 List2 的实例视为默认列表。我想这与heapq.heapify内置函数的事实有关，但我仍然不明白。

为什么__setitem__不调用被覆盖的对象heapq.heapify？

这里有趣的是，如果我将 heapq 的代码复制粘贴到我的本地模块中（因此它不再是内置函数），那么它会按预期工作并且我会调用List2.__settiem__，但它不适用于默认 (内置）heapq。

Python 2.7 如果重要的话

4

3 回答 3

4

作为 Python 3.0 项目的一部分，同样对于 3.3，他们通过文档更明确地说明了当某事采用 alist与一般sequence typeor mutable sequence typeoriterable时，并且在 3.3 中heapq明确表示list，这意味着在 2.7 中也是如此。

如果您跟踪代码，如果您有 C 实现， in_heapqmodule.c显heapify式调用PyList_Check以验证该类型是真实的list而不是类似list的序列。这不会捕获 的子类list，但您可以看到它直接调用PyList_GETSIZEand （在 内_siftup） PyList_GET_ITEMand PyList_SET_ITEM，因此它将list子类视为基础list对象。（从当前的主干开始，这并没有改变。）

所以，有几种方法可以解决这个问题。

首先，正如@FogleBird 建议的那样，您可以只 fork 的纯 Python 实现——heapq只需将完全相同的东西复制到您的项目中，给它一个不同的名称，然后删除第from _heapq import *318-321 行的位。

但是，这可能会慢很多。

从 CPython 切换到PyPy可能会自动解决这个问题（这也意味着无论您是否愿意，您都将获得纯 Python 实现）。

事实上，我对包含 1,000,000 个项目的列表进行了快速测试。在验证 PyPy 确实使用List2该类之后，我对其进行了修改，而不是打印，而是将字符串存储到全局变量中。（否则，在 Mac 上打印的时间是实际工作的 3 倍，在 Windows 上是 40 倍……）然后我用各种不同的 Python 运行它：

  • CPython 2.7.2 64 位 Mac：2.079s
  • CPython 3.3.0 64 位 Mac：1.997s
  • CPython 3.3.0 32 位 Mac：2.197s

  • PyPy 2.7.2/1.9.0 64 位 Mac：1.619s

  • CPython 2.7.3 32 位 Win：3.997s

  • PyPy 2.7.21.9.0 32 位 Win：2.334s

因此，尽管实际上调用了我的 Python 列表覆盖，PyPy 还是把其他所有东西都吹走了。（我没有测试 Jython 或 IronPython——部分原因是 JVM 或 .NET 的启动和预热时间太长，以至于您需要更长的测试才能完全公平……但它们也必须使用纯 Pythonheapq模块.)

但这可能是一个比你想要的更剧烈的变化。另一种选择也是分叉_heapqmodule.c。即使您根本不了解 C API，这实际上也只是一个搜索和替换的工作。对于每个PyList_FOO函数，将其替换为相应的PySequence_Foo函数（PyList_SIZE-> PySequence_Size、PyList_GETITEM->PySequence->GetItem等）。并在它出现的两个地方替换模块名称。就是这样。然后构建模块，并让你的 forkmyheapq.py尝试import _myheapq代替import _heapq. 这仍然不会像内置实现那么快，但这只是因为它会多次调用你的__getitem__and__setitem__方法，这正是你想要的。

于 2012-12-18T02:21:51.133 回答
3

heapq_heapq如果可用，则使用 C 实现。

当您将heapq模块复制到本地包时，_heapq找不到，并且Python implementationget 使用了，它确实使用了__setitem__并且__getitem__您可以找到类似heap[pos] = heap[childpos]in 的语句_siftup。

于 2012-12-18T00:47:45.390 回答
1

heapq 使用本机代码（如果您的平台上可用），我认为这是问题所在，尽管我不完全理解原因。

也许您可以采用不同的方法，并跟踪列表项的原始索引。

>>> n = [12, -3, 0, 5, 1, 7]
>>> m = [(v, i) for i, v in enumerate(x)]
>>> heapq.heapify(m)
>>> m
[(-3, 1), (1, 4), (0, 2), (5, 3), (12, 0), (7, 5)]

然后你可以在 heapify 之后提取值和索引......

>>> values, indicies = zip(*m)
>>> values
(-3, 1, 0, 5, 12, 7)
>>> indicies
(1, 4, 2, 3, 0, 5)

编辑：我试图通过提供一个不是从列表派生的类的实例来“欺骗”heapq。它不起作用，它需要列表，大概是因为本机代码出于性能原因将其用作假设。

>>> class List(object):
...     def __init__(self, data):
...         self.data = data
...     def __getitem__(self, key):
...         print 'getitem', key
...         return self.data[key]
...     def __setitem__(self, key, value):
...         print 'setitem', key, value
...         self.data[key] = value
... 
>>> x = List([12, -3, 0, 5, 1, 7])
>>> heapq.heapify(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: heap argument must be a list

编辑 2：注意 heapq.py 中的这段代码。这会覆盖 Python 实现。

# If available, use C implementation
try:
    from _heapq import *
except ImportError:
    pass

编辑 3：Python 文档讨论了您的根本问题。即“如果一个待处理的任务需要被删除，你如何找到它并从队列中移除它？”

http://docs.python.org/2/library/heapq.html#priority-queue-implementation-notes

这个想法是简单地将条目标记为已删除。当您在优先级队列的顶部看到这些项目时，您会忽略它们。该文档有示例代码。

于 2012-12-18T00:44:37.697 回答