ydb/library/cpp/containers/top_keeper

TopKeeper - структура данных для поддержания "top M from stream" Используется для выборки наибольших / наименьших элементов за один проход (полезно при фильтрации)

Пусть входной поток состоит из N элементов, из которых нужно отфильтровать M с наибольшим значением. Алгоритм (для случая top max M): 1) Выделим вектор размера 2 * M 2а) Если вектор заполнен меньше, чем наполовину - добавляем очередной элемент, обновляем минимум 2б) Иначе - сравниваем с текущим минимумом, в случае, если новый больше, добавляем его в вектор, минимум не обновляем, иначе - отбрасываем 3) Если заполнен - делаем Partition Sort с M-ым элементом в качестве сепаратора 4) Таким образом в левой половине все значения больше оных в правой, в позиции M стоит ровно M-ый элемент сортированной последовательности 5) Удаляем элементы из правой половины

Трудоёмкость: На M добавлений происходит 1 PartitionSort (усреднённая оценка трудоёмкости - О(M)) и удаление M элементов. Таким образом достигается О(1) операций в среднем на 1 добавление. Для алгоритма TLimitedHeap (library/cpp/containers/limited_heap) - эта оценка О(log (M))

Тесты: На случайных потоках данных количество сравнений у TopKeeper и LimitedHeap одинаково (происходит потому что минимум у первого обновляется раз в M добавлений, а у второго - при каждом добавлении). Худший случай LimitedHeap - сортированная последовательность (добавляем каждый элемент), на таком потоке для 2 000 000 000 int TopKeeper выигрывает во много раз.

Границы применимости: Применять стоит всегда вместо LimitedHeap (т.к. всегда не хуже, а в худшем случае - лучше) Ограничение - не поддерживает сценарий использования "чередующиеся добавления / извлечения элементов" (слишком часто будут происходить Partiotion Sortы) Для этого, когда добавление элементов закончено, должен вызываться метод Finalize(). Для упрощения использования добавлен автоматический Finalize() на GetNext() / Pop(). Тем не менее явный вызов Finalize() по-прежнему возможен - так можно контролировать момент выполнения трудоёмкой операции NthElement(). После того, как все элементы извлечены TopKeeper можно переиспользовать (для этого же служит метод Reset()). В ситуации когда нужны чередующиеся добавления / извлечения - используйте LimitedHeap

Примеры использования: library/cpp/containers/top_keeper/ut