Kalanand's October 2015 Log
October 1st
To compile C++11 file on my mac, I needed to do
g++ -std=c++11 <my_file.cpp> -o <my_program>
For example:
g++ -std=c++11 test_lru_cache.cpp -o test_lru_cache
October 2nd
LRU Cache
- Least Recently Used (LRU) is a family of caching algorithms,
which discards the least recently used (i.e., "the oldest seen") items first.
- This algorithm requires keeping track of when an item was
used. The key data structure of the algorithm is a Hash Map of
elements along with pointers to the forward and backward links.
- In the implementation below I initialize the Hash Map in a pre-defined size to store
elements and use the two links to index these elements
in the order of data age.
- The hash table makes the time of get() and the node addition/removal operations O(1).
//LruCache.h
#pragma once
#include <iostream>
#include <unordered_map>
#include <cstddef>
template<typename T>
class lru_cache {
public:
//Default constructor
lru_cache(){}
//Constructor: argument is the maximum cache size
lru_cache(const size_t max_size) : m_max_size(max_size) {}
//Destructor
~lru_cache()
{
//Delete nodes and clear the map
for (auto & it : m_cache_map)
{
if (it.second) delete it.second;
}
m_cache_map.clear();
}
struct Node {
typedef typename std::unordered_map<T, Node*>::iterator iterator;
iterator it;
Node *prev, *next;
Node() : it(iterator()), prev(nullptr), next(nullptr) {}
};
//Set maximum cache size
void set_max_size(const size_t max_size)
{
m_max_size = max_size;
//Delete items if the new max size is smaller
auto temp = m_tail;
while (temp != nullptr && m_cache_map.size() > m_max_size)
{
removeTail();
temp = m_tail;
}
}
//Put the most recent element to the LRU cache
//Returns true if added a element to the map else returns false
bool put(const T& element)
{
bool added_new;
//If element exists, update our links
typename std::unordered_map<T, Node*>::iterator entry;
std::tie(entry, added_new) = m_cache_map.emplace(element, new Node());
entry->second->it = entry;
if (!added_new)
{
//Remove this node if it already exists
removeNode(entry->second);
}
else if (m_cache_map.size() > m_max_size)
{
//If surpassed max capacity, delete the oldest entry
removeTail();
}
//The newest node is the head now
setHead(entry->second);
return added_new;
}
//Check if element exists in cache: returns the corresponding node
inline Node* exists(const T& element)
{
auto it = m_cache_map.find(element);
if (it == m_cache_map.end()) return nullptr;
return it->second;
}
//Size of the cache at a given instant
inline size_t size() const
{
return m_cache_map.size();
}
//Get maximum cache size
inline size_t max_size() const
{
return m_max_size;
}
//Get the head node
inline const Node* get_head() const
{
return m_head;
}
//Get the tail node
inline const Node* get_tail() const
{
return m_tail;
}
//Get cache map
inline const std::unordered_map<T, Node*>& get_cache() const
{
return m_cache_map;
}
private:
Node *m_head=nullptr, *m_tail=nullptr;
std::unordered_map<T, Node*> m_cache_map;
size_t m_max_size;
//Remove this node
void removeNode(Node *node)
{
if(node->prev)
{
node->prev->next = node->next;
}
else
{
m_head = node->next;
}
if(node->next)
{
node->next->prev = node->prev;
}
else
{
m_tail = node->prev;
}
}
//Set head
void setHead(Node *node)
{
node->next = m_head;
node->prev = nullptr;
if(m_head) m_head->prev = node;
m_head = node;
if(!m_tail) m_tail = node;
}
//Delete the oldest entry
void removeTail()
{
Node *tmp = m_tail;
auto tail_element = tmp->it->first;
m_tail = m_tail->prev;
if(m_tail) m_tail->next = nullptr;
delete tmp;
//Delete this from the map
if (m_cache_map.find(tail_element) != m_cache_map.end())
{
m_cache_map.erase(tail_element);
}
}
};
Testing the above implementation
Let's test our LRU cache for both numbers and strings.
//test_lru_cache.cpp
#include "LruCache.h"
#include <iostream>
#include <assert.h>
const int CACHE_CAPACITY = 10;
//Print the current cache
template<typename T>
void print_cache(lru_cache<T>& cache) {
std::cout << "======= Current cache =======" << std::endl;
int count = 0;
auto temp = cache.get_head();
auto & map = cache.get_cache();
while ( temp !=NULL)
{
if (count > 0) std::cout << ", ";
for (const auto & it : map)
{
if (it.second == temp)
{
std::cout << it.first;
break;
}
}
temp = temp->next;
++count;
}
std::cout << std::endl;
}
void TestLRU_ints() {
lru_cache<int> cache(CACHE_CAPACITY);
bool addedNew = false;
addedNew = cache.put(1); //1
assert(addedNew);
addedNew = cache.put(2); //2, 1
assert(addedNew);
addedNew = cache.put(3); //3, 2, 1
assert(addedNew);
addedNew = cache.put(4); //4, 3, 2, 1
assert(addedNew);
addedNew = cache.put(2); //2, 4, 3, 1
assert(!addedNew);
addedNew = cache.put(2); //2, 4, 3, 1
assert(!addedNew);
addedNew = cache.put(4); //4, 2, 3, 1
assert(!addedNew);
addedNew = cache.put(1); //1, 4, 2, 3
assert(!addedNew);
addedNew = cache.put(1); //1, 4, 2, 3
assert(!addedNew);
addedNew = cache.put(3); //3, 1, 4, 2
assert(!addedNew);
addedNew = cache.put(8); //8, 3, 1, 4, 2
assert(addedNew);
addedNew = cache.put(0); //0, 8, 3, 1, 4, 2
assert(addedNew);
addedNew = cache.put(5); //5, 0, 8, 3, 1, 4, 2
assert(addedNew);
addedNew = cache.put(6); //6, 5, 0, 8, 3, 1, 4, 2
assert(addedNew);
addedNew = cache.put(2); //2, 6, 5, 0, 8, 3, 1, 4
assert(!addedNew);
addedNew = cache.put(9); //9, 2, 6, 5, 0, 8, 3, 1, 4
assert(addedNew);
addedNew = cache.put(7); //7, 9, 2, 6, 5, 0, 8, 3, 1, 4
assert(addedNew);
addedNew = cache.put(3); //3, 7, 9, 2, 6, 5, 0, 8, 1, 4
assert(!addedNew);
addedNew = cache.put(1); //1, 3, 7, 9, 2, 6, 5, 0, 8, 4
assert(!addedNew);
addedNew = cache.put(59); // 59, 1, 3, 7, 9, 2, 6, 5, 0, 8
assert(addedNew);
addedNew = cache.put(86); // 86, 59, 1, 3, 7, 9, 2, 6, 5, 0
assert(addedNew);
//Print current cache
std::cout << "cache size = " << cache.size() << std::endl;
print_cache(cache);
//Element exists, is mapped correctly, etc.
int test_key = 4;
bool exists = cache.exists(test_key) != nullptr;
std::cout << "Element " << test_key << " exists = " << exists << std::endl;
test_key = 9;
exists = cache.exists(test_key) != nullptr;
std::cout << "Element " << test_key << " exists = " << exists << std::endl;
}
void TestLRU_strings() {
lru_cache<std::string> cache;
cache.set_max_size(CACHE_CAPACITY);
bool addedNew = false;
addedNew = cache.put("mathtag.com"); //mathtag.com
assert(addedNew);
addedNew = cache.put("adnxs.com"); //adnxs.com, mathtag.com
assert(addedNew);
addedNew = cache.put("abmr.net"); //abmr.net, adnxs.com, mathtag.com
assert(addedNew);
addedNew = cache.put("doubleclick.net"); //doubleclick.net, abmr.net, adnxs.com, mathtag.com
assert(addedNew);
addedNew = cache.put("mathtag.com"); //mathtag.com, doubleclick.net, abmr.net, adnxs.com
assert(!addedNew);
addedNew = cache.put("mathtag.com"); //mathtag.com, doubleclick.net, abmr.net, adnxs.com
assert(!addedNew);
addedNew = cache.put("liverail.com"); //liverail.com, mathtag.com, doubleclick.net, abmr.net, adnxs.com
assert(addedNew);
addedNew = cache.put("doubleclick.net"); //doubleclick.net, liverail.com, mathtag.com, abmr.net, adnxs.com
assert(!addedNew);
addedNew = cache.put("quantserve.com"); //quantserve.com, doubleclick.net, liverail.com, mathtag.com, abmr.net, adnxs.com
assert(addedNew);
addedNew = cache.put("questionmarket.com"); //questionmarket.com, quantserve.com, doubleclick.net, liverail.com, mathtag.com, abmr.net, adnxs.com
assert(addedNew);
addedNew = cache.put("adadvisor.net"); //adadvisor.net, questionmarket.com, quantserve.com, doubleclick.net, liverail.com, mathtag.com, abmr.net, adnxs.com
assert(addedNew);
addedNew = cache.put("adsafeprotected.com"); //adsafeprotected.com, adadvisor.net, questionmarket.com, quantserve.com, doubleclick.net, liverail.com, mathtag.com, abmr.net, adnxs.com
assert(addedNew);
addedNew = cache.put("btrll.com"); //btrll.com, adsafeprotected.com, adadvisor.net, questionmarket.com, quantserve.com, doubleclick.net, liverail.com, mathtag.com, abmr.net, adnxs.com
assert(addedNew);
addedNew = cache.put("trafficmanager.net"); //trafficmanager.net, btrll.com, adsafeprotected.com, adadvisor.net, questionmarket.com, quantserve.com, doubleclick.net, liverail.com, mathtag.com, abmr.net
assert(addedNew);
//Print current cache
std::cout << "cache size = " << cache.size() << std::endl;
print_cache(cache);
//Element exists, is mapped correctly, etc.
std::string test_key = "doubleclick.net";
bool exists = cache.exists(test_key) != nullptr;
std::cout << "Element " << test_key << " exists = " << exists << std::endl;
test_key = "google.com";
exists = cache.exists(test_key) != nullptr;
std::cout << "Element " << test_key << " exists = " << exists << std::endl;
}
int main()
{
TestLRU_ints();
TestLRU_strings();
return 0;
}
Output:
$g++ -std=c++11 test_lru_cache.cpp -o test_lru_cache
$./test_lru_cache
cache size = 10
======= Current cache =======
86, 59, 1, 3, 7, 9, 2, 6, 5, 0
Element 4 exists = 0
Element 9 exists = 1
======= Current cache =======
trafficmanager.net, btrll.com, adsafeprotected.com, adadvisor.net, questionmarket.com, quantserve.com, doubleclick.net, liverail.com, mathtag.com, abmr.net
Element doubleclick.net exists = 1
Element google.com exists = 0
October 29th
Some couchdb IO operations
- To print couchDB document
curl localhost:5984/<my_db_directory>/<my_doc_name>
For example
curl localhost:5984/my_contacts/contact_popularity
- To delete a document
curl -X DELETE 'localhost:5984/capture/<id>?rev=<rev>'
where 'id' is the autogenerated document ID from the original POST and 'rev' is the current revision. For example
curl -X DELETE localhost:5984/my_contacts/contact_popularity?rev=2-8a6e0bf7d2603d02189b5d51619e022f
- To create an empty document
curl -X PUT localhost:5984/<my_db_directory>/<my_doc_name>
Forexample
curl -X PUT localhost:5984/my_contacts/contact_popularity
- To put a new document by hand
curl -X PUT localhost:5984/<my_db_directory>/<my_doc_name> -d <document>
For example
curl -X PUT localhost:5984/my_contacts/contact_popularity -d '{"_id":"contact_popularity",
"commit":{"gmt":"2015-10-30T01:01:55Z","local":"Thu Oct 29 18:01:55 2015"},
"Contacts": {
"A":{"City": "San Francisco", "Friends" : 698, "Posts" : 148},
"B":{"City": "Seattle", "Friends" : 486, "Posts" : 612}
}
}'
Go to September's log
Last modified: Thu Oct 29 18:37:29 PDT 2015