Оглавление
Как я начал эту затею
Что такое биномиальная куча?
Как я тестировал свои решения
Решение с помощью map в c++
Первая реализация комом
Реализация без протечки
Новые тесты
Что касается сравнения по тестам в итоге: реальная скорость и память
В чём же плохо моё решение? Вставка же быстрее и все дела
Пожелания от читателей
Как я начал эту затею
Я сейчас изучаю продвинутые структуры данных и в один прекрасный вечер я решил собирать алгоритмы и структуры данных к себе на гитхаб (и до сих пор это делаю). Захотел я сделать так, чтобы сделать всё шаблонным, если что-то мне резко понадобится, то я смог за считанные секунды добавить себе шаблонный класс структуры данных или шаблонную функцию алгоритма и использовать. Звучит замечательно, особенно на контесты с codeforces.
Я столкнулся с проблемами и решил здесь поделиться опытом с тем, кто также, как и я, мало знаком с пром. прогой и до этого в основном увлекался олимпиадным программированием.
Что такое биномиальная куча?
Об этом уже ни раз рассказывали, например на сайте ИТМО, здесь и ещё в прекрасных лекциях от Маврина Павла Юрьевича (посмотрите его видео, оно очень крутое!).
Если коротко, то биномиальная куча - структура данных, которая является деревом, реализующая интерфейс очереди с приоритетом.
В куче, где у насэлементов
Вставка в кучу за
(амортизационное время)
Взятие минимума за
(зависит от реализации, в моей реализации это так)
Изъятие минимума за
И при этом, есть ещё один функционал, который работает быстро, если сравнивать с обычной кучей! В биномиальной куче можно сделать merge двух куч за . Возможно это бывает полезно ¯\_(ツ)_/¯
Как я тестировал свои решения
Здесь помог codeforces с системой для создания задач polygon. Задача выглядит следующим образом:
Сделаны эти "мини-тесты" для того, чтобы тесты были более рандомизированы и если была какая-то бага, то она выяснилась. Изначально тестов было 14 (и в течении статьи они будут пополняться для исследования).
Решение с помощью map в c++
Правильное решение выглядит так:
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while(t--) {
map<int, int> heap;
int n; cin >> n;
for (int i = 0; i < n; ++i) {
string op;
cin >> op;
if (op == "Insert") {
int x;
cin >> x;
heap[x]++;
} else if (op == "GetMin") {
cout << heap.begin()->first << '\n';
} else if (op == "EraseMin") {
heap.begin()->second--;
if (heap.begin()->second == 0) {
heap.erase(heap.begin());
}
}
}
}
return 0;
}
Просто заводится map<int, int>
, в котором ведётся подсчёт кол-ва элементов. При этом по умолчанию map
хранит элементы так, что при проходе контейнера от begin до end они будут в порядке увеличения ключа, поэтому минимум находится за, тогда как вставка и удаление работают за
. Если какой-то элемент встречается теперь
раз, то он удаляется из
map
, чтобы не увеличивать память и не замедлять операции.
Прошу заметить, что тут не подойдёт set
, так как он не хранит повторы (про multiset
автор решил тактично умолчать).
Первая реализация комом
Первая моя реализация давала протечку по памяти и выглядела так:
Комная реализация
#include <memory>
#include <cassert>
#include <functional>
#include <iostream>
#include <algorithm>
#include <list>
#include <stdexcept>
template<typename T>
class BinHeap {
private:
struct BinHeapNode {
T key;
std::list<std::shared_ptr<BinHeapNode>> childs;
size_t degree = 0;
};
std::shared_ptr<BinHeapNode> MergeEqualHeap(std::shared_ptr<BinHeapNode> l, std::shared_ptr<BinHeapNode> r) const {
if (!cmp(l->key, r->key)) {
swap(l, r);
}
l->childs.insert(l->childs.end(), r);
l->degree++;
return l;
}
public:
BinHeap() : size_(0) {};
BinHeap(const std::function<bool(T, T)>& cmpFunc) :
size_(0),
cmp(cmpFunc) {};
BinHeap(std::list<std::shared_ptr<BinHeapNode>>& newChilds,
const std::function<bool(T, T)>& cmpFunc) :
cmp(cmpFunc)
{
Heap_ = newChilds;
size_t newSize_ = 0;
for (const auto& c : Heap_) {
newSize_ += (1u << c->degree);
}
size_ = newSize_;
}
void push(const T& newKey) {
std::shared_ptr<BinHeapNode> node = std::make_shared<BinHeapNode>();
node->key = newKey;
auto it = Heap_.begin();
while (it != Heap_.end() && (*it)->degree == node->degree) {
if (cmp((*it)->key, node->key)) {
(*it)->childs.insert((*it)->childs.end(), node);
(*it)->degree++;
node = *it;
it = Heap_.erase(it);
}
else {
node->childs.insert(node->childs.end(), *it);
node->degree++;
}
}
Heap_.insert(it, node);
++size_;
}
void Merge(BinHeap& r) {
auto l = *this;
auto itl = l.Heap_.begin();
auto itr = r.Heap_.begin();
std::list<std::shared_ptr<BinHeapNode>> newHeap;
while (itl != l.Heap_.end() && itr != r.Heap_.end()) {
if ((*itl)->degree == (*itr)->degree) {
newHeap.insert(newHeap.end(), MergeEqualHeap(*itl, *itr));
itl = l.Heap_.erase(itl);
itr = r.Heap_.erase(itr);
}
else if (!newHeap.empty() && (*itl)->degree == newHeap.back()->degree) {
auto node = newHeap.back();
newHeap.pop_back();
newHeap.insert(newHeap.end(), MergeEqualHeap(node, *itl));
itl = l.Heap_.erase(itl);
}
else if (!newHeap.empty() && (*itr)->degree == newHeap.back()->degree) {
auto node = newHeap.back();
newHeap.pop_back();
newHeap.insert(newHeap.end(), MergeEqualHeap(node, *itr));
itr = r.Heap_.erase(itr);
}
else {
if (cmp((*itl)->key, (*itr)->key)) {
newHeap.insert(newHeap.end(), *itl);
itl = l.Heap_.erase(itl);
}
else {
newHeap.insert(newHeap.end(), *itr);
itr = r.Heap_.erase(itr);
}
}
}
while (itl != l.Heap_.end()) {
newHeap.insert(newHeap.end(), *itl);
itl = l.Heap_.erase(itl);
}
while (itr != r.Heap_.end()) {
newHeap.insert(newHeap.end(), *itr);
itr = r.Heap_.erase(itr);
}
Heap_ = newHeap;
}
size_t size() const {
return size_;
}
T top() const {
if (Heap_.empty()) {
return {}; // throw???
}
T res = Heap_.front()->key;
for (const auto& node : Heap_) {
if (cmp(node->key, res)) {
res = node->key;
}
}
return res;
}
void pop() {
if (Heap_.empty()) {
throw std::runtime_error("Erase from empty BinHeap");
}
auto minEl = Heap_.begin();
for (auto it = Heap_.begin(); it != Heap_.end(); ++it) {
if (cmp((*it)->key, (*minEl)->key)) {
minEl = it;
}
}
BinHeap<T> newHeap((*minEl)->childs, cmp);
Heap_.erase(minEl);
this->Merge(newHeap);
}
private:
size_t size_;
std::list<std::shared_ptr<BinHeapNode>> Heap_;
std::function<bool(T, T)> cmp = [](const T& l, const T& r) {
return l < r;
};
};
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while(t--) {
BinHeap<int> heap;
int n; cin >> n;
for (int i = 0; i < n; ++i) {
string op;
cin >> op;
if (op == "Insert") {
int x;
cin >> x;
heap.push(x);
} else if (op == "GetMin") {
cout << heap.top() << endl;
} else if (op == "EraseMin") {
heap.pop();
}
}
}
return 0;
}
Это давало ML (Memory Limit) на втором тесте. Протечка была знатная и моей первой протечкой от неё было просто удалять все элементы из кучи, пока она не пустая. Соответственно я добавил метод empty()
(надеюсь все догадываются как он выглядел) и я делал pop()
до того момента, пока куча не пустая перед тем, как закончить с ней работу.
За сколько это работало? Сначала было всё относительно хорошо: решение на map заходило за 498ms, а моя куча за 842ms. Но самый большой тест был таков, что былмини-тестов
операций в каждом мини-тесте. После чего мой сосед, Георгий Шукалов, говорит мне
Даня, так это же фигня, давай один тест на
операций
Я добавил этот тест (15-й тест). После чего пришлось изменить условие, что. В теории, всё должно было хорошо работать. После того, как я добавил один большой мини-тест на
операций, map проходил за 1045ms, а моя куча стала выдавать TL (Time Limit) на 15-м тесте (последним на тот момент тест, как раз в том, где в одной куче производится
операций).
Реализация без протечки
Вторая моя реализация выглядела так
Вторая реализация
#include <memory>
#include <cassert>
#include <functional>
#include <iostream>
#include <algorithm>
#include <list>
#include <stdexcept>
#include <unordered_set>
#include <queue>
template<typename T>
class BinHeap {
private:
struct BinHeapNode {
T key;
std::list<std::shared_ptr<BinHeapNode>> childs;
size_t degree = 0;
};
std::shared_ptr<BinHeapNode> MergeEqualHeap(std::shared_ptr<BinHeapNode> l, std::shared_ptr<BinHeapNode> r) const {
if (!cmp(l->key, r->key)) {
swap(l, r);
}
l->childs.insert(l->childs.end(), r);
l->degree++;
return l;
}
public:
BinHeap() : size_(0) {};
BinHeap(const std::function<bool(T, T)>& cmpFunc) :
size_(0),
cmp(cmpFunc) {};
void push(const T& newKey) {
std::shared_ptr<BinHeapNode> node = std::make_shared<BinHeapNode>();
node->key = newKey;
auto it = Heap_.begin();
while (it != Heap_.end() && (*it)->degree == node->degree) {
if (cmp((*it)->key, node->key)) {
(*it)->childs.insert((*it)->childs.end(), node);
(*it)->degree++;
node = *it;
}
else {
node->childs.insert(node->childs.end(), *it);
node->degree++;
}
if (it == MinNode_) {
MinNode_ = Heap_.end();
}
it = Heap_.erase(it);
}
if (MinNode_ == Heap_.end() || cmp(node->key, (*MinNode_)->key)) {
MinNode_ = Heap_.insert(it, node);
}
else {
Heap_.insert(it, node);
}
++size_;
}
void Merge(std::list<std::shared_ptr<BinHeapNode>>& r) {
auto itl = Heap_.begin();
auto itr = r.begin();
typename std::list<std::shared_ptr<BinHeapNode>>::iterator node;
while (itl != Heap_.end() && itr != r.end()) {
if ((*itl)->degree == (*itr)->degree) {
Heap_.insert(itl, MergeEqualHeap(*itl, *itr)); // вставляем вперёд itl
itl = Heap_.erase(itl); // переходим на то, что вставили
++itr;
}
else if (itl != Heap_.begin() && (*itl)->degree == (*prev(itl))->degree) {
node = prev(itl); // верх новой кучи
Heap_.insert(node, MergeEqualHeap(*node, *itl)); // вставляем по itl
Heap_.erase(node); // удаляем предыдущий элемент
itl = Heap_.erase(itl); //
}
else if (itl != Heap_.begin() && (*itr)->degree == (*prev(itl))->degree) {
node = prev(itl);
Heap_.insert(node, MergeEqualHeap(*node, *itr));
Heap_.erase(node);
++itr;
}
else {
if (cmp((*itl)->key, (*itr)->key)) {
++itl;
}
else {
Heap_.insert(itl, *itr);
++itr;
}
}
}
Heap_.insert(Heap_.end(), itr, r.end());
r.clear();
}
size_t size() const {
return size_;
}
T top() const {
if (Heap_.empty()) {
return {}; // throw???
}
return (*MinNode_)->key;
}
void pop() {
if (Heap_.empty()) {
throw std::runtime_error("Erase from empty BinHeap");
}
std::shared_ptr<BinHeapNode> mn_ptr = *MinNode_;
Heap_.erase(MinNode_);
this->Merge(mn_ptr->childs);
MinNode_ = Heap_.begin();
for (auto it = Heap_.begin(); it != Heap_.end(); ++it) {
if (cmp((*it)->key, (*MinNode_)->key)) {
MinNode_ = it;
}
}
size_--;
}
bool empty() const {
return size_ == 0;
}
private:
size_t size_;
std::list<std::shared_ptr<BinHeapNode>> Heap_;
typename std::list<std::shared_ptr<BinHeapNode>>::iterator MinNode_ = Heap_.end();
std::function<bool(T, T)> cmp = [](const T& l, const T& r) {
return l < r;
};
};
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
//BinHeap<int> heap;
while (t--) {
BinHeap<int> heap;
int n; cin >> n;
for (int i = 0; i < n; ++i) {
string op;
cin >> op;
if (op == "Insert") {
int x;
cin >> x;
heap.push(x);
}
else if (op == "GetMin") {
cout << heap.top() << '\n';
}
else if (op == "EraseMin") {
heap.pop();
}
}
//while (!heap.empty()) {
// heap.Erase();
//}
}
return 0;
}
Как видно, здесь уже не надо вручную удалять элементы из кучи, все удаления работают нормально. Также были убраны лишние копирования и было пересмотрено создавать кучу из list<shared_ptr<BinHeapNode>>
. Были приняты иные попытки ускорить кучу, но они не дали результатов.
Новые тесты
Опять же, мой сосед сказал
Так ты попробуй, чтобы у тебя элементов в куче побольше было, глядишь
BinHeap
будет побыстрее за счёт того, чтоpush
работает очень быстро
Я добавил два теста: в одном операции вставки, поиска минимума и удаление были в пропорции 3:3:2 (16-й тест), а в другом помимо этого, количество элементов не должно было опускаться ниже(17-й тест). Получились такие результаты:
Для 16-го теста
map
отработал за 347ms, а моя куча за 810msДля 17-го теста
map
отработал за 498ms, а моя куча за вышла за TL.
Что касается сравнения по тестам в итоге: реальная скорость и память
Напомним, что было по тестам:
До 14-го теста
тестов по
операций. По времени и памяти было всё одинаково, что в
map
, что в моей куче (в пределах погрешности в виде 30-50ms и 100-200КБ памяти)15-й тест
тест
операций с распределением операций Вставка/Взятие минимум/Извлечение минимума 2:1:1. По времени
map
отработал за 436ms, а моя куча за 1450ms. По памяти map съел 16k КБ, а моя куча 32k КБ.16-й тест
тест
операций с распределением операций Вставка/Взятие минимум/Извлечение минимума 3:3:2. По времени
map
отработал за 347ms, а моя куча за 810ms. По памяти map съел 10k КБ, а моя куча 18k КБ.16-й тест
тест
операций с распределением операций Вставка/Взятие минимум/Извлечение минимума 3:3:2 и минимальным количеством элементов в куч
. По времени
map
отработал за 498ms, а моя куча получила TL > 2000ms, поэтому сравнивать по памяти смысла нет.
В чём же плохо моё решение? Вставка же быстрее и все дела
Да, действительно, вставка в биномиальной куче работает очень быстро, но проблема начинается в другом: при хождении по биномиальной куче получается очень редкое попадание в кэш. Если map
хранит всё (насколько мне известно) не на указателях, а подряд, то в моей куче это пока не так (и есть над чем поработать в будущем). Ждите статью "Как я переписал Биномиальную кучу с указателей на массивы и выиграл кучу времени".
Как оказалось, не всегда асимптотически хорошее решение выигрывает при, казалось бы, правильной реализации.
Пожелания от читателей
Так как это была моя первая статья на хабре, я был бы рад, если бы вы смогли в комментариях предложить свои улучшения для изложения и прочие плюшки. Тогда в дальнейшем постараюсь сделать более качественный контент.