diff options
author | mbusel <mbusel@yandex-team.ru> | 2022-02-10 16:50:40 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:50:40 +0300 |
commit | a2054d07ad4a576bce8d64ecf9772db9927a475a (patch) | |
tree | 68a0ffa6c4b81d93f577e89aa85c0289173c63bf | |
parent | ab94ebd77c48b8060e47b5d56c3d715ddaaab5e5 (diff) | |
download | ydb-a2054d07ad4a576bce8d64ecf9772db9927a475a.tar.gz |
Restoring authorship annotation for <mbusel@yandex-team.ru>. Commit 1 of 2.
-rw-r--r-- | library/cpp/containers/top_keeper/README.md | 48 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/top_keeper.cpp | 2 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/top_keeper.h | 232 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/top_keeper/README.md | 48 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp | 2 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/top_keeper/top_keeper.h | 232 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp | 274 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/top_keeper/ut/ya.make | 22 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/top_keeper/ya.make | 18 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp | 274 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/ut/ya.make | 20 | ||||
-rw-r--r-- | library/cpp/containers/top_keeper/ya.make | 16 |
12 files changed, 594 insertions, 594 deletions
diff --git a/library/cpp/containers/top_keeper/README.md b/library/cpp/containers/top_keeper/README.md index f160fb1c01..d38299039e 100644 --- a/library/cpp/containers/top_keeper/README.md +++ b/library/cpp/containers/top_keeper/README.md @@ -1,26 +1,26 @@ -TopKeeper - структура данных для поддержания "top M from stream" -Используется для выборки наибольших / наименьших элементов за один проход (полезно при фильтрации) - -Пусть входной поток состоит из N элементов, из которых нужно отфильтровать M с наибольшим значением. -Алгоритм (для случая top max M): -1) Выделим вектор размера 2 * M -2а) Если вектор заполнен меньше, чем наполовину - добавляем очередной элемент, обновляем минимум -2б) Иначе - сравниваем с текущим минимумом, в случае, если новый больше, добавляем его в вектор, минимум не обновляем, иначе - отбрасываем -3) Если заполнен - делаем Partition Sort с M-ым элементом в качестве сепаратора -4) Таким образом в левой половине все значения больше оных в правой, в позиции M стоит ровно M-ый элемент сортированной последовательности -5) Удаляем элементы из правой половины - -Трудоёмкость: +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 - -Примеры использования: + +Тесты: +На случайных потоках данных количество сравнений у 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 diff --git a/library/cpp/containers/top_keeper/top_keeper.cpp b/library/cpp/containers/top_keeper/top_keeper.cpp index 29544bf227..56784271e5 100644 --- a/library/cpp/containers/top_keeper/top_keeper.cpp +++ b/library/cpp/containers/top_keeper/top_keeper.cpp @@ -1 +1 @@ -#include "top_keeper.h" +#include "top_keeper.h" diff --git a/library/cpp/containers/top_keeper/top_keeper.h b/library/cpp/containers/top_keeper/top_keeper.h index 2f282b5a9e..3ac2f41860 100644 --- a/library/cpp/containers/top_keeper/top_keeper.h +++ b/library/cpp/containers/top_keeper/top_keeper.h @@ -1,25 +1,25 @@ -#pragma once - -#include <util/generic/vector.h> -#include <util/generic/algorithm.h> -#include <util/generic/maybe.h> -#include <util/str_stl.h> - +#pragma once + +#include <util/generic/vector.h> +#include <util/generic/algorithm.h> +#include <util/generic/maybe.h> +#include <util/str_stl.h> + template <class T, class TComparator = TGreater<T>, bool sort = true, class Alloc = std::allocator<T>> -class TTopKeeper { -private: - class TVectorWithMin { - private: +class TTopKeeper { +private: + class TVectorWithMin { + private: TVector<T, Alloc> Internal; - size_t HalfMaxSize; - TComparator Comparer; + size_t HalfMaxSize; + TComparator Comparer; size_t MinElementIndex; - private: + private: void Reserve() { Internal.reserve(2 * HalfMaxSize); } - + template <class UT> bool Insert(UT&& value) noexcept { if (Y_UNLIKELY(0 == HalfMaxSize)) { @@ -45,16 +45,16 @@ private: return true; } - public: + public: using value_type = T; - TVectorWithMin(const size_t halfMaxSize, const TComparator& comp) - : HalfMaxSize(halfMaxSize) - , Comparer(comp) - { + TVectorWithMin(const size_t halfMaxSize, const TComparator& comp) + : HalfMaxSize(halfMaxSize) + , Comparer(comp) + { Reserve(); - } - + } + template <class TAllocParam> TVectorWithMin(const size_t halfMaxSize, const TComparator& comp, TAllocParam&& param) : Internal(std::forward<TAllocParam>(param)) @@ -64,27 +64,27 @@ private: Reserve(); } - void SortAccending() { - Sort(Internal.begin(), Internal.end(), Comparer); - } - - void Partition() { + void SortAccending() { + Sort(Internal.begin(), Internal.end(), Comparer); + } + + void Partition() { if (Y_UNLIKELY(HalfMaxSize == 0)) { return; } if (Y_LIKELY(Internal.size() >= HalfMaxSize)) { NthElement(Internal.begin(), Internal.begin() + HalfMaxSize - 1, Internal.end(), Comparer); - Internal.erase(Internal.begin() + HalfMaxSize, Internal.end()); + Internal.erase(Internal.begin() + HalfMaxSize, Internal.end()); //we should update MinElementIndex cause we just altered Internal MinElementIndex = HalfMaxSize - 1; - } - } - + } + } + bool Push(const T& value) { return Insert(value); } - + bool Push(T&& value) { return Insert(std::move(value)); } @@ -92,18 +92,18 @@ private: template <class... TArgs> bool Emplace(TArgs&&... args) { return Insert(T(std::forward<TArgs>(args)...)); // TODO: make it "real" emplace, not that fake one - } - - void SetMaxSize(size_t newHalfMaxSize) { - HalfMaxSize = newHalfMaxSize; + } + + void SetMaxSize(size_t newHalfMaxSize) { + HalfMaxSize = newHalfMaxSize; Reserve(); - Partition(); - } - - size_t GetSize() const { - return Internal.size(); - } - + Partition(); + } + + size_t GetSize() const { + return Internal.size(); + } + const auto& GetInternal() const { return Internal; } @@ -117,31 +117,31 @@ private: return values; } - const T& Back() const { - return Internal.back(); - } - - void Pop() { - Internal.pop_back(); - } - - void Reset() { - Internal.clear(); + const T& Back() const { + return Internal.back(); + } + + void Pop() { + Internal.pop_back(); + } + + void Reset() { + Internal.clear(); //MinElementIndex will reset itself when we start adding new values - } - }; - + } + }; + void CheckNotFinalized() { Y_ENSURE(!Finalized, "Cannot insert after finalizing (Pop() / GetNext() / Finalize())! " "Use TLimitedHeap for this scenario"); } - size_t MaxSize; + size_t MaxSize; const TComparator Comparer; - TVectorWithMin Internal; - bool Finalized; - -public: + TVectorWithMin Internal; + bool Finalized; + +public: TTopKeeper() : MaxSize(0) , Comparer() @@ -150,14 +150,14 @@ public: { } - TTopKeeper(size_t maxSize, const TComparator& comp = TComparator()) - : MaxSize(maxSize) - , Comparer(comp) - , Internal(maxSize, comp) - , Finalized(false) - { - } - + TTopKeeper(size_t maxSize, const TComparator& comp = TComparator()) + : MaxSize(maxSize) + , Comparer(comp) + , Internal(maxSize, comp) + , Finalized(false) + { + } + template <class TAllocParam> TTopKeeper(size_t maxSize, const TComparator& comp, TAllocParam&& param) : MaxSize(maxSize) @@ -167,32 +167,32 @@ public: { } - void Finalize() { + void Finalize() { if (Y_LIKELY(Finalized)) { - return; - } - Internal.Partition(); - if (sort) { - Internal.SortAccending(); - } - Finalized = true; - } - - const T& GetNext() { + return; + } + Internal.Partition(); + if (sort) { + Internal.SortAccending(); + } + Finalized = true; + } + + const T& GetNext() { Y_ENSURE(!IsEmpty(), "Trying GetNext from empty heap!"); - Finalize(); - return Internal.Back(); - } - - void Pop() { + Finalize(); + return Internal.Back(); + } + + void Pop() { Y_ENSURE(!IsEmpty(), "Trying Pop from empty heap!"); - Finalize(); - Internal.Pop(); - if (IsEmpty()) { - Reset(); - } - } - + Finalize(); + Internal.Pop(); + if (IsEmpty()) { + Reset(); + } + } + T ExtractOne() { Y_ENSURE(!IsEmpty(), "Trying ExtractOne from empty heap!"); Finalize(); @@ -212,8 +212,8 @@ public: bool Insert(const T& value) { CheckNotFinalized(); return Internal.Push(value); - } - + } + bool Insert(T&& value) { CheckNotFinalized(); return Internal.Push(std::move(value)); @@ -230,27 +230,27 @@ public: return Internal.GetInternal(); } - bool IsEmpty() const { - return Internal.GetSize() == 0; - } - - size_t GetSize() const { - return Min(Internal.GetSize(), MaxSize); - } - - size_t GetMaxSize() const { - return MaxSize; - } - - void SetMaxSize(size_t newMaxSize) { + bool IsEmpty() const { + return Internal.GetSize() == 0; + } + + size_t GetSize() const { + return Min(Internal.GetSize(), MaxSize); + } + + size_t GetMaxSize() const { + return MaxSize; + } + + void SetMaxSize(size_t newMaxSize) { Y_ENSURE(!Finalized, "Cannot resize after finalizing (Pop() / GetNext() / Finalize())! " "Use TLimitedHeap for this scenario"); - MaxSize = newMaxSize; - Internal.SetMaxSize(newMaxSize); - } - - void Reset() { - Internal.Reset(); - Finalized = false; - } -}; + MaxSize = newMaxSize; + Internal.SetMaxSize(newMaxSize); + } + + void Reset() { + Internal.Reset(); + Finalized = false; + } +}; diff --git a/library/cpp/containers/top_keeper/top_keeper/README.md b/library/cpp/containers/top_keeper/top_keeper/README.md index f160fb1c01..d38299039e 100644 --- a/library/cpp/containers/top_keeper/top_keeper/README.md +++ b/library/cpp/containers/top_keeper/top_keeper/README.md @@ -1,26 +1,26 @@ -TopKeeper - структура данных для поддержания "top M from stream" -Используется для выборки наибольших / наименьших элементов за один проход (полезно при фильтрации) - -Пусть входной поток состоит из N элементов, из которых нужно отфильтровать M с наибольшим значением. -Алгоритм (для случая top max M): -1) Выделим вектор размера 2 * M -2а) Если вектор заполнен меньше, чем наполовину - добавляем очередной элемент, обновляем минимум -2б) Иначе - сравниваем с текущим минимумом, в случае, если новый больше, добавляем его в вектор, минимум не обновляем, иначе - отбрасываем -3) Если заполнен - делаем Partition Sort с M-ым элементом в качестве сепаратора -4) Таким образом в левой половине все значения больше оных в правой, в позиции M стоит ровно M-ый элемент сортированной последовательности -5) Удаляем элементы из правой половины - -Трудоёмкость: +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 - -Примеры использования: + +Тесты: +На случайных потоках данных количество сравнений у 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 diff --git a/library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp b/library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp index 29544bf227..56784271e5 100644 --- a/library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp +++ b/library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp @@ -1 +1 @@ -#include "top_keeper.h" +#include "top_keeper.h" diff --git a/library/cpp/containers/top_keeper/top_keeper/top_keeper.h b/library/cpp/containers/top_keeper/top_keeper/top_keeper.h index 2f282b5a9e..3ac2f41860 100644 --- a/library/cpp/containers/top_keeper/top_keeper/top_keeper.h +++ b/library/cpp/containers/top_keeper/top_keeper/top_keeper.h @@ -1,25 +1,25 @@ -#pragma once - -#include <util/generic/vector.h> -#include <util/generic/algorithm.h> -#include <util/generic/maybe.h> -#include <util/str_stl.h> - +#pragma once + +#include <util/generic/vector.h> +#include <util/generic/algorithm.h> +#include <util/generic/maybe.h> +#include <util/str_stl.h> + template <class T, class TComparator = TGreater<T>, bool sort = true, class Alloc = std::allocator<T>> -class TTopKeeper { -private: - class TVectorWithMin { - private: +class TTopKeeper { +private: + class TVectorWithMin { + private: TVector<T, Alloc> Internal; - size_t HalfMaxSize; - TComparator Comparer; + size_t HalfMaxSize; + TComparator Comparer; size_t MinElementIndex; - private: + private: void Reserve() { Internal.reserve(2 * HalfMaxSize); } - + template <class UT> bool Insert(UT&& value) noexcept { if (Y_UNLIKELY(0 == HalfMaxSize)) { @@ -45,16 +45,16 @@ private: return true; } - public: + public: using value_type = T; - TVectorWithMin(const size_t halfMaxSize, const TComparator& comp) - : HalfMaxSize(halfMaxSize) - , Comparer(comp) - { + TVectorWithMin(const size_t halfMaxSize, const TComparator& comp) + : HalfMaxSize(halfMaxSize) + , Comparer(comp) + { Reserve(); - } - + } + template <class TAllocParam> TVectorWithMin(const size_t halfMaxSize, const TComparator& comp, TAllocParam&& param) : Internal(std::forward<TAllocParam>(param)) @@ -64,27 +64,27 @@ private: Reserve(); } - void SortAccending() { - Sort(Internal.begin(), Internal.end(), Comparer); - } - - void Partition() { + void SortAccending() { + Sort(Internal.begin(), Internal.end(), Comparer); + } + + void Partition() { if (Y_UNLIKELY(HalfMaxSize == 0)) { return; } if (Y_LIKELY(Internal.size() >= HalfMaxSize)) { NthElement(Internal.begin(), Internal.begin() + HalfMaxSize - 1, Internal.end(), Comparer); - Internal.erase(Internal.begin() + HalfMaxSize, Internal.end()); + Internal.erase(Internal.begin() + HalfMaxSize, Internal.end()); //we should update MinElementIndex cause we just altered Internal MinElementIndex = HalfMaxSize - 1; - } - } - + } + } + bool Push(const T& value) { return Insert(value); } - + bool Push(T&& value) { return Insert(std::move(value)); } @@ -92,18 +92,18 @@ private: template <class... TArgs> bool Emplace(TArgs&&... args) { return Insert(T(std::forward<TArgs>(args)...)); // TODO: make it "real" emplace, not that fake one - } - - void SetMaxSize(size_t newHalfMaxSize) { - HalfMaxSize = newHalfMaxSize; + } + + void SetMaxSize(size_t newHalfMaxSize) { + HalfMaxSize = newHalfMaxSize; Reserve(); - Partition(); - } - - size_t GetSize() const { - return Internal.size(); - } - + Partition(); + } + + size_t GetSize() const { + return Internal.size(); + } + const auto& GetInternal() const { return Internal; } @@ -117,31 +117,31 @@ private: return values; } - const T& Back() const { - return Internal.back(); - } - - void Pop() { - Internal.pop_back(); - } - - void Reset() { - Internal.clear(); + const T& Back() const { + return Internal.back(); + } + + void Pop() { + Internal.pop_back(); + } + + void Reset() { + Internal.clear(); //MinElementIndex will reset itself when we start adding new values - } - }; - + } + }; + void CheckNotFinalized() { Y_ENSURE(!Finalized, "Cannot insert after finalizing (Pop() / GetNext() / Finalize())! " "Use TLimitedHeap for this scenario"); } - size_t MaxSize; + size_t MaxSize; const TComparator Comparer; - TVectorWithMin Internal; - bool Finalized; - -public: + TVectorWithMin Internal; + bool Finalized; + +public: TTopKeeper() : MaxSize(0) , Comparer() @@ -150,14 +150,14 @@ public: { } - TTopKeeper(size_t maxSize, const TComparator& comp = TComparator()) - : MaxSize(maxSize) - , Comparer(comp) - , Internal(maxSize, comp) - , Finalized(false) - { - } - + TTopKeeper(size_t maxSize, const TComparator& comp = TComparator()) + : MaxSize(maxSize) + , Comparer(comp) + , Internal(maxSize, comp) + , Finalized(false) + { + } + template <class TAllocParam> TTopKeeper(size_t maxSize, const TComparator& comp, TAllocParam&& param) : MaxSize(maxSize) @@ -167,32 +167,32 @@ public: { } - void Finalize() { + void Finalize() { if (Y_LIKELY(Finalized)) { - return; - } - Internal.Partition(); - if (sort) { - Internal.SortAccending(); - } - Finalized = true; - } - - const T& GetNext() { + return; + } + Internal.Partition(); + if (sort) { + Internal.SortAccending(); + } + Finalized = true; + } + + const T& GetNext() { Y_ENSURE(!IsEmpty(), "Trying GetNext from empty heap!"); - Finalize(); - return Internal.Back(); - } - - void Pop() { + Finalize(); + return Internal.Back(); + } + + void Pop() { Y_ENSURE(!IsEmpty(), "Trying Pop from empty heap!"); - Finalize(); - Internal.Pop(); - if (IsEmpty()) { - Reset(); - } - } - + Finalize(); + Internal.Pop(); + if (IsEmpty()) { + Reset(); + } + } + T ExtractOne() { Y_ENSURE(!IsEmpty(), "Trying ExtractOne from empty heap!"); Finalize(); @@ -212,8 +212,8 @@ public: bool Insert(const T& value) { CheckNotFinalized(); return Internal.Push(value); - } - + } + bool Insert(T&& value) { CheckNotFinalized(); return Internal.Push(std::move(value)); @@ -230,27 +230,27 @@ public: return Internal.GetInternal(); } - bool IsEmpty() const { - return Internal.GetSize() == 0; - } - - size_t GetSize() const { - return Min(Internal.GetSize(), MaxSize); - } - - size_t GetMaxSize() const { - return MaxSize; - } - - void SetMaxSize(size_t newMaxSize) { + bool IsEmpty() const { + return Internal.GetSize() == 0; + } + + size_t GetSize() const { + return Min(Internal.GetSize(), MaxSize); + } + + size_t GetMaxSize() const { + return MaxSize; + } + + void SetMaxSize(size_t newMaxSize) { Y_ENSURE(!Finalized, "Cannot resize after finalizing (Pop() / GetNext() / Finalize())! " "Use TLimitedHeap for this scenario"); - MaxSize = newMaxSize; - Internal.SetMaxSize(newMaxSize); - } - - void Reset() { - Internal.Reset(); - Finalized = false; - } -}; + MaxSize = newMaxSize; + Internal.SetMaxSize(newMaxSize); + } + + void Reset() { + Internal.Reset(); + Finalized = false; + } +}; 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..55a27828a3 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 @@ -2,43 +2,43 @@ #include <library/cpp/containers/top_keeper/top_keeper.h> #include <library/cpp/testing/unittest/registar.h> #include <util/random/random.h> - -static ui32 seed = 3; -ui32 Rnd() { - seed = seed * 5 + 1; - return seed; -} - -/* - * Tests for TTopKeeper - */ + +static ui32 seed = 3; +ui32 Rnd() { + seed = seed * 5 + 1; + return seed; +} + +/* + * Tests for TTopKeeper + */ Y_UNIT_TEST_SUITE(TTopKeeperTest) { - // Tests correctness on usual examples + // Tests correctness on usual examples Y_UNIT_TEST(CorrectnessTest) { - int m = 20000; - + int m = 20000; + TLimitedHeap<std::pair<int, int>> h1(m); TTopKeeper<std::pair<int, int>> h2(m); - int n = 20000000; - while (n--) { - int r = int(Rnd()); - + int n = 20000000; + while (n--) { + int r = int(Rnd()); + h1.Insert({r, -r}); h2.Emplace(r, -r); - } - - h2.Finalize(); - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - } - + } + + h2.Finalize(); + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + } + // Tests on zero-size correctness Y_UNIT_TEST(ZeroSizeCorrectnes) { TTopKeeper<int> h(0); @@ -49,115 +49,115 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { UNIT_ASSERT(h.IsEmpty()); } - // Tests SetMaxSize behaviour + // Tests SetMaxSize behaviour Y_UNIT_TEST(SetMaxSizeTest) { - int m = 20000; - TLimitedHeap<int> h1(m); - TTopKeeper<int> h2(m); - - int n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - h1.SetMaxSize(m / 3); - h2.SetMaxSize(m / 3); - h2.Finalize(); - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - } - - // Tests reuse behavior + int m = 20000; + TLimitedHeap<int> h1(m); + TTopKeeper<int> h2(m); + + int n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + h1.SetMaxSize(m / 3); + h2.SetMaxSize(m / 3); + h2.Finalize(); + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + } + + // Tests reuse behavior Y_UNIT_TEST(ReuseTest) { - int m = 20000; - TLimitedHeap<int> h1(m); - TTopKeeper<int> h2(m); - - int n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - - n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - } - - // Tests reset behavior + int m = 20000; + TLimitedHeap<int> h1(m); + TTopKeeper<int> h2(m); + + int n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + + n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + } + + // Tests reset behavior Y_UNIT_TEST(ResetTest) { - int m = 20000; - TLimitedHeap<int> h1(m); - TTopKeeper<int> h2(m); - - int n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - for (int i = 0; i < m / 2; ++i) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - - h2.Reset(); - while (!h1.IsEmpty()) { - h1.PopMin(); - } - - n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - } + int m = 20000; + TLimitedHeap<int> h1(m); + TTopKeeper<int> h2(m); + + int n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + for (int i = 0; i < m / 2; ++i) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + + h2.Reset(); + while (!h1.IsEmpty()) { + h1.PopMin(); + } + + n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + } Y_UNIT_TEST(PreRegressionTest) { typedef std::pair<float, unsigned int> TElementType; @@ -219,4 +219,4 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { UNIT_ASSERT(keeper.IsEmpty()); } -} +} 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..772c3cd774 100644 --- a/library/cpp/containers/top_keeper/top_keeper/ut/ya.make +++ b/library/cpp/containers/top_keeper/top_keeper/ut/ya.make @@ -1,12 +1,12 @@ UNITTEST_FOR(library/cpp/containers/top_keeper) - -OWNER( - mbusel - rmplstiltskin -) - -SRCS( - top_keeper_ut.cpp -) - -END() + +OWNER( + mbusel + rmplstiltskin +) + +SRCS( + top_keeper_ut.cpp +) + +END() diff --git a/library/cpp/containers/top_keeper/top_keeper/ya.make b/library/cpp/containers/top_keeper/top_keeper/ya.make index 79be94ae2b..cb2bd8fa15 100644 --- a/library/cpp/containers/top_keeper/top_keeper/ya.make +++ b/library/cpp/containers/top_keeper/top_keeper/ya.make @@ -1,9 +1,9 @@ -LIBRARY() - -OWNER(mbusel) - -SRCS( - top_keeper.cpp -) - -END() +LIBRARY() + +OWNER(mbusel) + +SRCS( + top_keeper.cpp +) + +END() 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..55a27828a3 100644 --- a/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp +++ b/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp @@ -2,43 +2,43 @@ #include <library/cpp/containers/top_keeper/top_keeper.h> #include <library/cpp/testing/unittest/registar.h> #include <util/random/random.h> - -static ui32 seed = 3; -ui32 Rnd() { - seed = seed * 5 + 1; - return seed; -} - -/* - * Tests for TTopKeeper - */ + +static ui32 seed = 3; +ui32 Rnd() { + seed = seed * 5 + 1; + return seed; +} + +/* + * Tests for TTopKeeper + */ Y_UNIT_TEST_SUITE(TTopKeeperTest) { - // Tests correctness on usual examples + // Tests correctness on usual examples Y_UNIT_TEST(CorrectnessTest) { - int m = 20000; - + int m = 20000; + TLimitedHeap<std::pair<int, int>> h1(m); TTopKeeper<std::pair<int, int>> h2(m); - int n = 20000000; - while (n--) { - int r = int(Rnd()); - + int n = 20000000; + while (n--) { + int r = int(Rnd()); + h1.Insert({r, -r}); h2.Emplace(r, -r); - } - - h2.Finalize(); - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - } - + } + + h2.Finalize(); + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + } + // Tests on zero-size correctness Y_UNIT_TEST(ZeroSizeCorrectnes) { TTopKeeper<int> h(0); @@ -49,115 +49,115 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { UNIT_ASSERT(h.IsEmpty()); } - // Tests SetMaxSize behaviour + // Tests SetMaxSize behaviour Y_UNIT_TEST(SetMaxSizeTest) { - int m = 20000; - TLimitedHeap<int> h1(m); - TTopKeeper<int> h2(m); - - int n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - h1.SetMaxSize(m / 3); - h2.SetMaxSize(m / 3); - h2.Finalize(); - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - } - - // Tests reuse behavior + int m = 20000; + TLimitedHeap<int> h1(m); + TTopKeeper<int> h2(m); + + int n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + h1.SetMaxSize(m / 3); + h2.SetMaxSize(m / 3); + h2.Finalize(); + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + } + + // Tests reuse behavior Y_UNIT_TEST(ReuseTest) { - int m = 20000; - TLimitedHeap<int> h1(m); - TTopKeeper<int> h2(m); - - int n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - - n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - } - - // Tests reset behavior + int m = 20000; + TLimitedHeap<int> h1(m); + TTopKeeper<int> h2(m); + + int n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + + n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + } + + // Tests reset behavior Y_UNIT_TEST(ResetTest) { - int m = 20000; - TLimitedHeap<int> h1(m); - TTopKeeper<int> h2(m); - - int n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - for (int i = 0; i < m / 2; ++i) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - - h2.Reset(); - while (!h1.IsEmpty()) { - h1.PopMin(); - } - - n = 20000000; - while (n--) { - int r = int(Rnd()); - - h1.Insert(r); - h2.Insert(r); - } - - UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); - - while (!h1.IsEmpty()) { - UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); - h1.PopMin(); - h2.Pop(); - } - } + int m = 20000; + TLimitedHeap<int> h1(m); + TTopKeeper<int> h2(m); + + int n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + for (int i = 0; i < m / 2; ++i) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + + h2.Reset(); + while (!h1.IsEmpty()) { + h1.PopMin(); + } + + n = 20000000; + while (n--) { + int r = int(Rnd()); + + h1.Insert(r); + h2.Insert(r); + } + + UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize()); + + while (!h1.IsEmpty()) { + UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext()); + h1.PopMin(); + h2.Pop(); + } + } Y_UNIT_TEST(PreRegressionTest) { typedef std::pair<float, unsigned int> TElementType; @@ -219,4 +219,4 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { UNIT_ASSERT(keeper.IsEmpty()); } -} +} diff --git a/library/cpp/containers/top_keeper/ut/ya.make b/library/cpp/containers/top_keeper/ut/ya.make index 42cfdd6f13..0a3b150844 100644 --- a/library/cpp/containers/top_keeper/ut/ya.make +++ b/library/cpp/containers/top_keeper/ut/ya.make @@ -1,12 +1,12 @@ UNITTEST_FOR(library/cpp/containers/top_keeper) - -OWNER( + +OWNER( ilnurkh - rmplstiltskin -) - -SRCS( - top_keeper_ut.cpp -) - -END() + rmplstiltskin +) + +SRCS( + top_keeper_ut.cpp +) + +END() diff --git a/library/cpp/containers/top_keeper/ya.make b/library/cpp/containers/top_keeper/ya.make index ed206a1df9..163ddccf0a 100644 --- a/library/cpp/containers/top_keeper/ya.make +++ b/library/cpp/containers/top_keeper/ya.make @@ -1,12 +1,12 @@ -LIBRARY() - +LIBRARY() + OWNER(ilnurkh) - -SRCS( - top_keeper.cpp -) - -END() + +SRCS( + top_keeper.cpp +) + +END() RECURSE_FOR_TESTS(ut) |