diff options
| author | cerevra <cerevra@yandex-team.ru> | 2022-02-10 16:45:58 +0300 |
|---|---|---|
| committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:58 +0300 |
| commit | bf41dd01f6c920583e9faae7cd55ed25e547e052 (patch) | |
| tree | ec7c8c285ffa648a5c5efeff453787a15ab811ac /library/cpp/containers/top_keeper | |
| parent | e2c3e3004f7cd68441cefcfa4aaccd3d8051c846 (diff) | |
| download | ydb-bf41dd01f6c920583e9faae7cd55ed25e547e052.tar.gz | |
Restoring authorship annotation for <cerevra@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/containers/top_keeper')
5 files changed, 7 insertions, 7 deletions
diff --git a/library/cpp/containers/top_keeper/README.md b/library/cpp/containers/top_keeper/README.md index f160fb1c01..b5d3add816 100644 --- a/library/cpp/containers/top_keeper/README.md +++ b/library/cpp/containers/top_keeper/README.md @@ -11,7 +11,7 @@ TopKeeper - структура данных для поддержания "top M 5) Удаляем элементы из правой половины Трудоёмкость: -На M добавлений происходит 1 PartitionSort (усреднённая оценка трудоёмкости - О(M)) и удаление M элементов. Таким образом достигается О(1) операций в среднем на 1 добавление. Для алгоритма TLimitedHeap (library/cpp/containers/limited_heap) - эта оценка О(log (M)) +На 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 выигрывает во много раз. diff --git a/library/cpp/containers/top_keeper/top_keeper/README.md b/library/cpp/containers/top_keeper/top_keeper/README.md index f160fb1c01..2b0f67b214 100644 --- a/library/cpp/containers/top_keeper/top_keeper/README.md +++ b/library/cpp/containers/top_keeper/top_keeper/README.md @@ -11,7 +11,7 @@ TopKeeper - структура данных для поддержания "top M 5) Удаляем элементы из правой половины Трудоёмкость: -На M добавлений происходит 1 PartitionSort (усреднённая оценка трудоёмкости - О(M)) и удаление M элементов. Таким образом достигается О(1) операций в среднем на 1 добавление. Для алгоритма TLimitedHeap (library/cpp/containers/limited_heap) - эта оценка О(log (M)) +На 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 выигрывает во много раз. @@ -23,4 +23,4 @@ TopKeeper - структура данных для поддержания "top M В ситуации когда нужны чередующиеся добавления / извлечения - используйте LimitedHeap Примеры использования: -library/cpp/containers/top_keeper/ut +library/cpp/containers/top_keeper/ut diff --git a/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp b/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp index a938279025..61bc58ccb5 100644 --- a/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp +++ b/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp @@ -1,5 +1,5 @@ -#include <library/cpp/containers/limited_heap/limited_heap.h> -#include <library/cpp/containers/top_keeper/top_keeper.h> +#include <library/cpp/containers/limited_heap/limited_heap.h> +#include <library/cpp/containers/top_keeper/top_keeper.h> #include <library/cpp/testing/unittest/registar.h> #include <util/random/random.h> diff --git a/library/cpp/containers/top_keeper/top_keeper/ut/ya.make b/library/cpp/containers/top_keeper/top_keeper/ut/ya.make index 8553389e17..58bc33c3a9 100644 --- a/library/cpp/containers/top_keeper/top_keeper/ut/ya.make +++ b/library/cpp/containers/top_keeper/top_keeper/ut/ya.make @@ -1,4 +1,4 @@ -UNITTEST_FOR(library/cpp/containers/top_keeper) +UNITTEST_FOR(library/cpp/containers/top_keeper) OWNER( mbusel diff --git a/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp b/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp index a938279025..9609b71ea8 100644 --- a/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp +++ b/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp @@ -1,4 +1,4 @@ -#include <library/cpp/containers/limited_heap/limited_heap.h> +#include <library/cpp/containers/limited_heap/limited_heap.h> #include <library/cpp/containers/top_keeper/top_keeper.h> #include <library/cpp/testing/unittest/registar.h> #include <util/random/random.h> |