python - heapq.heapify 不适用于子类列表

Question

每次 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 是一个内置函数有关，但我还是不明白。

为什么 heapq.heapify 没有调用覆盖的 __setitem__？

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

Python 2.7 如果重要的话

Answer 1

作为 Python 3.0 项目的一部分，以及 3.3，他们仔细阅读了文档，使得当某些东西采用 list 与一般的 sequence type 时更明确或可变序列类型或可迭代，以及heapq在 3.3 中肯定是说 list，这意味着在 2.7 中也是如此。

如果您跟踪代码，如果您有 C 实现，在 _heapqmodule.c , heapify 显式调用 PyList_Check 来验证该类型是一个真正的 list 而不是类似 list 的序列。这不会捕获 list 的子类，但您可以看到它直接调用 PyList_GETSIZE 和(在 _siftup 内)PyList_GET_ITEM 和 PyList_SET_ITEM，因此它将 list 子类视为基础 list 对象。 (这在当前主干中没有改变。)

因此，有几种解决方法。

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

但是，这可能会慢很多。

从 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 位赢:3.997 秒

• PyPy 2.7.21.9.0 32 位赢:2.334 秒

因此，尽管实际上调用了我的 Python 列表重写，但 PyPy 把其他一切都搞砸了。 (我没有测试 Jython 或 IronPython——部分原因是 JVM 或 .NET 的启动和预热时间太长，你需要更长的测试才能公平......但它们也必须使用纯 Python heapq 模块。)

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