aboutsummaryrefslogtreecommitdiffstats
path: root/library/cpp/containers/top_keeper
diff options
context:
space:
mode:
authormbusel <mbusel@yandex-team.ru>2022-02-10 16:50:40 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:50:40 +0300
commitfb1804b03a8b3964304c3233eba4e7c072b60f18 (patch)
tree5d5cb817648f650d76cf1076100726fd9b8448e8 /library/cpp/containers/top_keeper
parenta2054d07ad4a576bce8d64ecf9772db9927a475a (diff)
downloadydb-fb1804b03a8b3964304c3233eba4e7c072b60f18.tar.gz
Restoring authorship annotation for <mbusel@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'library/cpp/containers/top_keeper')
-rw-r--r--library/cpp/containers/top_keeper/README.md48
-rw-r--r--library/cpp/containers/top_keeper/top_keeper.cpp2
-rw-r--r--library/cpp/containers/top_keeper/top_keeper.h232
-rw-r--r--library/cpp/containers/top_keeper/top_keeper/README.md48
-rw-r--r--library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp2
-rw-r--r--library/cpp/containers/top_keeper/top_keeper/top_keeper.h232
-rw-r--r--library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp274
-rw-r--r--library/cpp/containers/top_keeper/top_keeper/ut/ya.make22
-rw-r--r--library/cpp/containers/top_keeper/top_keeper/ya.make18
-rw-r--r--library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp274
-rw-r--r--library/cpp/containers/top_keeper/ut/ya.make20
-rw-r--r--library/cpp/containers/top_keeper/ya.make16
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 d38299039e..f160fb1c01 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 56784271e5..29544bf227 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 3ac2f41860..2f282b5a9e 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 d38299039e..f160fb1c01 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 56784271e5..29544bf227 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 3ac2f41860..2f282b5a9e 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 55a27828a3..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
@@ -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 772c3cd774..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,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 cb2bd8fa15..79be94ae2b 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 55a27828a3..a938279025 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 0a3b150844..42cfdd6f13 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 163ddccf0a..ed206a1df9 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)