我已经将堆排序算法实现为Python或Java（或任何其他语言）。因为我在Python或Java中并不是那么“流利”，所以我决定同时做这两件事。
但是在这里我遇到了一个问题，程序的运行时间太高了，而不是“应该”。我的意思是，堆排序应该运行到O（n * log n），并且对于以几GHz的时钟速率运行的当前处理器，我没想到该算法运行到超过2000secs的数组大小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），我在main函数中使用此循环：
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倍，所以现在它的运行时间仅为2秒，大小为320k
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
并且它使用与之前给出的相同的主要运行
有趣的是，你发布了计算机的时钟速度 - 你可以计算你的算法所需的实际步数......但是你需要知道很多关于实现的信息。例如，在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）时间插入（0）方法更好地向后使用输出！如果你真的需要订单，你可以使用dequeue对象输出以获得appendleft方法）
如果您发布了整个代码，那么我们可能会提供很多其他小事情。希望这有帮助！