SkipList documentation

• Introduction
• Project
• Credits
• Installation
  • C++
  • Python
    • From PyPi
    • Development
• Examples
  • C++
  • Python
• Testing
  • C++
    • Using the Makefile
    • Using CMake
  • Python
  • Both C++ and Python
• Design and Implementation of the C++ Skip List
  • Design of the C++ Skip List
    • Search Algorithms
    • Insertion Algorithm
    • Removal Algorithm
    • Insertion and Removal Stability
  • Implementation Notes
    • Memory Management
    • Thread Safety
  • Code Layout
    • Other Files of Significance
  • Code Idioms
    • Prevent Copying
    • Reverse Loop of unsigned int
  • Worst Case Behaviour
  • Roads not Travelled
    • Key/Value Implementation
    • Adversarial Users
    • Optimisation: Re-index Nodes on Complete Traversal
    • Optimisation: Reuse removed nodes
    • Reference Counting
    • Use an Array of {skip_width, Node<T>*} rather than a vector
• Skip List Performance
  • C++ Performance
    • Time Performance
    • Space Complexity
    • Effect of a Biased Coin
    • Multi-threaded C++ Performance
  • Python Performance
    • Time Performance
    • Multi-Threaded Python Performance
• Computing a Rolling Median
  • Rolling Median in C++
    • Even Window Length
    • C++ Performance
  • Rolling Median in Python
    • Python Performance
  • Performance Comparison of C++ and Python
  • Rolling Median in Python with multiprocessing.shared_memory
    • Code
    • Performance
    • Memory Usage
  • Handling NaNs
    • Propogate the Exception
    • Make the Median NaN
    • Forward Filling
• Visualising a Skip List
  • Simple Example in C++
    • Inserting the Values 0 to 7
    • Inserting the Values 0 to 3 and Removing them Multiple Times
  • Simple Example in Python
• Biased Coin Skip List Visualisations
  • Fair coin, p(0.5)
  • 1:8, p(0.125)
  • 1:4, p(0.25)
  • 3:4, p(0.75)
• Some Notes on Testing
  • Test Code
    • C++ Functional Tests.
    • C++ Performance Tests.
    • Python Functional Tests.
  • Testing a Probabilistic Structure
• Skip List API
  • C++ API
    • Example in C++
    • Constructors
    • HeadNode::insert(const T &val)
    • HeadNode::remove(const T &val)
    • HeadNode::has(const T &val) const;
    • HeadNode::at(size_t index) const;
    • HeadNode::at(size_t index, size_t count, std::vector<T> &dest) const;
    • HeadNode::index(const T &value) const;
    • HeadNode::size() const
    • Specialised APIs
  • Python API
    • Example in Python
    • Module cSkipList
    • Class cSkipList.PySkipList
    • Constructor
    • PySkipList.has(val)
    • PySkipList.at(index)
    • PySkipList.at_seq(index, count)
    • PySkipList.index(value)
    • PySkipList.size()
    • PySkipList.insert(value)
    • PySkipList.remove(value)
    • Specialised APIs
• orderedstructs Python Reference
  • orderedstructs.SkipList
• TODO
  • Existing TODOs

Indices and tables

• Index

• Search Page