У меня есть задание для реализации алгоритма сортировки кучи в Python или Java (или любые другие языки). Так как я не очень "свободно" говорю на Python или Java, я решил сделать и то, и другое.
Но здесь я столкнулся с проблемой: время выполнения программы слишком велико, чем "должно" быть.
Я имею в виду, что сортировка кучи должна работать в O (n * log n), а для текущего процессора, работающего на тактовой частоте в несколько ГГц, я не ожидал, что этот алгоритм будет работать с более чем 2000 сек для массива размером 320к
Итак, для того, что я сделал, я реализовал алгоритм из псевдокода такого рода на Python и в Java (я также попробовал код в Julia из Rosetta Code, чтобы увидеть, было ли время выполнения схожим, почему Julia? Случайный выбор)
Итак, я проверил вывод на наличие проблем с небольшим размером ввода, таких как массив размером 10, 20 и 30. Похоже, что массив правильно отсортирован в обеих языках / реализациях.
Затем я использовал библиотеку heapq, которая реализует этот же алгоритм, чтобы еще раз проверить, было ли время выполнения одинаковым. Меня это удивило, когда это было на самом деле ... Но после нескольких попыток я попробовал еще одну вещь - обновление Python, и затем программа, использующая heapq, работала намного быстрее, чем предыдущие. На самом деле это было около 2k сек для массива 320k, а теперь около 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,6 ГГц я бы ожидал что-то около 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-библиотеке, потому что есть одна, чтобы увидеть разницу с моей реализацией, моя ошибка)
Большое спасибо.
Редактировать: Я забыл добавить, что я запускаю эту программу на MacBook Pro (последняя версия MacOS, i7 2,6 ГГц. В случае, если проблема также может быть вызвана чем-то еще, кроме кода.
Редактировать 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
И он работает с использованием того же основного, что и ранее