Эффективная реализация двоичных куч
Я ищу информацию о том, как реализовать двоичный файл. aps эффективно. Я чувствую, что где-то должна быть хорошая статья об эффективной реализации кучи, но я ее не нашел. Фактически, мне не удалось найти никаких ресурсов по вопросу эффективной реализации, помимо таких основ, как хранение кучи в массиве. Я ищу методы создания быстрой двоичной кучи помимо тех, которые я описываю ниже.
Я уже написал реализацию C ++, которая быстрее, чем std :: priority_queue в Microsoft Visual C ++ и GCC, или использующая std :: make_heap, std :: push_heap и std :: pop_heap. Ниже приведены методы, которые я уже использовал в своей реализации. Я сам придумал только последние 2, хотя сомневаюсь, что это новые идеи:
(Правка: добавлен раздел по оптимизации памяти)
См. Примечания по реализации в Википедии для двоичных куч. Если корень кучи помещен в индекс 0, то формулы для родительского, левого дочернего и правого дочернего узла узла с индексом n будут соответственно (n-1) / 2, 2n + 1 и 2n + 2. Если вы используете массив, основанный на 1, то формулы становятся более простыми n / 2, 2n и 2n + 1. Таким образом, родительский и левый дочерний элементы более эффективны при использовании массива, основанного на 1. Если p указывает на массив, начинающийся с 0, и q = p - 1, тогда мы можем получить доступ к p [0] как q [1], поэтому нет накладных расходов при использовании массива, основанного на 1.
Попадание в куче часто описывается заменой верхнего элемента на крайний левый нижний лист и последующим перемещением его вниз до восстановления свойства кучи. Для этого требуется 2 сравнения на каждый уровень, по которому мы проходим, и мы, вероятно, уйдем далеко вниз по кучу, поскольку переместили лист на вершину кучи. Таким образом, мы должны ожидать немного меньше двух сравнений log n.
Вместо этого мы можем оставить дыру в куче там, где был верхний элемент. Затем мы перемещаем это отверстие в кучу, итеративно перемещая больший дочерний элемент вверх. Для этого требуется только одно сравнение на каждый уровень, который мы пройдем. Таким образом отверстие станет листом. На этом этапе мы можем переместить крайний правый нижний лист в положение отверстия и переместить это значение вверх, пока свойство кучи не будет восстановлено. Поскольку значение, которое мы переместили, было листом, мы не ожидаем, что он продвинется очень далеко вверх по дереву. Так что нам следует ожидать немного большего, чем сравнение log n, что лучше, чем раньше.
Предположим, вы хотите удалить элемент max, а также вставить новый элемент. Затем вы можете выполнить любую из описанных выше реализаций удаления / выталкивания, но вместо перемещения самого правого нижнего листа вы используете новое значение, которое хотите вставить / нажать. (Когда большинство операций такого рода, я обнаружил, что турнирное дерево лучше, чем куча, но в остальном куча немного лучше.)
Родитель, слева формулы -child и right-child работают с индексами, и их нельзя заставить работать непосредственно со значениями указателей. Итак, мы собираемся работать с индексами, что подразумевает поиск значений p [i] в массиве p по индексу i. Если p - это T *, а i - целое число, то
&(p[i]) == static_cast(p) + sizeof(T) * i
и компилятор должен выполнить это вычисление, чтобы получить p [i]. sizeof (T) - это константа времени компиляции, и умножение может быть выполнено более эффективно, если sizeof (T) является степенью двойки. Моя реализация стала быстрее, добавив 8 байтов заполнения, чтобы увеличить sizeof (T) с 24 до 32. Снижение эффективности кеша, вероятно, означает, что это не победа для достаточно больших наборов данных.
Это на моем наборе данных производительность увеличилась на 23%. Единственное, что мы делаем с индексом, кроме поиска родителя, левого потомка и правого дочернего элемента, - это поиск индекса в массиве. Таким образом, если мы отслеживаем j = sizeof (T) * i вместо индекса i, тогда мы могли бы выполнить поиск p [i] без умножения, которое в противном случае неявно при вычислении p [i], потому что
&(p[i]) == static_cast(p) + sizeof(T) * i == static_cast(p) + j
Тогда левый -детские и правые дочерние формулы для j-значений становятся соответственно 2 * j и 2 * j + sizeof (T). Родительская формула немного сложнее, и я не нашел другого способа сделать это, кроме преобразования j-значения в i-значение и обратно следующим образом:
parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T)
Если sizeof (T) является степенью двойки тогда это будет составлять 2 смены. Это на 1 операцию больше, чем у обычного родителя, использующего индексы i. Однако затем мы сохраняем 1 операцию поиска. Таким образом, общий эффект заключается в том, что поиск родителя таким образом занимает одинаковое количество времени, в то время как поиск левого дочернего и правого дочерних элементов становится быстрее.
Ответы TokenMacGuy и templatetypedef указывают на оптимизацию на основе памяти которые уменьшают промахи кеша. Для очень больших наборов данных или редко используемых очередей с приоритетом части очереди могут быть выгружены на диск операционной системой. В этом случае стоит добавить много накладных расходов для оптимального использования кеша, потому что загрузка с диска происходит очень медленно. Мои данные легко помещаются в памяти и используются постоянно, поэтому никакая часть очереди, скорее всего, не будет заменена на диск. Я подозреваю, что это справедливо для большинства случаев использования очередей с приоритетом.
Существуют и другие очереди с приоритетом, которые предназначены для более эффективного использования кэша ЦП. Например, у 4-х кучи должно быть меньше промахов кеша, а количество дополнительных накладных расходов не так уж и много. ЛаМарка и Ладнер сообщают в 1996 году, что они получают повышение производительности на 75% от перехода к выровненным 4-х кучкам. Однако, Хендрикс сообщает в 2010 году, что:
Также были протестированы улучшения неявной кучи, предложенные ЛаМаркой и Ладнером [17] для улучшения локальности данных и уменьшения количества промахов в кэше. Мы реализовали четырехстороннюю кучу, которая действительно показывает немного лучшую согласованность, чем двухсторонняя куча, для очень искаженных входных данных, но только для очень больших размеров очереди. Очереди очень больших размеров лучше обрабатываются иерархической кучей.
Есть ли другие методы, чем эти?