14
\$\begingroup\$

Skip lists are a probabilistic alternative to balanced trees, they are balanced by consulting a random number generator, that determines how many pointerscalled node level to successive elements a node will have.

Skip list is a simple data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, each skipping over fewer elements, as depicted on the following figure:

enter image description here

According to the paper this data structure offers same, in some cases even better performance of alternative data structures like: AVL trees, self adjusting trees, as one can see on the following table:

enter image description here

with relatively low implementation cost:

"However, implementing balanced trees is an exacting task and as a result balanced tree algorithms are rarely implemented except as part of a programming assignment in a data structures class. Skip lists are a simple data structure that can be used in place of balanced trees for most applications."

The following code implements a Skip List based on "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh.

Skip_list.h

#ifndef SKIP_LIST_H
#define SKIP_LIST_H 
//============================================================================== 
struct Skip_Node {
    int key;
    std::string value;

    // pointers to successor nodes
    std::vector<Skip_Node*> forward;

    Skip_Node (int k, const std::string& v, int level); 
};

//============================================================================== 
class Skip_list {
public:
    Skip_list ();
    ~Skip_list ();

    // non-modifying member functions
    void print ();
    Skip_Node* find (int searchKey);

    // modifying member functions
    void insert (int searchKey, std::string newValue);
    void erase (int searchKey); 
private:
    // pointer to first node
    Skip_Node* head;
    // last node
    Skip_Node* NIL;

    // implicitly used member functions
    int randomLevel (); 
    int nodeLevel(const std::vector<Skip_Node*>& v);
    Skip_Node* makeNode (int key, std::string val, int level);

    // data members  
    float probability;
    int maxLevel;
};

#include "Skip_list.cpp"
#endif

Skip_list.cpp

// Struct Skip_node member implementations
// constructor 
Skip_Node::Skip_Node (int k, const std::string& v, int level)
    :  key(k), value(v)
{
    for (int i = 0; i < level; ++i) forward.emplace_back(nullptr);
} 

//==============================================================================
// Class Skip_list member implementations
// constructor
Skip_list::Skip_list()
    : probability(0.5), maxLevel(16)
{
     // Initialize the head of the skip list

     // smallest possible key
     int headKey = std::numeric_limits<int>::min();
     head = new Skip_Node(headKey, "head", maxLevel);

     // Initialize the last element of the list

     // largest possible key
     int nilKey = std::numeric_limits<int>::max();
     NIL = new Skip_Node(nilKey, "NIL", maxLevel);

     // Connect start to end
     // connect all the levels/forward pointers of the header to NIL
     for (size_t i = 0; i < head->forward.size(); ++i) {
         head->forward[i] = NIL;
     }
}

// destructor
Skip_list::~Skip_list () {
    delete head;
    delete NIL;
}

// Helper functions
/*
    Function: randomLevel()
    Use: implicit in class Skip_list
    It generates node levels in the range
    [1, maxLevel). 

    It uses rand() scaled by its maximum 
    value: RAND_MAX, so that the randomly 
    generated numbers are within [0,1).
*/
int Skip_list::randomLevel () {
    int v = 1;

    while ((((double)std::rand() / RAND_MAX)) < probability && 
           std::abs(v) < maxLevel) {

        v += 1;
    }
    return abs(v);
}

/*
    Function: nodeLevel()
    Use: Implicitly in most of the member functions.

    It returns the number of non-null pointers
    corresponding to the level of the current node.
    (the node that contains the checked vector of 
    forward pointers)

    If list empty returns 1.
*/
int Skip_list::nodeLevel (const std::vector<Skip_Node*>& v) {
    int currentLevel = 1;
    // last element's key is the largest
    int nilKey = std::numeric_limits<int>::max();

    if (v[0]->key == nilKey) {
        return currentLevel;
    }

    for (size_t i = 0; i < v.size(); ++i) {

        if (v[i] != nullptr && v[i]->key != nilKey) {
            ++currentLevel;
        } else { 
            break;
        }
    }
    return currentLevel;
}

// Non-modifying member functions
/*
    Function: print()
    Use: skip_list_obj.print();

    It prints the key, value, level
    of each node of the skip list.

    Prints two nodes per line.
*/
void Skip_list::print () {
    Skip_Node* list = head;
    int lineLenght = 1;

    std::cout <<"{";

    while (list->forward[0] != nullptr) {
        std::cout <<"value: "<< list->forward[0]->value
                  <<", key: "<< list->forward[0]->key
                  <<", level: "<< nodeLevel(list->forward); 

        list = list->forward[0];

        if (list->forward[0] != nullptr) std::cout <<" : ";

        if (++lineLenght % 2 == 0) std::cout <<"\n";
    }
    std::cout <<"}\n";
}

/*
    Function: find()
    Use: Skip_Node* found = skip_list_obj.find(searchKey);

    It searches the skip list and
    returns the element corresponding 
    to the searchKey; otherwise it returns
    failure, in the form of null pointer.
*/
Skip_Node* Skip_list::find(int searchKey) {
    Skip_Node* x = head;
    unsigned int currentMaximum = nodeLevel(head->forward);

    for (unsigned int i = currentMaximum; i-- > 0;) {
        while (x->forward[i] != nullptr && x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }   
    }
    x = x->forward[0];

    if (x->key == searchKey) {
        return x;
    } else {
        return nullptr;
    }
} 

// Modifying member functions
/*
    Function: makeNode ()
    Use: Implicitly in member function insert().

    It wraps the Skip_Node constructor which creates
    a node on the heap and returns a pointer to it. 
*/
Skip_Node* Skip_list::makeNode (int key, std::string val, int level) {
    return new Skip_Node(key, val, level);
}

/*
    Function: insert();
    Use: void insert(searchKey, newValue);

    It searches the skip list for elements
    with seachKey, if there is an element
    with that key its value is reassigned to the 
    newValue, otherwise it creates and splices
    a new node, of random level.
*/
void Skip_list::insert(int searchKey, std::string newValue) {
    // reassign if node exists 
    Skip_Node* x = nullptr;
    x = find(searchKey);
    if (x) {
        x->value = newValue;
        return;
    }

    // vector of pointers that needs to be updated to account for the new node
    std::vector<Skip_Node*> update(head->forward);
    unsigned int currentMaximum = nodeLevel(head->forward);
    x = head;

    // search the list 
    for (unsigned int i = currentMaximum; i-- > 0;) {

        while (x->forward[i] != nullptr && x->forward[i]->key < searchKey) {

            x = x->forward[i];
        }
        update[i] = x;
    }
    x = x->forward[0];

    // create new node
    int newNodeLevel = 1;
    if (x->key != searchKey) {

        newNodeLevel = randomLevel();
        int currentLevel = nodeLevel(update);

        if (newNodeLevel > currentLevel) {

            for (int i = currentLevel + 1; i < newNodeLevel; ++i) {

                update[i] = head;
            }   
        }
        x = makeNode(searchKey, newValue, newNodeLevel);
    }

    // connect pointers of predecessors and new node to successors
    for (int i = 0; i < newNodeLevel; ++i) {

        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
    }
}

/*
    Function: delete_node()
    Use: skip_list_obj.erase(searchKey)

    It deletes the element containing 
   searchKey, if it exists.
*/
void Skip_list::erase (int searchKey) {
    // vector of pointers that needs to be updated to account for the deleted node
    std::vector<Skip_Node*> update(head->forward);
    Skip_Node* x = head;
    unsigned int currentMaximum = nodeLevel(head->forward);

    // search and update pointers
    for (unsigned int i = currentMaximum; i-- > 0;) {

        while (x->forward[i] != nullptr && x->forward[i]->key < searchKey) {

            x = x->forward[i];
        }
        update[i] = x;
    }
    x = x->forward[0];

    // update pointers and delete node 
    if (x->key == searchKey) {
        for (size_t i = 0; i < update.size(); ++i) {

            if (update[i]->forward[i] != x) {

                break;
            }
            update[i]->forward[i] = x->forward[i];
        }
        delete x;        
    }    
}

main

#include <iostream>
#include <time.h>
#include <string>
#include <sstream>
#include <vector>

#include "Skip_list.h"

//==================================================
int main () {

    // 1.Initialize an empty Skip_list object
    Skip_list s;

    // 2. insert()
    for (int i = 0; i < 50; ++i){

        std::stringstream ss;
        ss << i;

        s.insert(i, ss.str());
    }

    // 2a. print()
    s.print();

    // 3. find()
    Skip_Node* f = nullptr;
    f = s.find(10);
    if (f) std::cout <<"Node found!\nvalue: "<< f->value <<'\n';
    else std::cout <<"Node NOT found!\n";

    // 4. insert() - reassign
    s.insert(40, "TEST");

    // 4a. print()
    s.print();

    // 5. erase()
    s.erase(40);

    // 5a. print();
    s.print();

    std::cout << "\nDone!\n";
    getchar();   
}

I would like suggestions on how to improve the above code and correct any bad code practices.


Note: This is a first draft of solution to Exercise 11 Chapter 18 of C++ Programming: Principles and Practice by B. Stroustrup

Exercise 11 : Look up (e.g. on the web) skip list and implement that kind of list. This is not an easy exercise.

\$\endgroup\$
  • \$\begingroup\$ How does your fast skip list compare to the 'slow' tree implementation that underlies standard library containers like map<>? It's easy to write containers that are several orders of magnitude faster, since map<> has nothing to recommend it apart from its convenience; its performance starts low and then it goes down the drain. However, I'd wager that your code starts slower still and remains consistently behind. When Stroustrup said that skip list aren't easy he hit the nail on the head, since skip lists require careful engineering in order to shine. And engineering needs purpose/direction \$\endgroup\$ – DarthGizka Jan 10 '16 at 15:08
  • \$\begingroup\$ @DarthGizka I agree with what you argue. I personally don't claim anything and don't denounce any other data structure. As you said, everything depends on the purpose/ cost, etc. All I seek is some constructive criticism :). \$\endgroup\$ – Ziezi Jan 10 '16 at 15:17
  • 2
    \$\begingroup\$ However, implementing balanced trees is an exacting task and as a result balanced tree algorithms are rarely implemented and because we already have perfect examples implemented for us in the standard std::map and std::set \$\endgroup\$ – Martin York Jan 10 '16 at 16:48
  • 1
    \$\begingroup\$ Am I missing something or are you leaking all your nodes upon destruction except head and NIL? \$\endgroup\$ – MikeMB Jan 10 '16 at 17:30
  • 1
    \$\begingroup\$ Any reason you didn't make your non modifying methods const at the end of the signature? As far as I'm aware that expresses their non-modifying nature in syntax? \$\endgroup\$ – J_mie6 Jan 11 '16 at 10:34
5
\$\begingroup\$

Your code is a real pleasure to read because it is clean and well written - I wish more of the code here at CR were like this.

Stilistically the focus could be improved by factoring all key properties into a traits class. This would make the skip list code key-agnostic, so that it could be used without change for different kinds of key. This can be advantageous even before the class is turned into a template, and it would make the step from concrete class to a class template a lot easier.

At the moment the maximum node height is fixed; this means it is bound to be overkill for small numbers of elements and insufficient for big numbers. Most of the code could simply look at the head node to find the current max but the insert code would have to decide whether an increase is warranted (i.e. whenever the element count gains a new 1-bit at the front then a new 'express-way' should be opened by increasing the head node height). This would give more even performance over greater ranges of element counts than is currently the case.

Using a std::vector in every node gives a lot of flexibility and greatly facilitates experimentation. However, it also makes the skip list very resource-hungry. Since height of nodes is fixed at creation (apart from head nodes, but those can be dealt with differently) an alternative for high-performance production implementations would be a special-purpose allocator in the spirit of buddy systems.

It can be very instructive to run systematic performance tests with geometrically increasing element counts (e.g. 10^1, 10^2, ..., 10^10) separately for search, insert and delete, and to compare the results to (sorted) std::vector<>, std::map<>, std::unordered_map<> and so on, to get a feel for how skip lists behave. Unfortunately there's no B-tree template in the standard, so there's no data structure available for comparison that can take a bit of load (i.e. that's suitable for more than homoeopathic numbers of elements).

It can be similarly instructive to compare expected behaviour to actual behaviour. E.g. compare theoretically predicted comparison counts to actual comparison counts by instrumenting the code, for example with an interposer class for the key traits that wraps the less() predicate.

There's a well-written article on skip lists on MSDN that is very good for getting into the spirit of things. It's part of a series of articles on data structures: Part 4: Building a Better Binary Search Tree It starts with binary trees and lists but more than half of it is devoted to skip lists.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your time and help, much appreciated! Making the code more generic it is surely a future plan and I'll consider your suggestions. The idea for making the maximum level dynamic and function of the length of the list is really a great idea. Regarding the use of the memory consuming vector, it will probably replaced with an array of pointers (I'll research what the buddy system is). Finally, I will try and test it both against the standard library containers in the indicated increasing order and in comparison with the theoretical predictions of the paper. \$\endgroup\$ – Ziezi Jan 10 '16 at 17:40
  • 1
    \$\begingroup\$ The spirit of buddy system fits skip lists insofar as a skip list of order 20 would need nodes of 20 different sizes: lots of nodes with 1 pointer, half as much with 2 pointers, and so on. Hence you could have an allocator with 20 free lists which doles out nodes that have been allocated in bigger blocks, one for each node size (or for each group of sizes modulo some alignment). But that's for when you want to build a screaming jet engine. Don't worry about it now. The general-purpose allocator of modern C++ runtimes is pretty good, and at the moment you've got more interesting fish to fry... \$\endgroup\$ – DarthGizka Jan 10 '16 at 18:47
1
\$\begingroup\$

First of all, as DarthGizka mentioned, your code is mostly easy to read and understand and except for the memory leak I mentioned in the comments I don't see any errors.

I can't really contribute on the general question, of how effective skiplists are or what would be the best algorithm to determine the height of each node, however, I think there are still a few things that can be improved in your current implementation:

General Interface

I believe this is more of a proof-of-concept, but on if you go on with it, you should probably strive to make a interface more similar to STL-like associative containers. Meaning in particular: providing iterators, template the class on the member (and key type), providing the typical typedefs and functions (e.g. size()) etc. As mentioned by others, this would also make it easier to compare it to other data structures.

Making Skip_Node a nested class

Skip_Node is an implementation detail that should not be visible outside of the class, so you can just make it an nested class of Skip_list.

Const correctness and static member functions

You have a few member functions that should be specified const (print, find) or even static (nodeLevel, makeNode).

Structure

It seems that you assume, that you will never add an item to the container with the same key as the NIL key. If that is the case, you should probably document and assert that. However, this also means, that there is no need to treat the NIL node in a special way. More to the point: The main reason for using dedicated head and NIL nodes is so that your member functions don't have to care about empty lists, or whether a new node is the first or last node in the list.
If you embrace this concept, then you can e.g. make nodeLevel a one liner that simply returns the size of the vector.

Also, insert and erase seem a little long to me and share a nontrivial amount of code, so you might want to refactor the common functionality in a separate function.

Finally, std::vector seems to be a pretty heavy member for the list nodes (due to the size overhead and the additional memory allocation). If the maximum level is a compiletime constant, you could try e.g. a member array instead (possibly using multiple different node classes of different sizes, as suggested by DarthGizka).

Dead Code

With the above in mind and when you carefully think, about what invariants hold at each line of code, you might see, that there is a lot of test that always evaluate to true or false and code that never gets executed.

Comments

Nice to see a thoroughly commented code. Personally I would write the function documentation at the point of declaration (in the class definition) and I also try to avoid to write comments basically repeat the code the code.

After reviewing and refactoring your code, I ended up with the following (some of the changes are just personal style):

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>


class Skip_list {
public:
    Skip_list();
    ~Skip_list();

    // non-modifying member functions

    /*
    It prints the key, value, level
    of each node of the skip list.

    Prints two nodes per line.
    */
    void print() const;

    /*  
    It searches the skip list and
    returns the element corresponding
    to the searchKey; otherwise it returns
    failure, in the form of null pointer.
    */
    std::string* find(int searchKey) const;

    // modifying member functions

    /*
    It searches the skip list for elements
    with seachKey, if there is an element
    with that key its value is reassigned to the
    newValue, otherwise it creates and splices
    a new node, of random level.
    */
    void insert(int searchKey, const std::string& newValue);

    /*
    It deletes the element containing
    searchKey, if it exists.
    */
    void erase(int searchKey);

private:

    struct Node {
        int key;
        std::string value;

        // pointers to successor nodes
        std::vector<Node*> forward;

        Node(int k, const std::string& v, int level): 
            key(k), value(v),forward(level,nullptr)
        {}          
    };  

    // Generates node levels in the range [1, maxLevel).    
    int randomLevel() const;    

    //Returns number of incoming and outgoing pointers
    static int nodeLevel(const Node* v);

    //creates a node on the heap and returns a pointer to it.   
    static Node* makeNode(int key, std::string val, int level);

    // Returns the first node for which node->key < searchKey is false  
    Node* lower_bound(int searchKey) const ;

    /*
    * Returns a collection of Pointers to Nodes
    * result[i] hold the last node of level i+1 for which result[i]->key < searchKey is true
    */
    std::vector<Node*> predecessors(int searchKey) const ;

    // data members 
    const float probability;
    const int maxLevel;
    Node* head; // pointer to first node
    Node* NIL;  // last node
};


//==============================================================================
// Class Skip_list member implementations

Skip_list::Skip_list() :
    probability(0.5), 
    maxLevel(16)
{   
    int headKey = std::numeric_limits<int>::min();
    head = new Node(headKey, "head", maxLevel); 

    int nilKey = std::numeric_limits<int>::max();
    NIL = new Node(nilKey, "NIL", maxLevel);

    std::fill(head->forward.begin(), head->forward.end(), NIL);
}

Skip_list::~Skip_list() {
    auto node = head;
    while (node->forward[0]) {
        auto tmp = node;
        node = node->forward[0];
        delete tmp;
    }
    delete node;
}

std::string* Skip_list::find(int searchKey) const {
    std::string* res{};
    if (auto x = lower_bound(searchKey)) {
        if (x->key == searchKey && x!=NIL) {
            res = &(x->value);
        }
    } 
    return res; 
}

void Skip_list::print() const {
    Node* list = head->forward[0];
    int lineLenght = 0;

    std::cout << "{";

    while (list != NIL) {
        std::cout << "value: " << list->value
            << ", key: " << list->key
            << ", level: " << nodeLevel(list);

        list = list->forward[0];

        if (list != NIL) std::cout << " : ";

        if (++lineLenght % 2 == 0) std::cout << "\n";
    }
    std::cout << "}\n";
}

void Skip_list::insert(int searchKey, const std::string& newValue) {
    auto preds = predecessors(searchKey);

    {//reassign value if node exists and return
        auto next = preds[0]->forward[0];
        if (next->key == searchKey && next != NIL) {
            next->value = newValue;
            return;
        }
    }

    // create new node
    const int newNodeLevel = randomLevel();
    auto newNodePtr = makeNode(searchKey, newValue, newNodeLevel);

    // connect pointers of predecessors and new node to respective successors
    for (int i = 0; i < newNodeLevel; ++i) {
        newNodePtr->forward[i] = preds[i]->forward[i];
        preds[i]->forward[i] = newNodePtr;
    }   
}


void Skip_list::erase(int searchKey) {
    auto preds = predecessors(searchKey);

    //check if the node exists
    auto node = preds[0]->forward[0];   
    if (node->key != searchKey || node == NIL) {
        return;
    }

    // update pointers and delete node 
    for (size_t i = 0; i < nodeLevel(node); ++i) {
        preds[i]->forward[i] = node->forward[i];
    }
    delete node;        
}

//###### private member functions ######
int Skip_list::nodeLevel(const Node* v) {
    return v->forward.size();
}

Skip_list::Node* Skip_list::makeNode(int key, std::string val, int level)  {
    return new Node(key, val, level);
}

int Skip_list::randomLevel() const {
    int v = 1;
    while (((double)std::rand() / RAND_MAX) < probability &&
        v < maxLevel) {
        v++;
    }
    return v;
}

Skip_list::Node* Skip_list::lower_bound(int searchKey) const{
    Node* x = head;

    for (unsigned int i = nodeLevel(head); i-- > 0;) {
        while ( x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }
    }
    return x->forward[0];
}

std::vector<Skip_list::Node*> Skip_list::predecessors(int searchKey) const {
    std::vector<Node*> result(nodeLevel(head),nullptr);
    Node* x = head;

    for (unsigned int i = nodeLevel(head); i-- > 0;) {
        while (x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }
        result[i] = x;
    }
    return result;
}



//==================================================
int main() {

    // 1.Initialize an empty Skip_list object
    Skip_list s;

    // 2. insert()
    for (int i = 0; i < 50; ++i) {
        std::stringstream ss;
        ss << i;

        s.insert(i, ss.str());
    }

    // 2a. print()
    s.print();
    std::cout << std::endl;

    // 3. find()        
    auto f = s.find(10);
    if (f) std::cout << "Node found!\nvalue: " << f << '\n';
    else std::cout << "Node NOT found!\n";

    // 4. insert() - reassign
    s.insert(40, "TEST");

    // 4a. print()
    s.print();
    std::cout << std::endl;

    // 5. erase()
    s.erase(40);

    // 5a. print();
    s.print();
    std::cout << std::endl;

    std::cout << "\nDone!\n";
    getchar();
}
\$\endgroup\$
  • \$\begingroup\$ Gratitudes for your remarks, insights and help! I've integrated Node within the private members of the Skip_list, as you suggested, added const ( and static ) specifier in front of the non-modifying members. Additionally, as you said there were a lot of lines with meaningless code or code that never gets used, which I've removed. Finally, after converting the complex search for loops into new members predecessors(), lower_bound() the code looks really neat and easy to understand. \$\endgroup\$ – Ziezi Jan 11 '16 at 15:01
  • \$\begingroup\$ I found one line in erase() difficult to understand (check the suggested edit). Apologies if I'm wrong. \$\endgroup\$ – Ziezi Jan 11 '16 at 15:08
  • 1
    \$\begingroup\$ @simplicisveritatis: Yes sorry. Apparently I forgot to negate that expression, when I changed from if(..) {doStuff} to if(...){early exit}; doStuff \$\endgroup\$ – MikeMB Jan 11 '16 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.