Saturday, September 10, 2011

Skip lists in Ruby

Skip lists are an interesting data structure that you can use as a substitute of balanced trees. This relatively new data structure was invented by William Pugh in 1990. According to his paper on skip lists :

Skip lists are a data structure that can be used in place of balanced trees.
Skip lists use probabilistic balancing rather than strictly enforced balancing
and as a result the algorithms for insertion and deletion in skip lists are
much simpler and significantly faster than equivalent algorithms for
balanced trees.

I have tried to implement skip lists in Ruby. It is not super hard because the paper has pseudocode and the algorithm is rather intuitive.

class Node
  attr_accessor :key
  attr_accessor :value
  attr_accessor :forward

  def initialize(k, v = nil)
    @key = k 
    @value = v.nil? ? k : v 
    @forward = []
  end
end

class SkipList
  attr_accessor :level
  attr_accessor :header
  
  def initialize
   @header = Node.new(1) 
   @level = 0
   @max_level = 3 
   @p = 0.5 
   @node_nil = Node.new(1000000)
   @header.forward[0] = @node_nil
  end
  
  def search(search_key)
    x = @header
    @level.downto(0) do |i|
      while x.forward[i].key < search_key do
        x = x.forward[i]
      end
    end    
    x = x.forward[0]
    if x.key == search_key
      return x.value
    else
      return nil
    end
  end

  def random_level
    v = 0
    while rand < @p && v < @max_level
      v += 1
    end
    v
  end

  def insert(search_key, new_value = nil)
    new_value = search_key if new_value.nil? 
    update = []
    x = @header
    @level.downto(0) do |i|
      while x.forward[i].key < search_key do
        x = x.forward[i]
      end
      update[i] = x
    end    
    x = x.forward[0]
    if x.key == search_key
      x.value = new_value
    else
      v = random_level
      if v > @level 
        (@level + 1).upto(v) do |i|
          update[i] = @header
          @header.forward[i] = @node_nil
        end
        @level = v
      end
      x = Node.new(search_key, new_value) 
      0.upto(v) do |i|
        x.forward[i] = update[i].forward[i]
        update[i].forward[i] = x
      end
    end
  end
end

I have not implemented the delete method yet. It is similar to insert method and won't be so difficult to code. If you are interested, why don't you try to write it on your own?

3 comments:

light24bulbs said...

Hey! Nice, I can tell what this is doing unlike the more popular ruby skiplist which was hard for me to read. I've copied your source to try to add dynamic toplevel finding, delete, and speed up search as much as possible with link-lengths. I would have rather done a repository fork. Does this have a repository?

light24bulbs said...

My skiplist gem that is loosely based off this can be found here:
https://github.com/light24bulbs/dynamic-skiplist
Turned out to be way way faster than the other one I mentioned. I say "loosely" because I added a ton of features

Eiji Sakai a.k.a. elm200 said...

Thank you for your comments, light24bulbs. I have just looked at your github repository. I am happy to see my blog entry help you a little bit.