为什么我的 Python 脚本 运行 比我的 HeapSort 实现慢？
Why does my Python script run slower than it should on my HeapSort implementation?
我的任务是将堆排序算法实现为 Python 或 Java（或任何其他语言）。由于我在 Python 或 Java 中并不是真正的 "fluent"，所以我决定两者都做。
但是我运行遇到了一个问题，运行程序的运行时间比"should"高太多了。
我的意思是，堆排序应该 运行 到 O(n * log n) 并且对于当前处理器 运行 宁在几个 GHz 的时钟速率上我没想到对于大小为 320k
的数组，算法 运行 超过 2000 秒
因此，对于我所做的，我在 Python 和 Java 中通过此类伪代码实现了算法（我还尝试了 Rosetta Code 中的 Julia 代码以查看如果 运行ning 时间相似，为什么是 Julia？随机选择）
所以我检查了输出是否存在小输入大小问题，例如大小为 10、20 和 30 的数组。看来它在 languages/implementations.
中都正确排序了数组
然后我使用实现相同算法的 heapq 库再次检查 运行ning 时间是否相似。当实际情况如此时，这让我感到惊讶......但经过几次尝试后，我尝试了最后一件事，即更新 Python 然后，使用 heapq 运行 的程序比以前的程序快得多。实际上，320k 阵列大约需要 2k 秒，现在大约需要 1.5 秒左右。
我重试了我的算法，问题仍然存在。
下面是我实现的 Heapsort class：
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
如果您需要其余的代码来查看错误可能出在哪里，请不要犹豫，我会提供。就是不想无缘无故分享整个文件。
如前所述，我预期的 运行ning 时间是最坏情况下的 运行ning 时间：O(n * log n)
使用现代架构和 2.6GHz 的处理器，我希望大约 1 秒或更少（因为 运行ning 时间以纳秒为单位询问，我想即使 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
我认为这些结果可以用来确定需要多少时间，具体取决于机器（理论上）
如您所见，高 运行ning 时间结果来自我的算法，但我无法分辨代码中的位置，这就是我在这里寻求帮助的原因。 （在 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
有趣的是，您发布了计算机的时钟速度 - 您可以计算出您的算法所需的实际步数...但是您需要了解很多关于实现的信息。例如，在 python 中，每次创建对象或超出范围时，解释器都会更新底层对象的计数器，并在这些引用计数达到 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 方法）
如果您发布了完整的代码，我们可能会提供很多其他的帮助。希望这对您有所帮助！
我的任务是将堆排序算法实现为 Python 或 Java（或任何其他语言）。由于我在 Python 或 Java 中并不是真正的 "fluent"，所以我决定两者都做。
但是我运行遇到了一个问题，运行程序的运行时间比"should"高太多了。 我的意思是，堆排序应该 运行 到 O(n * log n) 并且对于当前处理器 运行 宁在几个 GHz 的时钟速率上我没想到对于大小为 320k
的数组，算法 运行 超过 2000 秒因此，对于我所做的，我在 Python 和 Java 中通过此类伪代码实现了算法（我还尝试了 Rosetta Code 中的 Julia 代码以查看如果 运行ning 时间相似，为什么是 Julia？随机选择）
所以我检查了输出是否存在小输入大小问题，例如大小为 10、20 和 30 的数组。看来它在 languages/implementations.
中都正确排序了数组然后我使用实现相同算法的 heapq 库再次检查 运行ning 时间是否相似。当实际情况如此时，这让我感到惊讶......但经过几次尝试后，我尝试了最后一件事，即更新 Python 然后，使用 heapq 运行 的程序比以前的程序快得多。实际上，320k 阵列大约需要 2k 秒，现在大约需要 1.5 秒左右。
我重试了我的算法，问题仍然存在。
下面是我实现的 Heapsort class：
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
如果您需要其余的代码来查看错误可能出在哪里，请不要犹豫，我会提供。就是不想无缘无故分享整个文件。
如前所述，我预期的 运行ning 时间是最坏情况下的 运行ning 时间：O(n * log n) 使用现代架构和 2.6GHz 的处理器，我希望大约 1 秒或更少（因为 运行ning 时间以纳秒为单位询问，我想即使 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
我认为这些结果可以用来确定需要多少时间，具体取决于机器（理论上）
如您所见，高 运行ning 时间结果来自我的算法，但我无法分辨代码中的位置，这就是我在这里寻求帮助的原因。 （在 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
有趣的是，您发布了计算机的时钟速度 - 您可以计算出您的算法所需的实际步数...但是您需要了解很多关于实现的信息。例如，在 python 中，每次创建对象或超出范围时，解释器都会更新底层对象的计数器，并在这些引用计数达到 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 方法）
如果您发布了完整的代码，我们可能会提供很多其他的帮助。希望这对您有所帮助！