Добавление недостающей функции для работы с кучей

[Roman-Koshelev]

В стандарте есть функции для работы с кучей. is_heap, make_heap, push_heap, pop_heap и другие. Не достает std::shift_down которая будет просеивать модифицированный максимальный/минимальный элемент. Например библиотеки событий используют кучу для хранения таймеров. Те получаем таймер, отрабатываем callback и переводим. Делать перезавод удалением + добавлением не оптимально. (Та функция которую приходится заново писать на каждом месте работы)

[Roman-Koshelev]

На всякий случай привожу пример реализации #include <functional> #include <iterator> #include <algorithm>

template <class Iter, class Compare = std::less<typename std::iterator_traits<Iter>::value_type>> void sift_down(Iter first, Iter last, Compare comp = {}) { std::size_t len = last - first; std::size_t head = 0; std::size_t next = head; while (head < (len - 1) / 2) { next = 2 * (next + 1); if (comp(*(first + next), *(first + (next - 1)))) next--; if (comp(*(first + next), *(first + head))) break; std::iter_swap(first + next, first + head); head = next; }

if (((len % 2) == 0) && (next == (len - 2) / 2)) { next = 2 * head + 1; if (!comp(*(first + next), *(first + head))) std::iter_swap(first + next, first + head); }

}

[apolukhin]

Расскажите пожалуйста подробнее, можно ли расширить алгоритм, чтобы просеивать не только первый элемент вниз, но и

• элементы из середины вниз
• элементы из середины вверх

Нужны примеры помимо таймеров, где подобный подход полезен. Чем больше примеров - тем проще будет уговаривать людей из комитета

[Roman-Koshelev]

Думаю что нет смысла просеивать из середины, тк после построения кучи вся работа идет с вершиной. По крайней мере мне трудно придумать для чего может понадобится просеивание элемента из середины, и как мы вообще его получили из кучи (линейным поиском?). А вот то, что получив вершину мы ее модифицируем, а не удалим вполне логично.

[apolukhin]

По бенчмаркам получается, что sift_down даже немного проигрывает pop_heap+push_heap https://quick-bench.com/q/uGgN7SV6NWzoWmTwnjRBFpNX-t4

#include <algorithm>
#include <vector>

constexpr std::size_t kCount = 1024;
constexpr std::size_t kIntervals = 1024;

auto make_vector_heap() {
    std::vector<std::size_t> v;
    v.reserve(kCount);
    for (std::size_t i = 0; i < kCount; ++i) {
        v.push_back(i);
    }

    std::make_heap(v.begin(), v.end());
    return v;  
}

template <class Iter, class Compare = std::less<typename std::iterator_traits<Iter>::value_type>>
void sift_down(Iter first, Iter last, Compare comp = {}) {
    std::size_t len = last - first;
    std::size_t head = 0;
    std::size_t next = head;
    while (head < (len - 1) / 2) {
        next = 2 * (next + 1);
        if (comp(*(first + next), *(first + (next - 1)))) next--;
        if (comp(*(first + next), *(first + head))) break;
        std::iter_swap(first + next, first + head);
        head = next;
    }

    if (((len % 2) == 0) && (next == (len - 2) / 2)) {
        next = 2 * head + 1;
        if (!comp(*(first + next), *(first + head))) std::iter_swap(first + next, first + head);
    }
}

/*
static void MakeHeap(benchmark::State& state) {
  auto heap = make_vector_heap();
  const auto addition = state.range(0);
  for (auto _ : state) {
    heap[0] += addition;
    std::make_heap(heap.begin(), heap.end());
    if (!std::is_heap(heap.begin(), heap.end())) throw 42;
    benchmark::DoNotOptimize(heap);
  }
}
// Register the function as a benchmark
BENCHMARK(MakeHeap)->Range(kCount / kIntervals, kCount);
// */

static void PopPush(benchmark::State& state) {
  auto heap = make_vector_heap();
  const auto addition = state.range(0);
  for (auto _ : state) {
    heap[0] += addition;
    std::pop_heap(heap.begin(), heap.end());
    std::push_heap(heap.begin(), heap.end());
    if (!std::is_heap(heap.begin(), heap.end())) throw 42;
    benchmark::DoNotOptimize(heap);
  }
}
// Register the function as a benchmark
BENCHMARK(PopPush)->Range(kCount / kIntervals, kCount);

static void SiftDown(benchmark::State& state) {
  auto heap = make_vector_heap();
  const auto addition = state.range(0);
  for (auto _ : state) {
    heap[0] += addition;
    sift_down(heap.begin(), heap.end());
    if (!std::is_heap(heap.begin(), heap.end())) throw 42;
    benchmark::DoNotOptimize(heap);
  }
}
// Register the function as a benchmark
BENCHMARK(SiftDown)->Range(kCount / kIntervals, kCount);

Можно ли что-то соптимизировать?

[Roman-Koshelev]

К сожалению вы допустили серьезную ошибку. С std::is_heap хорошо прогнать один раз для проверки, но она только сильно портит результаты.

Прогнал у себя

gcc 9.3. stdlib=libstdc++

Дебаг сборка (-O0)

2021-04-11 13:29:57 Running ./a.out Run on (4 X 3000 MHz CPU s) CPU Caches: L1 Data 32K (x4) L1 Instruction 32K (x4) L2 Unified 256K (x4) L3 Unified 12288K (x4) Load Average: 0.55, 0.36, 0.32

Benchmark Time CPU Iterations

PopPush/1 725 ns 725 ns 935610 PopPush/8 717 ns 717 ns 958056 PopPush/64 718 ns 718 ns 948277 PopPush/512 720 ns 720 ns 922112 PopPush/4096 718 ns 718 ns 950095 PopPush/8192 720 ns 720 ns 938844 SiftDown/1 44.7 ns 44.6 ns 15657294 SiftDown/8 44.8 ns 44.8 ns 15647386 SiftDown/64 44.6 ns 44.6 ns 15587821 SiftDown/512 44.8 ns 44.7 ns 15629534 SiftDown/4096 45.1 ns 45.1 ns 14752498 SiftDown/8192 44.7 ns 44.6 ns 15405241

Релиз сборка (-O2) 2021-04-11 13:30:17 Running ./a.out Run on (4 X 3000 MHz CPU s) CPU Caches: L1 Data 32K (x4) L1 Instruction 32K (x4) L2 Unified 256K (x4) L3 Unified 12288K (x4) Load Average: 0.68, 0.40, 0.33

Benchmark Time CPU Iterations

PopPush/1 24.5 ns 24.5 ns 27903927 PopPush/8 24.9 ns 24.9 ns 28272596 PopPush/64 24.8 ns 24.8 ns 27600987 PopPush/512 24.5 ns 24.5 ns 28117353 PopPush/4096 24.5 ns 24.5 ns 28302327 PopPush/8192 25.5 ns 25.4 ns 28033435 SiftDown/1 2.24 ns 2.23 ns 308260079 SiftDown/8 2.21 ns 2.21 ns 315506332 SiftDown/64 2.20 ns 2.19 ns 316876814 SiftDown/512 2.19 ns 2.19 ns 315840977 SiftDown/4096 2.22 ns 2.22 ns 311711964 SiftDown/8192 2.21 ns 2.21 ns 315256111

Выигрыш на порядок

[apolukhin]

Да, результат получается великолепный https://quick-bench.com/q/NggXPvvYT947oplUbmyhLNQUobo

Попробуйте написать предложение для международного комитета по инструкции https://stdcpp.ru/instruction ? Если что - я помогу

Пара мелочей, которые надо учитывать:

• В C++20 добавили ranges, так что алгоритм должен быть продублирован и в ranges стиле тоже
• Остальные алгоритмы с кучами имеют _heap в названии. Стоит подумать на таким же именем, например update_heap или sift_down_heap
• на забудьте про constexpr :)

[Roman-Koshelev]

Внезапно во время придумывания std::heap наткнулся на давно забытый std::priority_queue. Он не только имеет ряд недостатков (методы не constexpr. Нет reserve метода. И тд), но и ужасное название. Думаю можно наверное сделать using heap = priority_queue прямо в std чтоб каждый не писал эту строчку сам.

TODO: Также продумать как новый std::update_heap ляжет на priority_queue

[toughengineer]

Я напилил свою версию, которая имхо проще в написании и понимании, а также слегка быстрее работает (https://quick-bench.com/q/eD-G0nkrHntqdLR0a0CXNj5VNJw):

template<typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>>
void sift_down(RandomIt begin, RandomIt end, const Compare &comp = {}) { // sift down element at 'begin'
  using std::swap;

  const auto length = static_cast<size_t>(end - begin);
  size_t current = 0;
  size_t next = 2;
  while (next < length) {
    if (comp(*(begin + next), *(begin + (next - 1))))
      --next;
    if (!comp(*(begin + current), *(begin + next)))
      return;
    swap(*(begin + current), *(begin + next));

    current = next;
    next = 2 * current + 2;
  }
  --next;
  if (next < length && comp(*(begin + current), *(begin + next)))
    swap(*(begin + current), *(begin + next));
}

Также, чтобы каждый разработчик на свете не писал каждый раз

if (value < *begin) {
  *begin = value;
  sift_down(begin, end);
}

наверное, было бы интересно иметь такую версию:

template<typename RandomIt, typename T, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>>
void sift_down(RandomIt begin, RandomIt end, T &&value, Compare comp = {});

которая могла бы использовать только move без swap, что должно работать несколько оптимальнее. Тогда можно было бы писать просто

sift_down(begin, end, value);