为什么我的 Python 脚本在我的 HeapSort 实现上运行得比它应该慢？

Question

我得到了在 Python 或 Java（或任何其他语言）中实现堆排序算法的任务。因为我在 Python 或 Java 方面并不是那么“流利”，所以我决定两者都做。

但在这里我遇到了一个问题，程序的运行时间比它“应该”的要高得多。我的意思是，堆排序应该运行到 O(n * log n) 并且对于在几个 GHz 的时钟频率上运行的当前处理器我没想到该算法会运行超过 2000 秒的数组大小为 320k

因此，对于我所做的，我从 Python 和 Java 中的此类伪代码实现了算法（我还尝试了 Rosetta Code 中的 Julia 中的代码，以查看运行时间是否相似，为什么是 Julia？随机选择）

所以我检查了小输入大小问题的输出，例如大小为 10、20 和 30 的数组。它似乎在两种语言/实现中正确排序的数组。

然后我使用实现相同算法的 heapq 库再次检查运行时间是否相似。当实际情况确实如此时，它让我感到惊讶……但经过几次尝试后，我尝试了最后一件事，即更新 Python，然后，使用 heapq 的程序比以前的程序运行得快得多。实际上，320k 阵列大约需要 2k 秒，现在大约为 1.5 秒左右。

我重试了我的算法，问题仍然存在。

所以这里是我实现的 Heapsort 类：

class MaxHeap:

    heap = []

    def __init__(self, data=None):

        if data is not None:

            self.buildMaxHeap(data)

    @classmethod

    def toString(cls):

        return str(cls.heap)

    @classmethod

    def add(cls, elem):

        cls.heap.insert(len(cls.heap), elem)

        cls.buildMaxHeap(cls.heap)

    @classmethod

    def remove(cls, elem):

        try:

            cls.heap.pop(cls.heap.index(elem))

        except ValueError:

            print("The value you tried to remove is not in the heap")

    @classmethod

    def maxHeapify(cls, heap, i):

        left = 2 * i + 1

        right = 2 * i + 2

        largest = i

        n = len(heap)

        if left < n and heap[left] > heap[largest]:

            largest = left

        if right < n and heap[right] > heap[largest]:

            largest = right

        if largest != i:

            heap[i], heap[largest] = heap[largest], heap[i]

            cls.maxHeapify(heap, largest)

    @classmethod

    def buildMaxHeap(cls, heap):

        for i in range(len(heap) // 2, -1, -1):

            cls.maxHeapify(heap, i)

        cls.heap = heap

    @staticmethod

    def heapSort(table):

        heap = MaxHeap(table)

        output = []

如果您需要其余的代码来查看错误可能在哪里，请不要犹豫，我会提供它。只是不想无缘无故地共享整个文件。

如前所述，我预期的运行时间来自最坏情况下的运行时间：O(n * log n) 使用现代架构和 2.6GHz 的处理器我希望大约 1 秒或更短的时间（因为运行时间以纳秒为单位询问）我想即使是 1 秒也太长了）

Answer 1

有趣的是，您发布了计算机的时钟速度 - 您可以计算算法所需的实际步骤数……但是您需要对实现有很多了解。例如，在 python 中，每次创建对象或超出范围时，解释器都会更新底层对象上的计数器，如果这些 ref 计数达到 0，则释放内存。相反，您应该查看相对速度。您发布的第三方示例显示，当输入数组长度加倍时，速度小于加倍。好像不太对吧？事实证明，对于这些示例，构建数组的初始工作可能支配了对数组进行排序所花费的时间！在您的代码中，已经有一条注释指出了我要说的内容...heap.remove(heap.heap[i])&nbsp;此操作将遍历您的列表（从索引 0 开始）寻找匹配的值，然后将其删除。这已经很糟糕了（如果它按预期工作，如果您的代码按预期工作，您将在该行上进行 320k 比较！）。但情况更糟——从数组中删除一个对象不是就地修改——删除对象后的每个对象都必须在列表中向前移动。最后，不能保证您确实删除了那里的最后一个对象……可能存在重复值！这是一个有用的网站，列出了 python 中各种操作的复杂性 -&nbsp;https://wiki.python.org/moin/TimeComplexity。为了尽可能高效地实现算法，您需要尽可能多的数据结构操作为 O(1)。这是一个例子......这是一些原始代码，大概是heap.heap是一个列表......&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output&nbsp;=&nbsp;[heap.heap[i]]&nbsp;+&nbsp;output &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;heap.remove(heap.heap[i])正在做&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output.append(heap.heap.pop())将避免分配新列表并使用恒定时间操作来改变旧列表。（向后使用输出比使用 O(n) 时间 insert(0) 方法要好得多！如果您确实需要订单，您可以使用出队对象进行输出以获得 appendleft 方法）如果您发布了整个代码，那么我们可能会提供很多其他的小东西。希望这有帮助！