Python heapify Implementierung Laufzeit

Question

Ich nehme einen Kurs über Datenstrukturen und Algorithmen, wo ich den Heapsort-Algorithmus implementieren sollte, um in einem bestimmten Zeitrahmen zu laufen. Im Folgenden sind die beiden Implementierungen:

def generateSwaps(): 
size=self._n 
    for root in range((size//2)-1,-1,-1): 
     root_val = self._data[root]    # save root value 
     child = 2*root+1 
     while(child<size): 
      if child<size-1 and self._data[child]>self._data[child+1]: 
       child+=1 
      if root_val<=self._data[child]:  # compare against saved root value 
       break 
      self._data[(child-1)//2]=self._data[child] # find child's parent's index correctly 
      self._swaps.append(((child-1)//2,child)) 
      child=2*child+1 
      # print(child) 
     self._data[(child-1)//2]=root_val  # here too, and assign saved root value 
    return self._data 

Hier self._n die Größe des Eingangs ist, ist self._data eine Liste von Elementen, die in eine heap.This Umsetzung gebildet müssen den Test besteht mit vielen Untertrum Zeit (größte Iteration, die bis zu 0,32 Sekunden von der vorgegebenen 3-Sekunden-Zeitgrenze dauert).

Unten ist das zweite Codestück, das kläglich (bis zu 6 Sekunden dauert mit dem größten Iteration) nicht

for i in range(self._n//2 , -1, -1): 
     child_index = 0 
     if (2*i + 2) == self._n: 
     child_index = 2*i + 1 
     elif (2*i + 2) < self._n: 
     child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2])) 
     else: 
     child_index = 0 

     while self._data[i] > self._data[child_index]: 
     b = 0 
     print("child is smaller for n = " + str(i)) 
     print(child_index) 
     if child_index == 0: 
      break 
     else: 
      self._swaps.append((i, child_index)) 
      self._data[i], self._data[child_index] = self._data[child_index], self._data[i] 
      if child_index <= n//2: 
      i = child_index 
      else: 
      break 
      if (2*i + 2) == self._n: 
      child_index = 2*i + 1 
      elif(2*i + 2) < self._n: 
      child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2])) 
      else: 
      child_index = 0 

     print("hello work") 
     self._data[i], self._data[child_index] = self._data[child_index], self._data[i] 
     print(self._data) 

Was ich möchte, ist der Grund für diese große Differenz verstehen mal in Laufen. Ich nahm an, dies könnte durch das Austauschen von Listenelementen bei jedem Schritt in der while-Schleife verursacht werden, aber da eine Liste in Python im Grunde ein Array ist, erkannte ich, dass Swaps auch konstante Zeitschritte sein sollten (dies ist meine Annahme. Bitte korrigieren Sie mich, wenn ich eine falsche).

Vielen Dank im Voraus

Answer 1

Wie oben in den Kommentaren von user2357112 und user2357112 Vorgeschlagen wurde das Problem der .index() Betrieb in der unterhalb der Linie.

child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2])) 

Runitime von in einem Array-Index eines Elements zu finden, ist O (n), wie es zu Fuß durch das Array benötigt, bis Sie in einem ersten Spiel finden, die value.This die übermäßig lange Laufzeit in der zweiten Ursachen Implementierung. In der ersten Implementierung wurde dies durch den direkten Vergleich der Werte des betrachteten Kindes und seines benachbarten Kindes ersetzt, wie unten gezeigt.

if child<size-1 and self._data[child]>self._data[child+1]: 
    child+=1 

Da Arrays konstante Zeit Zugriff auf Elemente aufweist, ist die obige Implementierung somit konstante Zeit, um die Laufzeit zu reduzieren.