时间戳

首页 > 解决方案 > 为什么我的 Python 脚本在我的 HeapSort 实现上运行得比它应该运行的慢？

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

问题描述

我的任务是在 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 = []

        i = len(heap.heap) - 1
        while i >= 0:
            heap.heap[0], heap.heap[i] = heap.heap[i], heap.heap[0]
            output = [heap.heap[i]] + output
            heap.remove(heap.heap[i])
            heap.maxHeapify(heap.heap, 0)
            i -= 1
        return output

为了记录每个数组大小（10000 - 320000）的运行时间，我在主函数中使用了这个循环：

     i = 10000
     while i <= 320000:
         tab = [0] * i
         j = 0
         while j < i:
             tab[j] = randint(0, i)
             j += 1
         start = time()
         MaxHeap.heapSort(tab)
         end = time()
         pprint.pprint("Size of the array " + str(i))
         pprint.pprint("Total execution time: " + str(end - start) + "s")
         i *= 2

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

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

以下是结果：

Python (own) :                 Java (Own)

  Time        Size               Time       Size 
 593ms.       10k               243ms.      10k
 2344ms.      20k               600ms.      20k
 9558ms.      40k               1647ms.     40k
 38999ms.     80k               6666ms.     80k
 233811ms.    160k              62789ms.    160k
 1724926ms.   320k              473177ms.   320k

Python (heapq)                 Julia (Rosetta Code)
  Time        Size               Time        Size
 6ms.         10k               21ms.        10k
 14ms.        20k               21ms.        20k
 15ms.        40k               23ms.        40k
 34ms.        80k               28ms.        80k
 79ms.        160k              39ms.        160k
 168ms.       320k              60ms.        320k


And according to the formula the O(n * log n) give me :
40000       10k
86021       20k
184082      40k
392247      80k
832659      160k
1761648     320k

我认为这些结果可用于确定取决于机器（理论上）应该花费多少时间

如您所见，高运行时间结果来自我的算法，但我不知道代码在哪里，这就是我在这里寻求帮助的原因。（在 Java 和 Python 中运行缓慢）（没有尝试在 java lib 中使用堆排序是否有一个看到我的实现的差异，我的错）

非常感谢。

编辑：我忘了补充说我在 MacBook Pro（最新版本 MacOS，i7 2,6GHz）上运行这个程序。如果问题也可能来自代码以外的任何其他东西。

编辑 2：这是我根据收到的答案对算法所做的修改。该程序的运行速度比以前快了大约 200 倍，因此对于大小为 320k 的数组，它现在只需 2 秒即可运行

class MaxHeap:

    def __init__(self, data=None):
        self.heap = []
        self.size = 0

        if data is not None:
            self.size = len(data)
            self.buildMaxHeap(data)

    def toString(self):
        return str(self.heap)

    def add(self, elem):
        self.heap.insert(self.size, elem)
        self.size += 1
        self.buildMaxHeap(self.heap)

    def remove(self, elem):
        try:
            self.heap.pop(self.heap.index(elem))
        except ValueError:
            print("The value you tried to remove is not in the heap")

    def maxHeapify(self, heap, i):
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i

        if left < self.size and heap[left] > heap[largest]:
            largest = left
        if right < self.size and heap[right] > heap[largest]:
            largest = right
        if largest != i:
            heap[i], heap[largest] = heap[largest], heap[i]
            self.maxHeapify(heap, largest)

    def buildMaxHeap(self, heap):
        for i in range(self.size // 2, -1, -1):
            self.maxHeapify(heap, i)
        self.heap = heap

    @staticmethod
    def heapSort(table):
        heap = MaxHeap(table)

        i = len(heap.heap) - 1
        while i >= 0:
            heap.heap[0], heap.heap[i] = heap.heap[i], heap.heap[0]
            heap.size -= 1
            heap.maxHeapify(heap.heap, 0)
            i -= 1
        return heap.heap

它使用与之前给出的相同的 main 运行

标签： pythonalgorithmheapsort

解决方案

有趣的是，您发布了计算机的时钟速度-您可以计算算法所需的实际步数……但是您需要对实现有很多了解。例如，在 python 中，每次创建对象或超出范围时，解释器都会更新底层对象的计数器，并在这些 ref 计数达到 0 时释放内存。相反，您应该查看相对速度。

您发布的第三方示例显示，当输入数组长度加倍时，速度低于两倍。这似乎不对，是吗？事实证明，对于这些示例，构建数组的初始工作可能支配了对数组进行排序所花费的时间！

在您的代码中，已经有一条评论指出了我要说的话......

heap.remove(heap.heap[i]) 此操作将遍历您的列表（从索引 0 开始）寻找匹配的值，然后将其删除。这已经很糟糕了（如果它按预期工作，那么如果您的代码按预期工作，那么您将在该行上进行 320k 比较！）。但它变得更糟 - 从数组中删除一个对象不是就地修改 - 删除对象之后的每个对象都必须在列表中向前移动。最后，不能保证您实际上删除了那里的最后一个对象......可能存在重复值！

这是一个有用的网站，列出了 python 中各种操作的复杂性 - https://wiki.python.org/moin/TimeComplexity。为了尽可能高效地实现算法，您需要尽可能多的数据结构操作为 O(1)。这是一个示例...这是一些原始代码，大概是 heap.heap 是一个列表...

        output = [heap.heap[i]] + output
        heap.remove(heap.heap[i])

正在做

        output.append(heap.heap.pop())

将避免分配新列表并使用恒定时间操作来改变旧列表。（向后使用输出比使用 O(n) 时间 insert(0) 方法好得多！如果你真的需要订单，你可以使用 dequeue 对象作为输出来获取 appendleft 方法）

如果您发布了整个代码，那么我们可能会提供很多其他的小东西。希望这有帮助！

推荐阅读