From: Eero Saynatkari Date: 2006-09-08T08:28:33+09:00 Subject: Re: Faster datastructure for lookups wanted 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. > or Judy arrays (http://rjudy.sourceforge.net), but I wouldn't > expect > major performance gains (Judy::JudySL, being more specialized than Hash, > might have a chance)... -- Posted via http://www.ruby-forum.com/.