Блог

Мой вариант использования выглядит следующим образом:

1. Мне нужно получить минимум набора растущих элементов; мне понадобится только минимум для любой итерации
2. Я обновлю минимальное значение, после чего оно гарантированно перестанет быть минимальным, но его новая позиция в заказе, как правило, не вычисляется напрямую.
3. Я помещаю это новое значение обратно в коллекцию и перехожу к следующей итерации, где я смотрю на новый минимальный элемент.

Прямо сейчас я использую std::vector и std::pop_heap std::push_heap следующим образом. Я вызываю std::pop_heap в своем векторе, который помещает минимальный элемент в конец вектора, я получаю ссылку на последний элемент и обновляю его, затем я вызываю std::push_heap, который перемещает последний элемент в его новое местоположение. Поэтому мне не нужно копировать структуру из std::vector, чтобы обновить ее в данный момент. Рассматриваемая структура имеет размер 16 байт и легко поддается конструированию, она довольно простая, полностью состоящая из целых типов.

Согласно моему профилировщику и по целому ряду проблем, которые я вижу, я трачу> 75% своего процессорного времени в std ::pop_heap и ~ 10% в std ::push_heap. Теперь логика, выполняемая для каждого минимального элемента, который проверяется, довольно тривиальна, состоящая в основном из дополнений и нескольких сравнений с фиксированным вводом, поэтому я полагаю, что возможно, что это так же хорошо, как и получается. Однако, если есть другая или случайная странная структура данных, которая может быть быстрее, чем min_heap, которую я сейчас использую, было бы интересно попробовать.

Я пробовал std ::min_element, std::nth_element, std::sort, каждый из которых занимает мое текущее время решения менее 1 секунды для задачи размером 1 000 000 или меньше и увеличивает время выполнения на порядки (многие 10 секунд). Чего я и ожидал, учитывая, что все они имеют худшую сложность, чем std::push_heap и std::pop_heap.

Я также пытался использовать древовидные структуры, такие как std ::map и std::set, но это также снижает производительность (у меня сейчас нет удобных чисел).

Итак, кто-нибудь знает что-нибудь лучше, чем min_heap для этого варианта использования?

(К сожалению, я не могу предоставить исходный код, но, учитывая, что 85% процессорного времени тратится на pop_heap / push_heap, я не думаю, что это было бы очень полезно в любом случае)

Редактировать: Оператор сравнения — это единственное сравнение между двумя целочисленными типами. таким образом, это не похоже на то, что оператор сравнения, используемый в куче, выполняет огромный объем работы.

Вместо того, чтобы удалять минимальный элемент и повторно вставлять обновленное значение, вы можете изменить значение на месте и понизить значение из корня. Удаление минимального элемента часто заменяет его одним из худших элементов для замены корня, что обычно обходится в длинный нижний пузырь, а затем повторная вставка относительно небольшого значения также обходится в относительно длинный верхний пузырь. Изменение ключа на месте заменяет оба из них, взятых вместе, только одним понижающим пузырьком, который также обычно короче, если новое значение остается в среднем относительно близко к корню.

К сожалению, для этого нет функции <algorithm> , но не так уж сложно создать свою собственную. Запишите это в терминах перемещений в «дыру», оставшуюся после создания временной копии корня, а не в виде серии std::swap s. Выполнение этого с помощью swaps позволяет примерно удвоить общее количество загрузок и хранилищ.

Использование кучи большего размера (вероятно, 4, может быть, 8) может помочь.