Фибоначчи против Бинарное повышение производительности кучи в методе Fast Marching

Question

Я сейчас этот вопрос задавал много раз. Тем не менее, я не могу найти решение для моей конкретной проблемы.

Я реализовал метод быстрого марширования (очень похожий на Дейкстру) в C++11 и два разных варианта: с кучей Фибоначчи и двоичной кучей. Для этого я использовал реализации кучи Boost 1.55 (Фибоначчи и D_ary, D=2).

Ожидается, что двоичная куча будет быстрее в маленьких сетках, а Фибоначчи будет быстрее в огромных сетках. Однако двоичная куча всегда быстрее (и есть "огромная" разница). Например:

200x200 grid: 
 Binary: 16 ms
 Fibonacci: 24 ms

300x300 grid: 
 Binary: 38 ms
 Fibonacci: 50 ms

500x500 grid: 
 Binary: 113 ms
 Fibonacci: 148 ms

1000x1000 grid: 
 Binary: 504 ms
 Fibonacci: 642 ms

я использую -Ofast -fno-finite-math-only флаги в G++ 4.8.

Суть в том, что я могу заверить, что несколько недель назад точно такая же реализация дала ожидаемые результаты.

Кто-нибудь может дать мне немного света на это, пожалуйста?

Спасибо!

Answer 1

На самом деле я нашел ответ, и никакой код не был необходим:

Есть две разные проблемы: - 1: это зависит от процессора. Один и тот же дистрибутив Ubuntu, один и тот же компилятор и один и тот же код дают разные результаты на одном компьютере. - 2: размер сетки был недостаточно большим. Мне пришлось подняться до 4000x4000, чтобы получить большее время для версии Дари, чем для версии Фибоначчи. В других компьютерных тестах, которые я тестировал (оба 64-битных), было достаточно с сеткой 2000x2000, чтобы получить ожидаемые результаты.

Кроме того, это зависит от источника, в котором вычисляется карта расстояний, и от других небольших точек, которые зависят от теории куч и метода быстрого марширования.