Как улучшить производительность Boost Fibonacci Heap
Я реализую алгоритм Fast Marching, который представляет собой некий непрерывный Дейкстра. Как я читал во многих статьях, куча Фибоначчи — самая подходящая куча для этой цели.
Однако при профилировании с помощью callgrind моего кода я вижу, что следующая функция отнимает 58% времени выполнения:
int popMinIdx () {
const int idx = heap_.top()->getIndex();
heap_.pop();
return idx;
}
Конкретно, pop() занимает 57,67% всего времени выполнения.
heap_определяется следующим образом:
boost::heap::fibonacci_heap<const FMCell *, boost::heap::compare<compare_cells>> heap_;
Это нормально, что это занимает «так много» времени, или я могу что-то сделать, чтобы улучшить производительность?
Извините, если недостаточно информации предоставлено. Я старался быть максимально кратким. Я добавлю больше информации, если это необходимо.
Спасибо!
Решение
Функция pop () кучи Fibanacci имеет амортизированное время выполнения O (log n) и худший случай O (n). Если ваша куча велика, она может легко потреблять большую часть процессорного времени в вашем алгоритме, тем более что большинство других операций, которые вы, вероятно, используете, имеют время выполнения O (1) (insert, top и т. Д.)
Одна вещь, которую я бы порекомендовал, это попробовать callgrind с вашим предпочтительным уровнем оптимизации (например, -O3) с отладочной информацией (-g), потому что шаблонизированные структуры данных / контейнеры, такие как fibonacci_heap, сильно влияют на использование встроенных функций. Вполне возможно, что большинство измеряемых вами циклов ЦП даже не существует в оптимизированном исполняемом файле.
Другие решения
Другие ответы не упоминают большую часть: конечно, pop () отнимает большую часть вашего времени: это единственная функция, которая выполняет любую реальную работу!
Как вы, возможно, читали, границы операций с кучей Фибоначчи являются амортизированными границами. Это означает, что если вы выполняете достаточно операций в хорошей последовательности, границы будут усреднены к этому. Однако фактические затраты полностью скрыты.
Каждый раз, когда вы вставляете элемент, ничего не происходит. Он просто выбрасывается в корневой список. Бум, O (1) раз. Каждый раз, когда вы объединяете два дерева, его корень просто связывается с корневым списком. Бум, O (1) раз. Но подождите, ваша структура не является действительной кучей Фибоначчи! Вот где приходит pop () (или extract-root): каждый раз, когда вызывается эта операция, вся куча реструктурируется обратно в правильную форму. Корень удаляется, его дочерние элементы обрезаются до корневого списка, и затем мы начинаем объединять деревья в корневом списке, чтобы в корневом списке не было двух деревьев с одинаковой степенью (числом дочерних элементов).
Таким образом, вся работа Insert (e) и Merge (t) фактически задерживается до вызова Pop (), который затем выполняет всю работу. А как насчет других операций?
Удалить (е) красиво. Мы выполняем команду Decrease-Key (e, -inf), чтобы элемент e стал корневым. И теперь мы исполняем Pop ()! Опять же, работа выполняется Pop ().
Decrease-Key (e, v) выполняет свою работу сам: он обрезает e до корневого списка и запускает каскад обрезки, чтобы также поместить своих дочерних элементов в корневой список (что также может обрезать их дочерние списки). Таким образом, Decrease-Key помещает множество элементов в корневой список. Можете ли вы угадать, какая функция должна это исправить?
TL; DR: Pop () — рабочая лошадка кучи Фибоначчи. Все остальные операции выполняются эффективно, потому что они создают работу для операции Pop (). Pop () собирает работу и выполняет ее за один раз (что может занять до O (n)). Это действительно очень эффективно, потому что «групповая» работа может выполняться быстрее, чем каждая операция в отдельности.
Так что да, естественно, что Pop () занимает большую часть вашего времени!