C++

Forum

 
Randomized SkipList Implementation

Mae4ashy (29)
Good Afternoon!

I'm currently implementing a randomized skip list and don't know what's going wrong here. My insert function isn't inserting.

Here is my code so far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
void SkipList::insert(int value) {
  
  std::random_device r;
  std::default_random_engine e(r());
  std::uniform_int_distribution<int>uniform(0,1);
  
  Node* current = this->head;
  std::vector<Node*> update (this->max_level_+1, 0);
  
  //Searching
  for(int i = this->head->level()-1; i>=0; i--){
    while(current -> forward.at(i) != nullptr && current -> forward.at(i)->value < value){
      current = current -> forward.at(i);
    }
    update.at(i) = current;
   }
  
  current = current -> forward.at(0); //put back to level zero for insertion

  int count = 0;
  if(current == nullptr || current -> value != value) { //random level
    int r = uniform(e);
    while(r == 1 && count < 16){
      ++count;
      r = uniform(e);
    }

    std::size_t rlevel = count;
  
    Node* n = new Node(value,rlevel);
    
   for(std::size_t i=0; i<rlevel; i++){ //insert new node
      n->forward.at(i) = update.at(i) -> forward.at(i);
      update.at(i)->forward.at(i) = n;
    }
  }
    
}


As for the Skiplist-Class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#include <vector>

class SkipList {
  public:
    // A node represents the whole column of element occurences on levels [1..level].
    class Node {
      public:
        int value;
    
        // pointers to successor nodes
        std::vector<Node*> forward;

        Node(int v, std::size_t level)
          : value(v), forward(level, nullptr) {}
    
        std::size_t level() const {
            return forward.size();
        }
    };

  public:
    SkipList() : max_level_(16) {
        head = new Node(0, max_level_); 
        std::fill(head->forward.begin(), head->forward.end(), nullptr);
    }

    ~SkipList();
    
  private:
    // data members
    const std::size_t max_level_;
    Node* head; // pointer to first node
};


There is an Iterator defined as well, but that works just fine :).

I hope you can help me and thank you in advance!
Mae
coder777 (8444)
How is the insert(...) supposed to work?

On line 12 it is < but after that it is random?

By the way: You could let uniform() provide a number between 0...16.
Mae4ashy (29)
The new node is supposed to be inserted at the place where the values before are lower and the values after higher.
So my idea was to store the nodes that come before the insertion place in the vector update, so that i can insert the new node right after update and adjust the pointers accordingly.

And yes, i actually coud let uniform provide a number between 0 and 16, thanks :D.
Mae4ashy (29)
Okay, so i adjusted my code like this and strangely sometimes it is working well and sometimes it is only inserting some of the values i want to insert.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
void SkipList::insert(int value) {
  
  std::random_device r;
  std::default_random_engine e(r());
  std::uniform_int_distribution<int>uniform(0,16);
  
  Node* current = this->head;
  std::vector<Node*> update (this->max_level_+1, 0);
  
  //Suchfunktion
  for(int i = this->head->level()-1; i>=0; i--){
    while(current -> forward.at(i) != nullptr && current -> forward.at(i)->value < value){
      current = current -> forward.at(i);
    }
    update.at(i) = current;
   }
  
  current = current -> forward.at(0);

   std::size_t rlevel = uniform(e);
  
    Node* n = new Node(value,rlevel);
    
   for(std::size_t i=0; i<rlevel; i++){
      n->forward.at(i) = update.at(i) -> forward.at(i);
      update.at(i)->forward.at(i) = n;
    }
}


Does anyone maybe know what the problem is?
(Duplicates are allowed and should be inserted as well)
seeplus (6597)
and tracing through the code and showing values using the debugger shows an issue to be where?
Mae4ashy (29)
I think the issue is after line 22 in inserting the new node.
Copying the values into the update vector seems to be working fine.
dhayden (5798)
The code works for me.

I see that level() returns 1 for the bottom level, not 0. That might be throwing off some other code.

I added a print() method to show the skiplist and a simple main() to read numbers from cin, insert them, and then print the list after each insertion. With this input:
50
3
7
10
5
6


I get this output:
After adding 50:
Level 15: 0
Level 14: 0
Level 13: 0
Level 12: 0
Level 11: 0
Level 10: 0
Level 9: 0
Level 8: 0
Level 7: 0
Level 6: 0
Level 5: 0
Level 4: 0
Level 3: 0 50
Level 2: 0 50
Level 1: 0 50
Level 0: 0 50

After adding 3:
Level 15: 0
Level 14: 0
Level 13: 0
Level 12: 0
Level 11: 0
Level 10: 0
Level 9: 0
Level 8: 0 3
Level 7: 0 3
Level 6: 0 3
Level 5: 0 3
Level 4: 0 3
Level 3: 0 3 50
Level 2: 0 3 50
Level 1: 0 3 50
Level 0: 0 3 50

After adding 7:
Level 15: 0
Level 14: 0
Level 13: 0
Level 12: 0 7
Level 11: 0 7
Level 10: 0 7
Level 9: 0 7
Level 8: 0 3 7
Level 7: 0 3 7
Level 6: 0 3 7
Level 5: 0 3 7
Level 4: 0 3 7
Level 3: 0 3 7 50
Level 2: 0 3 7 50
Level 1: 0 3 7 50
Level 0: 0 3 7 50

After adding 10:
Level 15: 0
Level 14: 0
Level 13: 0
Level 12: 0 7
Level 11: 0 7
Level 10: 0 7
Level 9: 0 7 10
Level 8: 0 3 7 10
Level 7: 0 3 7 10
Level 6: 0 3 7 10
Level 5: 0 3 7 10
Level 4: 0 3 7 10
Level 3: 0 3 7 10 50
Level 2: 0 3 7 10 50
Level 1: 0 3 7 10 50
Level 0: 0 3 7 10 50

After adding 5:
Level 15: 0
Level 14: 0
Level 13: 0
Level 12: 0 5 7
Level 11: 0 5 7
Level 10: 0 5 7
Level 9: 0 5 7 10
Level 8: 0 3 5 7 10
Level 7: 0 3 5 7 10
Level 6: 0 3 5 7 10
Level 5: 0 3 5 7 10
Level 4: 0 3 5 7 10
Level 3: 0 3 5 7 10 50
Level 2: 0 3 5 7 10 50
Level 1: 0 3 5 7 10 50
Level 0: 0 3 5 7 10 50

After adding 6:
Level 15: 0 6
Level 14: 0 6
Level 13: 0 6
Level 12: 0 5 6 7
Level 11: 0 5 6 7
Level 10: 0 5 6 7
Level 9: 0 5 6 7 10
Level 8: 0 3 5 6 7 10
Level 7: 0 3 5 6 7 10
Level 6: 0 3 5 6 7 10
Level 5: 0 3 5 6 7 10
Level 4: 0 3 5 6 7 10
Level 3: 0 3 5 6 7 10 50
Level 2: 0 3 5 6 7 10 50
Level 1: 0 3 5 6 7 10 50
Level 0: 0 3 5 6 7 10 50


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
#include <vector>
#include <iostream>
#include <random>

class SkipList {
  public:
    // A node represents the whole column of element occurences on levels [1..level].
    void insert(int value);
    void print(std::ostream &os);
    
    class Node {
      public:
        int value;
    
        // pointers to successor nodes
        std::vector<Node*> forward;

        Node(int v, std::size_t level)
          : value(v), forward(level, nullptr) {}
    
	// Bottom level is 1, not 0
        std::size_t level() const {
            return forward.size();
        }
    };

  public:
    SkipList() : max_level_(16) {
        head = new Node(0, max_level_); 
        std::fill(head->forward.begin(), head->forward.end(), nullptr);
    }

    ~SkipList() {};		// for now
    
  private:
    // data members
    const std::size_t max_level_; // really numLevels?
    Node* head; // pointer to first node
};


void SkipList::insert(int value) {
  
  std::random_device r;
  std::default_random_engine e(r());
  std::uniform_int_distribution<int>uniform(0,16);
  
  Node* current = this->head;
  std::vector<Node*> update (this->max_level_+1, 0);
  
  //Suchfunktion
  for(int i = this->head->level()-1; i>=0; i--){
    while(current -> forward.at(i) != nullptr && current -> forward.at(i)->value < value){
      current = current -> forward.at(i);
    }
    update.at(i) = current;
   }
  
  current = current -> forward.at(0);

   std::size_t rlevel = uniform(e);
  
    Node* n = new Node(value,rlevel);
    
   for(std::size_t i=0; i<rlevel; i++){
      n->forward.at(i) = update.at(i) -> forward.at(i);
      update.at(i)->forward.at(i) = n;
    }
}

void SkipList::print(std::ostream &os)
{
    for (int i= head->forward.size(); i-- > 0;) {
	os << "Level " << i << ":";
	for (Node *n = head; n; n = n->forward[i]) {
	    os << ' ' << n->value;
	}
	os << '\n';
    }
}


int main()
{
    int value;
    SkipList slist;
    while (std::cin >> value) {
	slist.insert(value);
	std::cout << "\nAfter adding " << value << ":\n";
	slist.print(std::cout);
    }
}


Mae4ashy (29)
Oh wow, thats strange. But thanks for your help, then I'll work on my other code first :D.

Edit: it's working very well now after i changed uniform(0,16) to (1,16), so your guess was right, thanks a lot!
Last edited on
Mae4ashy (29)
Okay, here's another question regarding my erase function.
It is working very well for small amounts of data. But as soon as i let the programm process bigger amounts between 100.000 and 200.000 there is a Segmentation fault.

Here is my code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
void SkipList::erase(int value) {
  
  Node* current = this->head;
  std::vector<Node*> update (this->max_level_+1, 0);
  
  
  //Searching
  for(int i = this->head->level()-1; i>=0; i--){
    while(current -> forward.at(i) != nullptr && current -> forward.at(i)->value < value){
      current = current -> forward.at(i);
    }
    update.at(i) = current;
   }
   
   current = current -> forward.at(0);
   Node* temp = current;
   

   if(current->forward.at(0)==0){ //in case it is the last element of the SkipList
     for(std::size_t i=0; i<this->head->level();i++){
       if(update.at(i)->forward.at(i) != current)
          break;
        update.at(i)->forward.at(i) = current->forward.at(i);
      
     }
     delete current;
   }
   
  while(current->value == value){ //delete all Nodes with the value 'value'
     for(std::size_t i=0; i<this->head->level();i++){
       if(update.at(i)->forward.at(i) != current)
          break;
        update.at(i)->forward.at(i) = current->forward.at(i);
      
     }
     temp = current;
     current = current -> forward.at(0);
     delete temp;

   }
   
}


Does anyone know where the problem is? Cause it isn't really possible to debug this using std::cerr and strangely smaller cases are working fine.

I really appreciate your help, thanks a lot :)
Last edited on
dhayden (5798)
Line 15 can set current to NULL. There may be other problems, but that one struck me first.
Mae4ashy (29)
Ahh yes, i didn't see that. I edited like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
void SkipList::erase(int value) {
  
  Node* current = this->head;
  std::vector<Node*> update (this->max_level_+1, 0);

  for(int i = this->head->level()-1; i>=0; i--){
    while(current -> forward.at(i) != nullptr && current -> forward.at(i)->value < value){
      current = current -> forward.at(i);
    }
    update.at(i) = current;
  }
   
   current = current -> forward.at(0);
   
   Node* temp = current;
   
   if(current == nullptr){ //this is different
     return;
   }
   
   if(current->forward.at(0)==nullptr && current->value == value){ //this as well
     for(std::size_t i=0; i<current->level();i++){
       if(update.at(i)->forward.at(i) != current)
          break;
        if(update.at(i)->forward.at(i) == current){
          update.at(i)->forward.at(i) = current->forward.at(i);
        }
     }
     delete current;
     return;
   }
   
  while(current->value == value){
     for(std::size_t i=0; i<current->level();i++){
       if(update.at(i)->forward.at(i) != current)
          break;
        if(update.at(i)->forward.at(i) == current){
          update.at(i)->forward.at(i) = current->forward.at(i);
        }
      
     }
     temp = current;
     current = current -> forward.at(0);
     delete temp;

   }
   
}


Now it is working better, but still doing segmentation fault for big data amounts :)
Last edited on
seeplus (6597)
Doesn't the same null issue could also happen a L43? so shouldn't the while condition L33 also check that current isn't nullptr?
Mae4ashy (29)
Thanks a lot, that was the problem!! Oh wow, i think i wouldn't have found it all alone, so thank you very much :)
Topic archived. No new replies allowed.