Я ищу информацию о том, как эффективно реализовать двоичные кучи .Я чувствую, что где-то должна быть хорошая статья об эффективной реализации кучи, но я ее не нашел.На самом деле мне не удалось найти какие-либо ресурсы по поводу эффективной реализации, помимо основ, таких как хранение кучи в массиве.Я ищу методы для создания быстрой двоичной кучи помимо тех, которые я описываю ниже.
Я уже написал реализацию C ++, которая работает быстрее, чем Microsoft Visual C ++ и GCC std :: priority_queue или использует std:: make_heap, std :: push_heap и std :: pop_heap.Ниже приведены методы, которые я уже рассмотрел в своей реализации.Я только придумал последние 2, хотя сомневаюсь, что это новые идеи:
(Редактировать: добавлен раздел по оптимизации памяти)
Начать индексы с 1 Посмотрите на
замечания по реализации Википедии для двоичных куч.Если корень кучи находится в индексе 0, то формулы для parent, left-child и right-child узла в index 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 сравнений, что лучше, чем раньше.
Support replace-top Предположим, вы хотите удалить элемент max, а такжевставить новый элемент.Затем вы можете выполнить любую из описанных выше реализаций удаления / выталкивания, но вместо перемещения крайнего правого нижнего листа вы используете новое значение, которое вы хотите вставить / нажать.(Когда большинство операций такого типа, я обнаружил, что турнирное дерево лучше, чем куча, но в остальном куча немного лучше.)
Сделать sizeof (T) степеньюиз 2 Родительские, левые и правые дочерние формулы работают с индексами, и их нельзя заставить работать непосредственно со значениями указателя.Итак, мы будем работать с индексами, а это подразумевает поиск значений p [i] в массиве p по индексу i.Если p - это T *, а i - целое число, то
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i
и компилятор должен выполнить это вычисление, чтобы получить p [i].sizeof (T) является константой времени компиляции, и умножение может быть выполнено более эффективно, если sizeof (T) является степенью двойки.Моя реализация стала быстрее благодаря добавлению 8 байтов заполнения для увеличения sizeof (T) с 24 до 32. Снижение эффективности кэша, вероятно, означает, что это не является победой для достаточно больших наборов данных.
Предварительно умножить индексы Это было увеличение производительности моего набора данных на 23%. Единственное, что мы когда-либо делаем с индексом, отличным от поиска parent, left-child и right-child, - это поиск индекса в массиве. Таким образом, если мы будем отслеживать j = sizeof (T) * i вместо индекса 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-значение в i-значение и обратно, вот так:
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 кучи. Однако Хендрикс сообщает в 2010 году, что:
Были также протестированы улучшения неявной кучи, предложенные LaMarca и Ladner [17] для улучшения локальности данных и уменьшения количества кешей. Мы реализовали четырехстороннюю кучу, которая действительно демонстрирует немного лучшую согласованность, чем двухсторонняя куча для очень искаженных входных данных, но только для очень больших размеров очереди. Очень большие размеры очереди лучше обрабатываются иерархической кучей.
Вопрос
Есть ли больше техник, чем эти?