Как улучшить Boost Fibonacci Heap performance

Question

Я реализую алгоритм Fast Marching, который является своего рода непрерывным Dijkstra. Как я читал во многих работах, куча Фибоначчи является наиболее подходящей кучей для этой цели.

Однако, при профилировании с 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_; 

Это нормально, что он принимает «что много» времени, или есть что-то я могу сделать, чтобы улучшить производительность?

Извините, если недостаточно информации. Я старался быть как можно более кратким. При необходимости добавлю дополнительную информацию.

Спасибо!

Answer 1

Поп() по умолчанию (Fibanacci Heap) имеет амортизированное время выполнения O (log n) и наихудший случай O (n). Если ваша куча велика, она может легко потреблять большую часть времени процессора в вашем алгоритме, тем более что большинство других операций, которые вы, скорее всего, используете, имеют O (1) время автономной работы (вставка, верх и т. Д.)

Я бы рекомендовал попробовать callgrind с вашим предпочтительным уровнем оптимизации (например, -O3) с информацией об отладке (-g), потому что templatized datastructures/container, такие как fibonacci_heap, сильно зависят от использования встроенной функции. Может быть, большинство циклов процессора, которые вы измеряете, даже не существует в вашем оптимизированном исполняемом файле.

Answer 2

В других ответах не упоминается большая часть: конечно, pop() занимает большую часть вашего времени: это единственная функция, которая выполняет любую реальную работу!

Как вы, возможно, читали, границы операций Фибоначчи-Кучи являются амортизированными границами. Это означает, что , если вы выполняете достаточно операций в хорошей последовательности, границы будут в среднем равны этому. Однако фактические затраты полностью скрыты.

Каждый раз, когда вы вставляете элемент, ничего не происходит. Он просто забрасывается в корневой список. Бум, O (1) раз. Каждый раз, когда вы объединяете два дерева, его корень просто связан с корневым списком. Бум, O (1) раз. Но держитесь, ваша структура не является допустимой кучей Фибоначчи! Вот где приходит pop() (или extract-root): каждый раз, когда эта операция вызывается, вся куча реструктурируется обратно в правильную форму. Корень удаляется, его дети вырезаются в корневом списке, а затем мы начинаем слияние деревьев в корневом списке, чтобы в корневом списке не было двух деревьев с одинаковой степенью (количество детей).

Итак, вся работа Insert (e) и Merge (t) на самом деле задерживается до тех пор, пока не вызывается Pop(), которая затем выполняет всю работу. Как насчет других операций?

Удалить (e) красиво. Мы выполняем Decrease-Key (e, -inf), чтобы элемент e стал корнем. И теперь мы выполняем Pop()! Опять же, работа выполняется Pop().

Decrease-Key (e, v) выполняет свою работу сам по себе: он разрезает e в корневой список и запускает срезающий каскад, чтобы также поместить своих детей в корневой список (что также может сократить их дочерние списки). Таким образом, Decrease-Key помещает в список корней множество элементов. Можете ли вы угадать, какая функция должна это исправить?

TL; DR: Pop() является рабочей лошадью Кучи Фибоначчи. Все остальные операции выполняются эффективно, поскольку они создают работу для операции Pop(). Pop() собирает работу и выполняет ее за один раз (что может занять до O (n)). Это действительно эффективно, потому что «сгруппированные» работы могут выполняться быстрее, чем каждая операция отдельно.

Так что да, естественно, что Pop() занимает большую часть вашего времени!