1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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
|
