Skip to content

Instantly share code, notes, and snippets.

@eXCoreX

eXCoreX/main.cpp Secret

Last active February 19, 2021 10:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save eXCoreX/e3dcb3cc60fa13272b0626c3ffb19844 to your computer and use it in GitHub Desktop.
Save eXCoreX/e3dcb3cc60fa13272b0626c3ffb19844 to your computer and use it in GitHub Desktop.
Download ZIP
Linked List + 2 Hash Maps vs Tree Map
Raw
main.cpp
// {
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <list>
#include <iostream>
#include <chrono>
using namespace std;
// }
class Constant {
private:
// Appart from value we also store the iterator to the corresponding current bucket.
struct Value {
unsigned int value;
list<pair<unsigned int, unordered_set<string>>>::iterator bucket;
};
// List of buckets: value + set of keys with this value.
// We keep this list sorted by value.
list<pair<unsigned int, unordered_set<string>>> _buckets;
// Map from value to count of keys with that value.
unordered_map<unsigned int, unsigned int> _counts;
// Map from key to Value.
unordered_map<string, Value> _values;
public:
void create_element(const string& key) {
if (_buckets.size() == 0 || _buckets.front().first != 1) {
_buckets.push_front(make_pair(1, unordered_set<string>{key}));
}
else {
_buckets.front().second.insert(key);
}
auto it = _buckets.begin();
_values.insert(make_pair(key, Value{ 1, it }));
_counts[1]++;
}
void delete_element(unordered_map<string, Value>::iterator it) {
_counts[1]--;
if (_counts[1] == 0) {
_buckets.pop_front();
}
else {
_buckets.front().second.erase(it->first);
}
_values.erase(it);
}
// Adjust element by +1/-1
void adjust_element(unordered_map<string, Value>::iterator it, int adj) {
unsigned current = it->second.value;
unsigned next = current + adj;
_counts[current]--;
_counts[next]++;
// remove the key from the current bucket
it->second.bucket->second.erase(it->first);
// no bucket change, just adjust the number in the bucket
if (_counts[current] == 0 && _counts[next] == 1) {
it->second.bucket->first += adj;
}
// no bucket change, we need to adjust iterator
if (_counts[current] > 0 && _counts[next] > 1) {
advance(it->second.bucket, adj);
}
// create a new next bucket
if (_counts[current] > 0 && _counts[next] == 1) {
if (adj > 0) // insert inserts before the element, if we are increasing value, we want first advance once
advance(it->second.bucket, adj);
it->second.bucket = _buckets.insert(it->second.bucket, make_pair(next, unordered_set<string>{it->first}));
}
// delete the current bucket
if (_counts[current] == 0 && _counts[next] > 1) {
it->second.bucket = _buckets.erase(it->second.bucket);
if (adj < 0) // erase returns the iterator after the removed element, if we decreasing the value, we need to go one back
advance(it->second.bucket, adj);
}
// add the bucket to the next bucket
it->second.bucket->second.insert(it->first);
it->second.value = next;
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(const string& key) {
auto it = _values.find(key);
if (it == _values.end()) {
create_element(key);
}
else {
adjust_element(it, 1);
}
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(const string& key) {
auto it = _values.find(key);
if (it == _values.end())
return;
if (it->second.value == 1) {
delete_element(it);
}
else {
adjust_element(it, -1);
}
}
/** Returns one of the keys with maximal value. */
string getMaxKey() const {
if (_buckets.empty())
return string("");
return *_buckets.back().second.begin();
}
/** Returns one of the keys with Minimal value. */
string getMinKey() const {
if (_buckets.empty())
return string("");
return *_buckets.front().second.begin();
}
};
string gen_string(size_t len)
{
static const char alphanum[] =
"0123456789"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
string res;
for (size_t i = 0; i < len; i++)
{
res += alphanum[rand() % (sizeof(alphanum) - 1)];
}
return res;
}
using namespace std::chrono;
// {
int main() {
const size_t TEST_NUM = 10;
const size_t CASE_SIZE = 100000;
const size_t KEYS_NUM = 100000;
Constant c;
map<string, int> m;
vector<string> keys = { "a", "b", "c", "d", "e" };
srand(time(nullptr));
cout << "5 known keys:\n";
{
auto inc = [&c](const string& key) {
c.inc(key);
c.getMinKey();
c.getMaxKey();
// cout << "inc(\"" << key << "\") min = \"" << c.getMinKey() << "\" max = \"" << c.getMaxKey() << "\"" << endl;
};
auto dec = [&c](const string& key) {
c.dec(key);
c.getMinKey();
c.getMaxKey();
// cout << "dec(\"" << key << "\") min = \"" << c.getMinKey() << "\" max = \"" << c.getMaxKey() << "\"" << endl;
};
high_resolution_clock::time_point t1 = high_resolution_clock::now();
high_resolution_clock::time_point t2 = high_resolution_clock::now();
auto total = duration_cast<microseconds>(t1 - t1);
for (int test = 0; test < TEST_NUM; test++)
{
t1 = high_resolution_clock::now();
for (int i = 0; i < CASE_SIZE; i++)
{
inc(keys[rand() % 5]);
dec(keys[rand() % 5]);
}
t2 = high_resolution_clock::now();
total += duration_cast<microseconds>(t2 - t1);
}
total /= TEST_NUM;
cout << "Average O(1): " << total.count() << " us\n";
auto inc_m = [&m](const string& key)
{
++m[key];
m.begin();
m.rbegin();
};
auto dec_m = [&m](const string& key)
{
auto it = m.find(key);
if (it == m.end())
{
return;
}
--(it->second);
if (it->second == 0)
{
m.erase(it);
}
m.begin();
m.rbegin();
};
auto total_m = duration_cast<microseconds>(t1 - t1);
for (int test = 0; test < TEST_NUM; test++)
{
t1 = high_resolution_clock::now();
for (int i = 0; i < CASE_SIZE; i++)
{
inc_m(keys[rand() % 5]);
dec_m(keys[rand() % 5]);
}
t2 = high_resolution_clock::now();
total_m += duration_cast<microseconds>(t2 - t1);
}
total_m /= TEST_NUM;
cout << "Average O(log(n)): " << total_m.count() << " us\n";
}
cout << KEYS_NUM << " random keys:\n";
keys = vector<string>(KEYS_NUM);
for (size_t i = 0; i < KEYS_NUM; i++)
{
keys[i] = gen_string(static_cast<size_t>(rand() % 10) + 1);
}
{
auto inc = [&c](const string& key) {
c.inc(key);
c.getMinKey();
c.getMaxKey();
// cout << "inc(\"" << key << "\") min = \"" << c.getMinKey() << "\" max = \"" << c.getMaxKey() << "\"" << endl;
};
auto dec = [&c](const string& key) {
c.dec(key);
c.getMinKey();
c.getMaxKey();
// cout << "dec(\"" << key << "\") min = \"" << c.getMinKey() << "\" max = \"" << c.getMaxKey() << "\"" << endl;
};
high_resolution_clock::time_point t1 = high_resolution_clock::now();
high_resolution_clock::time_point t2 = high_resolution_clock::now();
auto total = duration_cast<microseconds>(t1 - t1);
for (int test = 0; test < TEST_NUM; test++)
{
t1 = high_resolution_clock::now();
for (int i = 0; i < CASE_SIZE; i++)
{
inc(keys[rand() % KEYS_NUM]);
dec(keys[rand() % KEYS_NUM]);
}
t2 = high_resolution_clock::now();
total += duration_cast<microseconds>(t2 - t1);
}
total /= TEST_NUM;
cout << "Average O(1): " << total.count() << " us\n";
auto inc_m = [&m](const string& key)
{
++m[key];
m.begin();
m.rbegin();
};
auto dec_m = [&m](const string& key)
{
auto it = m.find(key);
if (it == m.end())
{
return;
}
--(it->second);
if (it->second == 0)
{
m.erase(it);
}
m.begin();
m.rbegin();
};
auto total_m = duration_cast<microseconds>(t1 - t1);
for (int test = 0; test < TEST_NUM; test++)
{
t1 = high_resolution_clock::now();
for (int i = 0; i < CASE_SIZE; i++)
{
inc_m(keys[rand() % KEYS_NUM]);
dec_m(keys[rand() % KEYS_NUM]);
}
t2 = high_resolution_clock::now();
total_m += duration_cast<microseconds>(t2 - t1);
}
total_m /= TEST_NUM;
cout << "Average O(log(n)): " << total_m.count() << " us\n";
}
}
// }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment