200 000 объектов за 2 мс: как выбирать топ-K без полной сортировки

[andy_p]

std::nth_element ?

[arhip1986]

std::nth_element даёт топ-K неотсортированным за O(N) в среднем. GameBudget.Net даёт топ-K отсортированным за O(N log K) с SIMD-скорингом и групповыми квотами. Разные инструменты для разных задач. Если вам нужна только partition — nth_element подойдёт. Если нужна сортировка, групповые квоты и SIMD — GameBudget.Net. Ну и для .NET-проектов нативная C++ библиотека создаёт проблемы с P/Invoke и маршалингом.

[AngryEvilCookie]

Да какой восьмой дот нет, прекратите уже.

Ускорение, просто замечательно. С потреблением памяти что?

[jury-churkin]

Полный heap не будет лучше? Там выходит N+KlogN.

[arhip1986]

Теоретически полный heap даёт меньше сравнений (O(N + K log N) против O(N log K)). На практике при малых K (100–2000) и больших N (100k+) разница незначительна, а полный heap требует O(N) дополнительной памяти и часто копирования исходных данных. В наших бенчмарках разница ~0.1 мс, но память экономится в 100 раз. Для групповых квот с per-group heaps разница ещё меньше. SIMD dot, а не селекция, является узким местом — 70–80% времени. Поэтому выбрали более экономный по памяти и аллокациям подход.

[jury-churkin]

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