Skip to content

Instantly share code, notes, and snippets.

@coderodde coderodde/main.cpp
Last active Dec 18, 2016

Embed
What would you like to do?
CodeReview Fibonacci heap performance demonstration
#include <iostream>
#include <algorithm>
#include <stdexcept>
#include <functional>
#include <unordered_map>
#include <vector>
template<typename K, typename P, typename Func = std::less<P>>
class fib_heap {
struct node {
K key;
P prty;
unsigned degree = 0;
bool mark = false;
node* parent = nullptr;
node* childs = nullptr;
node* left = nullptr;
node* right = nullptr;
node(const K& pkey, const P& priority)
: key(pkey),
prty(priority) { }
node(K&& pkey, const P& priority)
: key(std::move(pkey)),
prty(priority) { }
node(const K& pkey, P&& priority)
: key(pkey),
prty(std::move(priority)) { }
node(K&& pkey, P&& priority)
: key(std::move(pkey)),
prty(std::move(priority)) { }
node* add_brother(node* n) {
n->parent = parent;
n->left = this;
n->right = right;
right->left = n;
right = n;
return this;
}
node* remove_self() {
left->right = right;
right->left = left;
return this;
}
node* add_child(node* n) {
if (childs == nullptr) {
childs = n->to_single_list();
n->parent = this;
}
else {
childs->add_brother(n);
}
n->mark = false;
++degree;
return this;
}
node* to_single_list() {
left = this;
right = this;
return this;
}
void destroy() {
auto n = childs;
for (auto i = 0u; i < degree; ++i) {
auto next = n->right;
n->destroy();
n = next;
}
delete this;
}
};
void consolidate() {
unsigned bound = static_cast<unsigned>(
std::log(N) / LOG_OF_GOLDEN) + 1;
auto degree_array = new node*[bound]();
for (auto n = min; root_size > 0; --root_size) {
auto parent = n;
auto d = parent->degree;
n = n->right;
while (degree_array[d] != nullptr) {
auto child = degree_array[d];
if (cmp(child->prty, parent->prty)) {
std::swap(child, parent);
}
parent->add_child(child->remove_self());
degree_array[d++] = nullptr;
}
degree_array[d] = parent;
}
auto d = 0u;
while (degree_array[d++] == nullptr);
min = degree_array[d - 1]->to_single_list();
for (; d < bound; ++d) {
if (degree_array[d] != nullptr) {
add_to_root(degree_array[d]);
}
}
delete [] degree_array;
++root_size;
}
node* remove_min() {
if (empty()) {
throw std::underflow_error("underflow");
}
auto deleted = min;
add_childs_to_root(deleted);
deleted->remove_self();
--root_size;
if (deleted == deleted->right) {
min = nullptr;
}
else {
min = min->right;
consolidate();
}
--N;
return deleted;
}
void add_to_root(node* n) {
min->add_brother(n);
if (cmp(n->prty, min->prty)) {
min = n;
}
++root_size;
}
void add_childs_to_root(node* n) {
auto c = n->childs;
auto d = n->degree;
for (auto i = 0u; i < d; ++i) {
auto next = c->right;
add_to_root(c);
c = next;
}
}
template<typename PP>
void decrease_priority(node *n, PP&& new_p) {
if (cmp(n->prty, new_p)) {
throw std::runtime_error("key is greater");
}
n->prty = std::forward<PP>(new_p);
auto p = n->parent;
if (p != nullptr
&& cmp(n->prty, p->prty)) {
cut(n, p);
cascading_cut(p);
}
if (cmp(n->prty, min->prty)) {
min = n;
}
}
void cut(node* child, node* parent) {
min->add_brother(child->remove_self());
child->mark = false;
--parent->degree;
if (parent->degree == 0) {
parent->childs = nullptr;
}
else if (parent->childs == child) {
parent->childs = child->right;
}
++root_size;
}
void cascading_cut(node* n) {
while (n->parent != nullptr && n->mark) {
cut(n, n->parent);
n = n->parent;
}
n->mark = n->mark || n->parent;
}
static constexpr double LOG_OF_GOLDEN = 0.4812118;
std::unordered_map<K, node*> map_to_ptr;
node* min;
unsigned N;
unsigned root_size;
Func cmp;
public:
fib_heap()
: fib_heap(Func()){ }
fib_heap(Func pcmp) :
min(nullptr),
N(0),
root_size(0),
cmp(pcmp) { }
~fib_heap() {
auto n = min;
for (auto i = 0u; i < root_size; ++i) {
auto next = n->right;
n->destroy();
n = next;
}
}
void pop() {
auto min_node = remove_min();
map_to_ptr.erase(min_node->key);
delete min_node;
}
const std::pair<const K&, const P&> top() {
return { min->key, min->prty };
}
template<typename KK, typename PP>
void insert(KK&& key, PP&& prty) {
auto &new_node = map_to_ptr[key];
if (new_node != nullptr) {
return;
}
new_node = new node(std::forward<KK>(key),
std::forward<PP>(prty));
if (min == nullptr) {
min = new_node->to_single_list();
++root_size;
}
else {
add_to_root(new_node);
}
++N;
}
template<typename PP>
void decrease(const K& key, PP&& prty) {
auto itr = map_to_ptr.find(key);
if (itr != map_to_ptr.end()) {
decrease_priority(itr->second,
std::forward<PP>(prty));
}
}
bool empty() {
return min == nullptr;
}
unsigned size() {
return N;
}
};
template<typename K, typename P, typename Func = std::less<P>>
class fib_heap2 {
struct node {
K key;
P prty;
unsigned degree = 0;
bool mark = false;
node* parent = nullptr;
node* childs = nullptr;
node* left = nullptr;
node* right = nullptr;
node(const K& pkey, const P& priority)
: key(pkey),
prty(priority) { }
node(K&& pkey, const P& priority)
: key(std::move(pkey)),
prty(priority) { }
node(const K& pkey, P&& priority)
: key(pkey),
prty(std::move(priority)) { }
node(K&& pkey, P&& priority)
: key(std::move(pkey)),
prty(std::move(priority)) { }
node* add_brother(node* n) {
n->parent = parent;
n->left = this;
n->right = right;
right->left = n;
right = n;
return this;
}
node* remove_self() {
left->right = right;
right->left = left;
return this;
}
node* add_child(node* n) {
if (childs == nullptr) {
childs = n->to_single_list();
n->parent = this;
}
else {
childs->add_brother(n);
}
n->mark = false;
++degree;
return this;
}
node* to_single_list() {
left = this;
right = this;
return this;
}
void destroy() {
auto n = childs;
for (auto i = 0u; i < degree; ++i) {
auto next = n->right;
n->destroy();
n = next;
}
delete this;
}
};
void consolidate() {
unsigned bound = static_cast<unsigned>(
std::log(N) / LOG_OF_GOLDEN) + 1;
if (bound > degree_array_length)
{
delete[] degree_array;
degree_array = new node*[bound]();
degree_array_length = bound;
}
else
{
std::memset(degree_array, 0, bound * sizeof(node*));
}
for (auto n = min; root_size > 0; --root_size) {
auto parent = n;
auto d = parent->degree;
n = n->right;
while (degree_array[d] != nullptr) {
auto child = degree_array[d];
if (cmp(child->prty, parent->prty)) {
std::swap(child, parent);
}
parent->add_child(child->remove_self());
degree_array[d++] = nullptr;
}
degree_array[d] = parent;
}
auto d = 0u;
while (degree_array[d++] == nullptr);
min = degree_array[d - 1]->to_single_list();
for (; d < bound; ++d) {
if (degree_array[d] != nullptr) {
add_to_root(degree_array[d]);
}
}
++root_size;
}
node* remove_min() {
if (empty()) {
throw std::underflow_error("underflow");
}
auto deleted = min;
add_childs_to_root(deleted);
deleted->remove_self();
--root_size;
if (deleted == deleted->right) {
min = nullptr;
}
else {
min = min->right;
consolidate();
}
--N;
return deleted;
}
void add_to_root(node* n) {
min->add_brother(n);
if (cmp(n->prty, min->prty)) {
min = n;
}
++root_size;
}
void add_childs_to_root(node* n) {
auto c = n->childs;
auto d = n->degree;
for (auto i = 0u; i < d; ++i) {
auto next = c->right;
add_to_root(c);
c = next;
}
}
template<typename PP>
void decrease_priority(node *n, PP&& new_p) {
if (cmp(n->prty, new_p)) {
throw std::runtime_error("key is greater");
}
n->prty = std::forward<PP>(new_p);
auto p = n->parent;
if (p != nullptr
&& cmp(n->prty, p->prty)) {
cut(n, p);
cascading_cut(p);
}
if (cmp(n->prty, min->prty)) {
min = n;
}
}
void cut(node* child, node* parent) {
min->add_brother(child->remove_self());
child->mark = false;
--parent->degree;
if (parent->degree == 0) {
parent->childs = nullptr;
}
else if (parent->childs == child) {
parent->childs = child->right;
}
++root_size;
}
void cascading_cut(node* n) {
while (n->parent != nullptr && n->mark) {
cut(n, n->parent);
n = n->parent;
}
n->mark = n->mark || n->parent;
}
static constexpr double LOG_OF_GOLDEN = 0.4812118;
std::unordered_map<K, node*> map_to_ptr;
node** degree_array = new node*[10];
size_t degree_array_length = 10;
node* min;
unsigned N;
unsigned root_size;
Func cmp;
public:
fib_heap2()
: fib_heap2(Func()){ }
fib_heap2(Func pcmp) :
min(nullptr),
N(0),
root_size(0),
cmp(pcmp) { }
~fib_heap2() {
auto n = min;
for (auto i = 0u; i < root_size; ++i) {
auto next = n->right;
n->destroy();
n = next;
}
delete[] degree_array;
}
void pop() {
auto min_node = remove_min();
map_to_ptr.erase(min_node->key);
delete min_node;
}
const std::pair<const K&, const P&> top() {
return { min->key, min->prty };
}
template<typename KK, typename PP>
void insert(KK&& key, PP&& prty) {
auto &new_node = map_to_ptr[key];
if (new_node != nullptr) {
return;
}
new_node = new node(std::forward<KK>(key),
std::forward<PP>(prty));
if (min == nullptr) {
min = new_node->to_single_list();
++root_size;
}
else {
add_to_root(new_node);
}
++N;
}
template<typename PP>
void decrease(const K& key, PP&& prty) {
auto itr = map_to_ptr.find(key);
if (itr != map_to_ptr.end()) {
decrease_priority(itr->second,
std::forward<PP>(prty));
}
}
bool empty() {
return min == nullptr;
}
unsigned size() {
return N;
}
};
class CurrentTime {
std::chrono::high_resolution_clock m_clock;
public:
uint64_t milliseconds()
{
return std::chrono::duration_cast<std::chrono::milliseconds>
(m_clock.now().time_since_epoch()).count();
}
};
int main(int argc, const char * argv[]) {
fib_heap<int, int> heap1;
fib_heap2<int, int> heap2;
CurrentTime ct;
auto start = ct.milliseconds();
for (int i = 0; i < 10 * 1000 * 1000; ++i)
{
heap1.insert(i, 10 * 1000 * 1000 - i);
}
while (heap1.size() > 0)
{
heap1.pop();
}
auto end = ct.milliseconds();
std::cout << "Fibonacci heap with array in " << (end - start) << " milliseconds." << std::endl;
start = ct.milliseconds();
for (int i = 0; i < 10 * 1000 * 1000; ++i)
{
heap2.insert(i, 10 * 1000 * 1000 - i);
}
while (heap2.size() > 0)
{
heap2.pop();
}
end = ct.milliseconds();
std::cout << "Fibonacci heap with storage in " << (end - start) << " milliseconds." << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.