Среда выполнения Python heapify

Question

Я изучаю структуры данных и алгоритмы, в которых я должен был реализовать алгоритм heapsort для запуска в определенный период времени. Ниже приведены две реализации:

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

Здесь self._n - это размер входных данных, self._data - список элементов, которые должны быть сформированы в кучу. Эта реализация проходит тест с гораздо меньшим временем выполнения (наибольшая итерация занимает до 0,32 секунды из указанных 3 секунд лимит времени).

Ниже приведен второй фрагмент кода, который с треском проваливается (самая большая итерация занимает до 6 секунд)

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)

Я хотел бы понять причину такой большой разницы во времени выполнения. Я предположил, что это может быть связано со сменой элементов списка на каждом шаге в цикле while, но поскольку список в python является в основном массивом, я понял, что перестановки также должны выполняться с постоянными временными шагами (это мое предположение. Пожалуйста, исправьте меня, если я неправильно).

заранее спасибо

Answer 1

В соответствии с рекомендациями user2357112 и user2357112 в комментариях выше, проблема заключалась в операции.index() в строке ниже.

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

Время нахождения индекса элемента в массиве равно O(n), так как требует обхода массива до тех пор, пока не будет найдено первое совпадение значения. Это приводит к чрезмерно долгому времени выполнения во второй реализации. В первой реализации это было заменено непосредственным сравнением значений рассматриваемого дочернего элемента и его соседнего дочернего элемента, как показано ниже.

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

Поскольку массивы имеют постоянное время доступа к элементам, вышеописанная реализация является постоянным временем, что сокращает время работы.