diff options
| author | cerevra <cerevra@yandex-team.ru> | 2022-02-10 16:45:59 +0300 |
|---|---|---|
| committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:59 +0300 |
| commit | 4f292c7e2fd0a41da93fda51b2d440c979a330b7 (patch) | |
| tree | 1a2c5ffcf89eb53ecd79dbc9bc0a195c27404d0c /library/cpp/containers/top_keeper | |
| parent | bf41dd01f6c920583e9faae7cd55ed25e547e052 (diff) | |
| download | ydb-4f292c7e2fd0a41da93fda51b2d440c979a330b7.tar.gz | |
Restoring authorship annotation for <cerevra@yandex-team.ru>. Commit 2 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 b5d3add816..f160fb1c01 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 2b0f67b214..f160fb1c01 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 61bc58ccb5..a938279025 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 58bc33c3a9..8553389e17 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 9609b71ea8..a938279025 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> |