Предложения по оптимизации для мин кучи


Может кто-нибудь оптимизации для моей реализации минута кучи.Его производительность низка по сравнению с heapq модуль в Python. Мой вариант использования класса MinHeap будет 'N' вставок и выборок, где N > 1,000,000.

import math


class MinHeap:
    def __init__(self, arr):
        self.__items = arr
        self.build_heap()

    def size(self):
        """
        Returns the size of heap.
        """
        return len(self.__items)

    def items(self):
        """
        Returns the elements in the heap.
        """
        return self.__items

    def build_heap(self):
        """
        Builds heap using the list of elements.
        """
        for node_number in xrange(int(len(self.__items) / 2), 0, -1):
            self.heapify(node_number)

    def heapify(self, node_number):
        """
        Ensure that node follows heap property.
        """
        # return if leave node
        if node_number > int(len(self.__items) / 2):
            return

        node = self.__items[node_number-1]
        left_child = self.__items[(2 * node_number)-1] if (((2 * node_number)-1) < len(self.__items)) else None 

        right_child = self.__items[(2 * node_number + 1)-1] if (((2 * node_number + 1)-1) < len(self.__items)) else None        

        min_node = node

        if left_child != None and right_child != None:
            min_node = min(node, left_child, right_child)
        elif left_child != None :
            min_node = min(node, left_child)
        elif right_child != None :
            min_node = min(node, right_child)

        if min_node == node:
            return
        elif left_child!=None and min_node == left_child:

            self.__items[node_number - 1], self.__items[(2 * node_number)-1] = self.__items[(2 * node_number)-1], self.__items[node_number - 1]
            self.heapify(2 * node_number)
        elif right_child!=None and min_node == right_child:

            self.__items[node_number - 1], self.__items[(2 * node_number + 1)-1] = self.__items[(2 * node_number + 1)-1], self.__items[node_number - 1]
            self.heapify(2 * node_number + 1)

    def extract_min(self):
        """
        Returns the minimum element.
        """
        length = len(self.__items)
        if length == 0:
            return
        self.__items[0], self.__items[length-1] = self.__items[length-1], self.__items[0]
        min_element =  self.__items.pop()
        self.heapify(1);
        return min_element

    def insert(self, num):
        """
        Inserts a new element in the heap.
        """
        self.__items.append(num)
        current_node = len(self.__items)
        parent_node = int(current_node / 2)
        while current_node > 1:
            min_node = min(self.__items[current_node-1], self.__items[parent_node-1])
            if min_node == self.__items[parent_node-1]:
                break
            self.__items[current_node-1], self.__items[parent_node-1] = self.__items[parent_node-1], self.__items[current_node-1]
            current_node = parent_node
            parent_node = int(current_node / 2)


Комментарии
1 ответ

Комментарии с любыми методами: способом пойти, документ MinHeapтоже и пересмотреть PEP257 для деталей.
Ваш MinHeap решает ту же задачу, Модуль heapq используя почти такой же стратегию, и вы выражаете недовольство запустить время - бок о бок сравнения:


  • во многих местах, вы вычисляете что-то вроде node_number или parent_node чтобы повторно проиндексировать __items - не используя эту переменную, но что-то вроде parent_node - 1
    (Код, как вы думаете об этом: если есть несколько мест, где вы хотите, чтобы элемент с индексом i-1пишите a[i-1], b[i-1]..., если вы думаете, что же индексом происходит, чтобы быть i-1пишите j = i-1, a[j], b[j]...)
    оптимизации компилятора можно ожидать устранения общих подвыражений; что является более трудным для переводчика, чтобы оправдать (и я помню, почему это может быть трудно для Python).)

  • insert() присваивает новое значение для каждого кандидата на должность, а heapq._siftdown()/heappush() просто перемещает предметы, не имеющие первоочередного значения и помещает новый элемент один раз/два раза.

  • extract_min() меняет местами элементы на обоих концах, а не просто замена верхней приоритетном порядке (см. heapq.heappop())

  • heapify() условно назначает None для left_child и right_child чтобы идти дальше и условно выполнять инструкции, сравнение этих значений None (используя != вместо is&not)


    • heapq._siftup() использует реалистичный подход не сравнивая ценности "на пути вниз": половина узлы являются вершинами, это гораздо более вероятно, что новый элемент будет в конечном итоге в нижней части кучи.


  • heapq вводит heappushpop() как "быструю версию heappush последующим heappop."

Вы, кажется, быть согнуты на мышление узлы пронумерованы, начиная с 1 - ничего плохого в этом нет, и кодирование, как вы думаете о решении проблемы-это единственный разумный способ начать:
для выстрела от бедра, выделить один элемент массива, не использовать индекс 0 и бросить все " - 1".

2
ответ дан 5 февраля 2018 в 09:02 Источник Поделиться