2019q1 Homework7 (skiplist)
===
contributed by < `martinxluptak` >

* Cache sizes and layout can be an important performance factor. Different memory layouts can have an impact on performance of an algorithm regardless of factors such as big-O notation. Algorithmic analysis usually neglects these differences.

* A cache-size oblivious data structure performs optimally regardless of underlying cache-sizes, matching the optimal case of algorithmic analysis.

* When designing such a data structure, we distinguish slow and fast access memory blocks. Slow access memory blocks can only be moved to the other block in fixed size chunks. This is called the cache-oblivious model.

* Algorithms that make good use of the cache have the following very important property: When we read a block of data, we make use of every byte in that block.

* Many Cache-oblivious algorithms will divide the problem into subproblems up to a point when a subproblem size fits into cache.

# Skiplist:
* Skiplist is a data structure consisting of a levelled linked list which.
* The first level is the original linked list. Each higher level mirrors a part of the members from the previous level.
* The number of elements on a level decreases exponentially, i.e. a list with 100 elements would see 4 levels with 100, 50, 25, 12 elements per level.
* During insertion of an element, its level is decided by a random roll.
* The randomness can cause an imbalance in contents of each level, but this effect perishes when more elements are added with the Law of Large Numbers and is well worth it in comparison to keeping a perfect balance such as in case of an AVL tree.

The idea of skiplist is to reduce cache reaches by

Let's take a look at a basic list and a skiplist and compare their performance.

The following test is performed with 10,000 elements over 100,000 random searches.

*** Validating tests/list_heavyload ***
CPU time inserting in list:0.000567
CPU time searching in list:4.953987
	[ Verified ]
  CC	tests/skip_heavyload.o
  LD	tests/skip_heavyload
*** Validating tests/skip_heavyload ***
NIL
CPU time inserting in skiplist:0.010130
CPU time searching in skiplist:0.190573
	[ Verified ]

We can see the `O(log n)` average case inumerably sped the search up, whereas the worst case search complexity remains `O(n)` for both structures.

Skiplist implementation can still see performance improvements. One such improvement is an unrolled skip list. Instead of linking each element, we opt to move elements together into chunks with two or more elements. This reduces the number of links when searching a list:

(Performance comparison still not done)