为什么我在 Python 中的堆实现比 heapq 标准库慢得多？

Question

我自己实现最小堆，这是我的插入函数：

    def insert(self, new_elem):
        self.elems.append(new_elem)
        cur_pos = len(self.elems) - 1

        while cur_pos > 0:
            par_pos = (cur_pos - 1) // 2
            if self.elems[cur_pos] >= self.elems[par_pos]:
                break
            else:
                self.swap_node(cur_pos, par_pos)
            cur_pos = par_pos

我尝试插入这样的列表：

    for i in range(int(3e5), -1, -1):
        min_heap.insert(i)

这些操作在我的堆实现中需要 0.73 秒，而使用 heapq 库只需要 0.05 秒。我注意到 heapq not 在 C 中实现。那么为什么会有这么大的不同呢？

Answer 1

我注意到 heapq 没有在 C 中实现

呃…好吧…如果你向下滚动到

heapq.py

的底部：

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