mdan_2000 16 сен 2021 в 11:52

Как я писал Биномиальную кучу

9 мин

4.5K

Как я начал эту затею
Что такое биномиальная куча?
Как я тестировал свои решения
Решение с помощью map в c++
Первая реализация комом
Реализация без протечки
Новые тесты
Что касается сравнения по тестам в итоге: реальная скорость и память
В чём же плохо моё решение? Вставка же быстрее и все дела
Пожелания от читателей

Как я начал эту затею

Я сейчас изучаю продвинутые структуры данных и в один прекрасный вечер я решил собирать алгоритмы и структуры данных к себе на гитхаб (и до сих пор это делаю). Захотел я сделать так, чтобы сделать всё шаблонным, если что-то мне резко понадобится, то я смог за считанные секунды добавить себе шаблонный класс структуры данных или шаблонную функцию алгоритма и использовать. Звучит замечательно, особенно на контесты с codeforces.

Я столкнулся с проблемами и решил здесь поделиться опытом с тем, кто также, как и я, мало знаком с пром. прогой и до этого в основном увлекался олимпиадным программированием.

Что такое биномиальная куча?

Об этом уже ни раз рассказывали, например на сайте ИТМО, здесь и ещё в прекрасных лекциях от Маврина Павла Юрьевича (посмотрите его видео, оно очень крутое!).

Если коротко, то биномиальная куча - структура данных, которая является деревом, реализующая интерфейс очереди с приоритетом.

В куче, где у насэлементов

Вставка в кучу за(амортизационное время)
Взятие минимума за(зависит от реализации, в моей реализации это так)
Изъятие минимума за $O\log(n)$

И при этом, есть ещё один функционал, который работает быстро, если сравнивать с обычной кучей! В биномиальной куче можно сделать merge двух куч за $O(\log n)$ . Возможно это бывает полезно ¯\_(ツ)_/¯

Как я тестировал свои решения

Здесь помог 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 они будут в порядке увеличения ключа, поэтому минимум находится за O(1) , тогда как вставка и удаление работают за $O(\log(n))$ . Если какой-то элемент встречается теперьраз, то он удаляется из 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. Но самый большой тест был таков, что был 10^3 мини-тестов 10^3 операций в каждом мини-тесте. После чего мой сосед, Георгий Шукалов, говорит мне

Даня, так это же фигня, давай один тест наопераций

Я добавил этот тест (15-й тест). После чего пришлось изменить условие, что $n \cdot t \leq 10^6$ . В теории, всё должно было хорошо работать. После того, как я добавил один большой мини-тест на 10^6 операций, map проходил за 1045ms, а моя куча стала выдавать TL (Time Limit) на 15-м тесте (последним на тот момент тест, как раз в том, где в одной куче производится 10^6 операций).

Реализация без протечки

Вторая моя реализация выглядела так

Вторая реализация

#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-й тест), а в другом помимо этого, количество элементов не должно было опускаться ниже 10^5 (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 хранит всё (насколько мне известно) не на указателях, а подряд, то в моей куче это пока не так (и есть над чем поработать в будущем). Ждите статью "Как я переписал Биномиальную кучу с указателей на массивы и выиграл кучу времени".

Как оказалось, не всегда асимптотически хорошее решение выигрывает при, казалось бы, правильной реализации.

Пожелания от читателей

Так как это была моя первая статья на хабре, я был бы рад, если бы вы смогли в комментариях предложить свои улучшения для изложения и прочие плюшки. Тогда в дальнейшем постараюсь сделать более качественный контент.

Теги:

Хабы:

Как я писал Биномиальную кучу

Оглавление