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?

Visiting Goole

Yesterday I visited Google's headquarters to meet one of my acquaintances in US. He works for them as a software engineer. The Google's offices - actually they call them campuses like ones in college - were just overwhelmingly beautiful and affluent. As I have heard before, there were a plenty of decent restaurants and cafes inside the campuses and all foods and drinks are served to employees and visitors for free of charge.

I also got into the inside of office buildings and saw how employees work there. Their working desks were rather ordinary for North America, separated with cubicles (but the walls were semitransparent so that they won't feel isolated) However, beside their desks, there also existed sofas, toys, food and drink vendors, and all other kinds of amenities that help engineers alleviate their tiredness and keep concentrating on their work.

Google boasts of the quality of their engineers. They are the best and brightest in the world. They don't care which country the engineers come from and what kind of background they have - as long as they are smart.

I was totally overwhelmed. I just stood there in utter amazement. I was forced to realize that every effort I used to make in Japan just ended in vain. It is simply impossible for Japanese IT companies to defeat Google. It is just because Japanese companies run IT business wrong, while Google does it right.

(I also posted on FB and G+ .... Actually at first I didn't mean to post it on Blogger, I changed my mind because I've heard that G+ has a restriction that forces you to see only the latest 250 posts in your Profile screen)