From: Gregory Seidman <gsslist+ruby@...>
Date: 2006-09-08T10:19:09+09:00
Subject: Re: Faster datastructure for lookups wanted

On Fri, Sep 08, 2006 at 08:28:33AM +0900, Eero Saynatkari wrote:
} Mauricio Fernandez wrote:
} > On Fri, Sep 08, 2006 at 06:55:12AM +0900, m94asr@gmail.com wrote:
} >>   maybe somebody can recommend me the right datastructure or
} >> any other advice would be a big help.
} >> 
} >> My code spends most of its execution time doing lookups from
} >> a hashtable with about 1M keys. The keys are strings and the values
} >> are arrays of integers. Most of the time only of length 1.
} >> 
} >> I do not care  how long the construction of the datastructure takes,
} >> but the lookup should be as fast as possible.
} > 
} > It hardly gets faster than a Hash in Ruby.
} > You can also try a trie (Patricia tree if you have long keys and care 
} > about
} > space),
} 
} A Trie optimised by cutting off unambiguous traversal would
} be a definite possibility.

There is a trie gem that implements a Patricia Trie.

http://gemjack.com/gems/trie-0.0.1/classes/Trie.html

Of course, a Patricia Trie assumes no a priori knowledge of your string
inputs. If you know something about your keys, you may be able to do better
with a hash of hashes (to however many layers is appropriate), splitting as
appropriate for your key space. For example, if you know that your keys are
IPv4 addresses that come in dotted quad notation (e.g. 127.0.0.1), you
could do better with (note: untested):

class SplittableHash
  def initialize(split)
    @split = split
    @root = {}
  end

  def [](key)
    key.split(@split).inject(@root) { |h,k| h[k] if h }
  end

  def []=(key, val)
    path = key.split(@split)
    key = path.pop
    path.inject(@root) { |h,k| h[k] ||= {} }[key] = val
  end

end

--Greg