Loser story

Недавно листал коммиты в одном интересном мне проекте и заметил любопытную идею, которая мне раньше не приходила в голову

https://github.com/quickwit-oss/tantivy/commit/b525f653c09726c9f97d35ee15aea1d557bce4f2

В общем все просто, давайте для онлайн partial_sort-а большой последовательности (набора top k лучших из онлайн последовательности), вместо бинарной кучи (топ -- последний) использовать такой подход:

1. Достанем k * 2 элементов
2. Выкинем k последних с помощью nth_element
3. Достанем ещё k
Повторим начиная с шага 2
В конце посортируем то что осталось

Ещё часто помимо limit есть offset, в таких случаях k = offset + limit.
В конце же можно оптимизировать (что важно для большого offset) и использовать не
1. nth_element(offset + limit)
2. erase_tail
3. sort
4. erase_tail
а
1. nth_element(offset + limit)
2. erase_tail
3. nth_element(limit, opposite_cmp)
4. erase_tail
5. sort

Еще прикольно, что в отличие от кучи, где с практической точки зрения алгоритмы не продвинулись дальше чем выбор между оптимистичным и пессимистичным пушем в бинарную кучу, для селекта-к/сортировки есть алгоритмы быстрее чем в стандартной библиотеке

www.tgoop.com/reverse13/719

1.6K viewsedited  Dec 17, 2023 at 18:21

Недавно листал коммиты в одном интересном мне проекте и заметил любопытную идею, которая мне раньше не приходила в голову

https://github.com/quickwit-oss/tantivy/commit/b525f653c09726c9f97d35ee15aea1d557bce4f2

В общем все просто, давайте для онлайн partial_sort-а большой последовательности (набора top k лучших из онлайн последовательности), вместо бинарной кучи (топ -- последний) использовать такой подход:

1. Достанем k * 2 элементов
2. Выкинем k последних с помощью nth_element
3. Достанем ещё k
Повторим начиная с шага 2
В конце посортируем то что осталось

Ещё часто помимо limit есть offset, в таких случаях k = offset + limit.
В конце же можно оптимизировать (что важно для большого offset) и использовать не
1. nth_element(offset + limit)
2. erase_tail
3. sort
4. erase_tail
а
1. nth_element(offset + limit)
2. erase_tail
3. nth_element(limit, opposite_cmp)
4. erase_tail
5. sort

Еще прикольно, что в отличие от кучи, где с практической точки зрения алгоритмы не продвинулись дальше чем выбор между оптимистичным и пессимистичным пушем в бинарную кучу, для селекта-к/сортировки есть алгоритмы быстрее чем в стандартной библиотеке

BY Loser story