Is there in memory tree structure faster than std::map?
I have tried with AA tree (faster search slower insert), Btree (faster
search but slow erasing), general balanced tree (very slow inserts),
and finally my favorite Treap is slower for inserts and search
because it is not well balanced.
So I implemented scapegoat tree perfect balancing rebuilding of tree
during inserts for Treap, which repairs search but slows down insert
somewhat.
Sadly nothing I tried is faster on average than red black tree.
Here is my implementation of Treap with benchmark program so
if anyone wants to try I'd be rather interested to see results.
// bench program
// it is fair, as does searches after insert/erase operations,
// so in that case tree is least balanced
#include "Treap.h"
#include <map>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <iostream>
const int N = 100000;
int main()
{
std::vector<int> rnd1(N);
std::vector<int> rnd2(N);
for(int i = 0; i <N; ++i)
{
rnd1[i]=i;
rnd2[i]=i;
}
double sumtreap = 0,summap=0;
Treap<int,int> treap;
std::map<int,int> map;
clock_t begin,end;
double res;
for(int j = 0; j<3; ++j)
{
srand(time(0));
std::random_shuffle(rnd1.begin(),rnd1.end());
std::random_shuffle(rnd2.begin(),rnd2.end());
std::cout<<"------------------------------------\n";
begin = clock();
for(int i=0;i<N;++i)
{
treap[rnd1[i]]++;
treap.erase(rnd2[i]);
}
end = clock();
res = ((end-begin)/double(CLOCKS_PER_SEC));
sumtreap += res;
std::cout<<"treap insert/erase time "<<res<< "\n";
begin = clock();
for(int i=0;i<N;++i)
{
map[rnd1[i]]++;
map.erase(rnd2[i]);
}
end = clock();
res = ((end-begin)/double(CLOCKS_PER_SEC));
summap += res;
std::cout<<"map insert/erase time "<<res<< "\n\n";
begin = clock();
for(int i=0;i<N;++i)
{
treap.find(rnd2[i]);
}
end = clock();
res = ((end-begin)/double(CLOCKS_PER_SEC));
sumtreap += res;
std::cout<<"treap search time "<<res<< "\n";
begin = clock();
for(int i=0;i<N;++i)
{
map.find(rnd2[i]);
}
end = clock();
res = ((end-begin)/double(CLOCKS_PER_SEC));
summap += res;
std::cout<<"map search time "<<res<< "\n\n";
=09
begin = clock();
for(int i=0;i<N;++i)
{
treap[rnd1[i]]++;
}
end = clock();
res = ((end-begin)/double(CLOCKS_PER_SEC));
sumtreap += res;
std::cout<<"treap insert time "<<res<< "\n";
begin = clock();
for(int i=0;i<N;++i)
{
map[rnd1[i]]++;
}
end = clock();
res = ((end-begin)/double(CLOCKS_PER_SEC));
summap += res;
std::cout<<"map insert time "<<res<< "\n\n";
begin = clock();
for(int i=0;i<N/2;++i)
{=09
treap.erase(rnd2[i]);
}
end = clock();
res = ((end-begin)/double(CLOCKS_PER_SEC));
sumtreap += res;
std::cout<<"treap erase time "<<res<< "\n";
begin = clock();
for(int i=0;i<N/2;++i)
{=09
map.erase(rnd2[i]);
}
end = clock();
res = ((end-begin)/double(CLOCKS_PER_SEC));
summap += res;
std::cout<<"map erase time "<<res<< "\n\n";
}
std::cout<<"------------------------------------";
std::cout<<"\ntreap time "<<sumtreap<<"\n";
std::cout<<"\nmap time "<<summap<<"\n";
}
// Treap.h
#ifndef TREAP_H
#define TREAP_H
#include <functional>
#include <cstddef>
#include <utility>
#include <cassert>
#include <ctime>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <cstdlib>
template <class K,class V, class Compare = std::less<K> >
class Treap{
public:
Treap(unsigned seed = time(0))
: root_(0),size_(0),counter_(0), seed_(seed),inserts_(0),max_size_(0)
{
}
~Treap()
{
delete root_;
}
size_t size()const{ return size_; }
std::pair<K,V>& insert(const std::pair<K,V>& arg)
{
return insert_priv(arg);
}
V& operator[](const K& k)
{
return insert(std::pair<K,V>(k,V())).second;
}
V* find(const K& k)const;
size_t depth()const
{
size_t fd,ld;
first(root_,fd);
last(root_,ld);
if(fd>ld)return fd;
else return ld;
}
void erase(const K& key)
{
remove(key);
}
std::string toString()const
{
std::string tmp;
if(root_ == 0)tmp.append("Tree has no nodes");
else
{
tmp = toString(root_,"",true);
}
return tmp;
}
bool validate()const
{
return validate(root_);
}
size_t counter()const
{
return counter_;
}
void reset_counter()
{
counter_=0;
}
void clear()
{
delete root_;
size_ = 0;
root_ = 0;
}
void perfect_balance()
{
perfect_balance(root_);
}
template <class F>
void for_each(F f)
{
for_each(root_,f);
}
void weight(size_t& left,size_t& right)
{
if(!root_)
{
left=right=0;
return;
}
left = weight(root_->left_);
right = weight(root_->right_);
}
private:
struct Node{
Node(const std::pair<K,V>& data, Treap& trp)
: parent_(0),left_(0),right_(0),priority_(trp.prn()),data_(data)
{
}
~Node()
{
delete left_; delete right_;
}
Node* rotate_left()
{
Node* n = left_;
//std::cout<<"rotate left\n"<<toString(this,"",true)<<"\n";
if(n == 0)
{
return 0;
}
=09
left_ = n->right_;
if(left_)left_->parent_ = this;
=09
n->right_ = this;
if(parent_)
{
if(parent_->left_ == this)
{
parent_->left_ = n;
n->parent_ = parent_;
}
else
{
if(parent_->right_ != this)
{
std::cout<<"rotate right failed\nchild\n"<<toString(this,"",true)<<"\=
nparent\n"<<toString(parent_,"",true)<<"\n";
abort();
}
parent_->right_ = n;
n->parent_ = parent_;
}
}
else
{
n->parent_ = 0;
}
parent_ = n;
=09
return n;
}
Node* rotate_right()
{
Node* n = right_;
//std::cout<<"rotate right\n"<<toString(this,"",true)<<"\n";
if(n == 0)
{
return 0;
}
right_ = n->left_;
if(right_)right_->parent_ = this;
=09
n->left_ = this;
if(parent_)
{
if(parent_->left_ == this)
{
parent_->left_ = n;
n->parent_ = parent_;
}
else
{
if(parent_->right_ != this)
{
std::cout<<"rotate right failed\nchild\n"<<toString(this,"",true)<<"\=
nparent\n"<<toString(parent_,"",true)<<"\n";
abort();
}
parent_->right_ = n;
n->parent_ = parent_;
}
}
else
{
n->parent_ = 0;
}
parent_ = n;
=09
return n;
}
Node *parent_,*left_,*right_;
unsigned priority_;
std::pair<K,V> data_;
};
size_t weight(Node* n)
{
if(!n)return 0;
return weight(n->left_)+weight(n->right_)+1;
}
template <class F>
void for_each(Node* n, F f)
{
if(!n)return;
for_each(n->left_,f);
f(n->data_);
for_each(n->right_,f);
}
unsigned prn()
{
return rand_r(&seed_);
}
Node* first(Node* n,size_t& depth)const
{
Node *rc = 0;
depth = 0;
while(n)
{
++depth;
rc = n;
n = n->left_;
}
return rc;
}
Node* last(Node* n,size_t& depth)const
{
Node* rc = 0;
depth = 0;
while(n)
{
++depth;
rc = n;
n = n->right_;
}
return rc;
}
std::pair<K,V>& insert_priv(const std::pair<K,V>& ins_value,Node* node ==
0)
{
if(root_ == 0)
{
if(!node)
root_ = new Node(ins_value,*this);
else
{
root_ = node;
node->parent_ = node->left_ = node->right_ = 0;
}
++size_;
return root_->data_;
}
Compare cmp;
Node* n = root_;
Node *rc = 0, *prev = 0;
bool ret;
while(n)
{
prev = n;
ret = cmp(ins_value.first,n->data_.first);
if(ret)
{
n=n->left_;
}
else
{
rc = n;
n = n->right_;
}
}
if(rc && !cmp(rc->data_.first,ins_value.first))
{
return rc->data_;
}
=09
if(ret)
{
if(!node)
{
rc = prev->left_ = new Node(ins_value,*this);
}
else
{
rc = prev->left_ = node;
rc->parent_ = rc->left_ = rc->right_ = 0;
}
prev->left_->parent_ = prev;
}
else
{
if(!node)
{
rc = prev->right_ = new Node(ins_value,*this);
}
else
{
rc = prev->right_ = node;
rc->parent_ = rc->left_ = rc->right_ = 0;
}
prev->right_->parent_ = prev;
}
=09
if(!node && inserts_>max_size_)
{
inserts_ = 0;
max_size_ = size_*2;
perfect_balance();
}
else
{
n = rc;
rebalance_up(n);
++size_;
++inserts_;
}
return rc->data_;
}
void remove(const K& rem_value)
{
Compare cmp;
Node* rc = 0,*n = root_;
while(n)
{
bool ret = cmp(rem_value,n->data_.first);
if(ret)
{
n = n->left_;
}
else
{
rc = n;
n = n->right_;
}
}
if(!rc || cmp(rc->data_.first,rem_value))return;
=09
Node* reb = 0;
while(rc->left_ && rc->right_)
{
Node* n = rc->rotate_right();
if(root_ == rc)root_ = n;
if(!reb && n->left_ && n->left_->priority_ < n->priority_)reb = n;
}
Node** parent_node = 0;
if(rc->parent_)
parent_node = ((rc->parent_->left_ == rc)?&rc->parent_->left_:&rc-=
parent_->right_);
if(rc->left_ == 0 && rc->right_ == 0)
{
if(parent_node)*parent_node = 0;
else root_ = 0;
}
else
if(rc->left_ == 0)
{
if(parent_node)
{
*parent_node = rc->right_;
rc->right_->parent_ = rc->parent_;
}
else
{
root_ = rc->right_;
rc->right_->parent_ = 0;
}
rc->right_ = 0;
}
else
if(rc->right_ == 0)
{
if(parent_node)
{
*parent_node = rc->left_;
rc->left_->parent_ = rc->parent_;
}
else
{
root_ = rc->left_;
rc->left_->parent_ = 0;
}
rc->left_ = 0;
}
delete rc;
--size_;
if(max_size_>0)--max_size_;
rebalance_left(reb);
=09
}
bool validate(const Node* node)const
{
if(!node)return true;
Compare cmp;
if(node->left_ && !cmp(node->left_->data_.first,node->data_.first))
{
return false;
}
if(node->right_ && !cmp(node->data_.first,node->right_->data_.first))
{
return false;
}
if(node->left_ && node->left_->parent_ != node)
{
return false;
}
if(node->right_ && node->right_->parent_ != node)
{
return false;
}
if(node->left_ && node->priority_ > node->left_->priority_)
{
return false;
}
if(node->right_ && node->priority_ > node->right_->priority_)
{
return false;
}
bool rc1 = validate(node->left_);
bool rc2 = validate(node->right_);
return rc1 && rc2;
=09
}
void rebalance_left(Node* node)
{
if(!node)return;
rebalance_left(node->left_);
while(node->left_ && node->left_->priority_ < node->priority_)
{
Node* n = node->rotate_left();
if(node == root_)root_ = n;
}
}
void rebalance_right(Node* node)
{
if(!node)return;
rebalance_right(node->right_);
while(node->right_ && node->right_->priority_ < node->priority_)
{
Node* n = node->rotate_right();
if(node == root_)root_ = n;
}
}
void rebalance_up(Node* n)
{
while(n->parent_ && n->priority_ < n->parent_->priority_)
{
if(n->parent_->left_ == n)
n = n->parent_->rotate_left();
else
n = n->parent_->rotate_right();
if(n->parent_ == 0)root_ = n;
}
}
struct P{
P(Treap& t):t(t),weight(0){v.reserve(t.size());}
void operator()(Node* n)
{
v.push_back(n);
++weight;
}
Treap& t;
std::vector<Node*> v;
size_t weight;
};
template <class F>
void for_each_node(Node* n, F& f)
{
if(!n)return;
for_each_node(n->left_,f);
f(n);
for_each_node(n->right_,f);
}
void perfect_balance(Node *n)
{
if(!n)return;
P p(*this);
for_each_node(n,p);
Node** link = 0, *parent=0;
if(n->parent_)
{
if(n->parent_->left_ == n)
link = &n->parent_->left_;
else
link = &n->parent_->right_;
size_ -= p.weight;
parent = n->parent_;
}
else
{
link = &root_;
size_ = 0;
}
Treap<K,V,Compare> tmp;
unsigned prio = parent?parent->priority_+100000:0;
tmp.insert_divide(0,p.v.size(),p.v,prio);
*link = tmp.root_;
if(parent)tmp.root_->parent_ = parent;
size_ += tmp.size_;
tmp.root_ = 0;
}
void insert_divide(size_t b, size_t e,std::vector<Node*>& v,size_t prio)
{
if(e == b)return;
Node* p = v[(b+e)/2];
p->priority_ = prio;
insert_priv(p->data_,p);
insert_divide(b,(e+b)/2,v,prio+100000);
insert_divide((e+b)/2+1,e,v,prio+100000);
}
static std::string toString(const Node* node, const std::string& prefix, b=
ool isTail)
{
std::string tmp;
tmp.append(prefix).append(isTail ? "=E2=94=94=E2=94=80=E2=94=80 " : "=E2=
=94=9C=E2=94=80=E2=94=80 ");
=09
if(!node)
{
tmp.append(" null");
return tmp;
}
std::ostringstream oss;
const std::pair<K,V>& v = node->data_;
oss<<"p:"<<node->priority_<<" ("<<v.first<<","<<v.second<<")";
tmp.append(oss.str());
oss.str("");
tmp.append("\n");
=09
tmp.append(toString(node->left_,prefix + (isTail?" ":"=E2=94=82 "),f=
alse));
tmp.append("\n");
tmp.append(toString(node->right_,prefix + (isTail ? " " : "=E2=94=82 =
"),true));
return tmp;
}
public:
class iterator{
public:
iterator(Node* n):node_(n){}
std::pair<K,V>& operator*()const{ return node_->data_; }
std::pair<K,V>* operator->()const{ return &node_->data_; }
bool operator==(const iterator& other)const
{
return node_ == other.node_;
}
bool operator!=(const iterator& other)const
{
return !(*this == other);
}
iterator& operator++()
{
if(node_->right_ != 0)
{
node_ = node_->right_;
while(node_->left_ != 0)
{
node_ = node_->left_;
}
}
else
{
Node* tmp = node_->parent_;
while(tmp && node_ == tmp->right_)
{
node_ = tmp;
tmp = tmp->parent_;
}
if(node_->right_ != tmp)
{
node_ = tmp;
}
}
return *this;
}
private:
Node* node_;
};
iterator begin()
{
size_t depth = 0;
return iterator(first(depth));
}
iterator end()const
{
return iterator(0);
}
private:
Node* root_;
size_t size_,counter_;
unsigned seed_;
unsigned inserts_,max_size_;
bool flip_;
};
template <class K,class V, class Compare>
V* Treap<K,V,Compare>::find(const K& k)const
{
Compare cmp;
Node* n = root_,*tmp = 0;
V* rc = 0;
while(n)
{
bool ret = cmp(k,n->data_.first);
if(ret)
{
n = n->left_;
}
else
{
tmp = n;
n = n->right_;
}
}
if(tmp && !cmp(tmp->data_.first,k))
{
rc = &tmp->data_.second;
}
return rc;
}
#endif