Я ищу информацию о том, как эффективно реализовать двоичные кучи. Я чувствую, что там должна быть хорошая статья о том, как эффективно реализовать кучи, но я ее не нашел. На самом деле мне не удалось найти какие-либо ресурсы по поводу реализации effective за пределами основ, таких как сохранение кучи в массиве. Я ищу методы для создания быстрой двоичной кучи за пределами тех, которые я описываю ниже.
Я уже написал реализацию на С++, которая быстрее, чем Microsoft Visual С++ и GCC std:: priority_queue, или с помощью std:: make_heap, std:: push_heap и std:: pop_heap. Ниже приведены методы, которые я уже рассмотрел в своей реализации. Я только придумал последние 2, хотя я сомневаюсь, что это новые идеи:
(Edit: добавлен раздел по оптимизации памяти)
Начать индексы в 1
Посмотрите на заметки о реализации Википедии для двоичных куч. Если корень кучи помещен в индекс 0, то формулы для родительского, левого и правого-потомков node в индексе 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 сравнения на уровень, который мы проходим, и мы, вероятно, пойдем далеко вниз по куче, так как мы переместили лист на вершину кучи. Поэтому мы должны ожидать немного меньше, чем 2 log n сравнения.
Вместо этого мы можем оставить отверстие в куче, где был верхний элемент. Затем мы перемещаем это отверстие в кучу, итеративно перемещая больший ребенок вверх. Это требует только 1 сравнения за уровень, который мы проходим. Таким образом, отверстие станет листом. На этом этапе мы можем переместить правый нижний лист в положение отверстия и переместить это значение до тех пор, пока свойство кучи не будет восстановлено. Поскольку значение, которое мы перемещали, было листом, мы не ожидаем, что оно движется очень далеко по дереву. Поэтому мы должны ожидать немного больше, чем log n сравнения, что лучше, чем раньше.
Поддержка замены top
Предположим, вы хотите удалить элемент max, а также вставить новый элемент. Затем вы можете выполнить любую из описанных выше реализаций удаления/поп, но вместо того, чтобы перемещать правый нижний лист, вы используете новое значение, которое вы хотите вставить/нажать. (Когда большинство операций такого типа, я обнаружил, что дерево турниров лучше, чем куча, но в остальном куча немного лучше.)
Сделайте sizeof (T) мощностью 2
Родительские, лево-дочерние и правые-дочерние формулы работают над индексами, и их нельзя заставить работать непосредственно с значениями указателя. Таким образом, мы собираемся работать с индексами, и это означает, что мы оцениваем значения p [i] в массиве p из индекса i. Если p - T *, а я - целое число, то
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i
и компилятор должен выполнить это вычисление, чтобы получить p [i]. sizeof (T) является константой времени компиляции, и умножение может быть выполнено более эффективно, если sizeof (T) является степенью двух. Моя реализация ускорилась, добавив 8 заполняющих байтов для увеличения sizeof (T) с 24 до 32. Уменьшенная эффективность кеша, вероятно, означает, что это не выигрыш для достаточно больших наборов данных.
Предварительно умножить индексы
Это было увеличение производительности на 23% в моем наборе данных. Единственное, что мы делаем с индексом, отличным от поиска родителя, левого и правого ребёнка, - это просмотр индекса в массиве. Поэтому, если мы будем отслеживать j = sizeof (T) * я вместо индекса i, тогда мы могли бы выполнить поиск p [i] без умножения, которое иначе неявно при оценке p [i], поскольку
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i == static_cast<char*>(p) + j
Тогда формулы слева-ребенка и правого ребенка для j-значений становятся соответственно 2 * j и 2 * j + sizeof (T). Родительская формула немного сложнее, и я не нашел способ сделать это иначе, чем преобразование значения j в значение я и обратно так:
parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T)
Если sizeof (T) является степенью 2, то это скомпилируется в 2 смены. Это 1 операция больше, чем обычный родитель с использованием индексов i. Однако мы сохраняем 1 операцию при поиске. Таким образом, чистый эффект заключается в том, что поиск родителя занимает такое же количество времени таким образом, в то время как поиск левого и правого ребёнка становится быстрее.
Оптимизация памяти
Ответы TokenMacGuy и templatetypedef указывают на оптимизацию на основе памяти, которая уменьшает промахи в кэше. Для очень больших наборов данных или редко используемых очередей приоритетов части очереди могут быть заменены ОС на ОС. В этом случае стоит добавить много накладных расходов, чтобы оптимально использовать кеш, потому что замена с диска происходит очень медленно. Мои данные легко вписываются в память и постоянно используются, поэтому часть очереди, скорее всего, не будет заменена на диск. Я подозреваю, что это относится к большинству применений очередей приоритетов.
Существуют другие очереди приоритетов, которые предназначены для более эффективного использования кэша ЦП. Например, в 4-куче должно быть меньше промахов в кеше, и количество дополнительных накладных расходов не так много. LaMarca и Ladner сообщили в 1996 году, что они получают 75% -ное улучшение производительности от согласования 4-х кучек. Тем не менее, Hendriks сообщает в 2010 году, что:
Также были проверены усовершенствования неявной кучи, предложенные Ламаркой и Ладнер [17] для улучшения локальности данных и сокращения промахов в кэше. Мы реализовали четырехпозиционную кучу, которая действительно демонстрирует немного лучшую согласованность, чем двухсторонняя куча для очень искаженных входных данных, но только для очень больших размеров очереди. Очень большие размеры очереди лучше обрабатываются иерархической кучей.
Вопрос
Есть ли больше методов, чем эти?
