I’ve Moved My Blog

To my millions of loyal readers: http://blog.jonahb.com

Northampton Center for the Arts

My mom runs the Northampton Center for the Arts.  I developed their new web site, and we deployed it today.

It was fun and rewarding to work closely with Ann Shanahan, the Chair of the Center’s board, who moonlights as web site editor.  She reviewed each version of the site and suggested changes and new features.  At Microsoft, we imagined customers, but we rarely developed working relationships with real customers.  So it was refreshing to have Ann involved the whole time.

Picking a Random, Unlit Number

On The Darfur Wall, when a user clicks “Donate,” we need to select a random, unlit number fast.  But users can light numbers at any time.  What data structure should we use to hold unlit numbers?

We need fast random selection and fast deletion.  Arrays provide fast random selection but slow deletion, hashes the opposite.  Below is an array-hash hybrid, based on this article, that performs both operations fast.

(By the way, I am new to Ruby.  If anyone is actually reading this, feel free to offer feedback on the code.  Should delete throw or return nil, like Array?  Is there a better exception than RuntimeError?  What should insert and delete return?  I’ve tried to be consistent with Array and Hash, but it seems odd to return anything!)

class RandomSelectionList

  def initialize
    # hash key is an element in the list; hash value is the index of the same element in @array
    @hash = Hash.new
    # array contains all elements in the list, unordered; allows fast random selection
    @array = Array.new
  end
  
  def insert( value )
    raise ArgumentError, "List already contains value" if @hash.has_key?( value )
    @hash[ value ] = @array.length
    @array[ @array.length ] = value
  end
  
  def delete( value )
  
    # remove element from the hash (Hash.delete returns the value i.e. the array index)
    index = @hash.delete( value )
    raise ArgumentError, "List does not contain value" if index == nil
    
    if index < @array.length - 1
      # replace the removed element with the element at the end of the array
      replacement_value = @array[ -1 ]
      @array[ index ] = replacement_value

      # update the hash with the new index of that element
      @hash[ replacement_value ] = index
    end
    
    # finally, remove the last element from the array
    @array.delete_at( -1 )
    
    value
  end
  
  def get_random
    raise RuntimeError, "No elements in list" if @array.length <= 0
    @array[ rand( @array.length ) ]
  end
end

ECBs

I enjoy the writing of Erica C. Barnett. And I love a good egg cheese bacon sandwich. Behold a beautiful union.

Ruby Reader-Writer Lock

I couldn’t find one of these in the Ruby libraries, so I wrote one quickly. I’m using this on The Darfur Wall. Since the site is mostly static, I cache data in memory. I use this reader-writer lock to control access to the cache.

# allows many readers, one writer

# a writer must wait until there are zero readers and zero writers
# a reader must wait until there are zero writers

# we could change this so that writers have priority, i.e. new readers are blocked until the writer is finished

class ReaderWriterLock

  def initialize
    # there is ((one or more readers) or (one writer)) iff @reader_mutex is locked
    @reader_mutex = Mutex.new

    # there is one writer iff @writer_mutex is locked
    @writer_mutex = Mutex.new

    # the number of readers
    @reader_count = 0

    # we must acquire lock on @reader_count_mutex before reading or writing @reader_count
    @reader_count_mutex = Mutex.new
  end

  def start_read
    @reader_count_mutex.synchronize do
      if @reader_count == 0
        @reader_mutex.lock
      end
      @reader_count = @reader_count + 1
    end
    self
  end

  def end_read
    @reader_count_mutex.synchronize do
      if @reader_count > 0
        @reader_count = @reader_count - 1
        if @reader_count == 0
          @reader_mutex.unlock
        end
        self
      else
        nil
      end
    end
  end

  def read
    begin
      start_read
      yield
    ensure
      end_read
    end
  end

  def start_write
    @writer_mutex.lock
    @reader_mutex.lock
    self
  end

  def end_write
    if @writer_mutex.unlock
      @reader_mutex.unlock
      self
    else
      nil
    end
  end

  def write
    begin
      start_write
      yield
    ensure
      end_write
    end
  end
end