From: Robert Klemme Date: 2009-02-04T00:50:57+09:00 Subject: Re: Quicker finding strings? Alternative for array, hash, set? 2009/2/3 Ken Bloom : > On Mon, 02 Feb 2009 08:21:48 -0500, Robert Klemme wrote: > >> 2009/2/2 Patrick Put : >>>> Rehearsal ----------------------------------------------------------- >>>> Array#find existing 3.160000 0.700000 3.860000 ( 3.870061) >>>> Array#find non-existing 6.280000 1.630000 7.910000 ( 7.935304) >>>> Hash#[] existing 0.000000 0.000000 0.000000 ( 0.000019) >>>> Hash#[] non-existing 0.000000 0.000000 0.000000 ( 0.000018) >>>> ------------------------------------------------- total: 11.770000sec >>>> >>>> user system total real >>>> Array#find existing 3.130000 0.710000 3.840000 ( 3.866618) >>>> Array#find non-existing 5.820000 1.580000 7.400000 ( 9.195417) >>>> Hash#[] existing 0.000000 0.000000 0.000000 ( 0.000030) >>>> Hash#[] non-existing 0.000000 0.000000 0.000000 ( 0.000032) >>> >>> That is impressive indeed! No need for any other containers here I >>> guess. ;-) Thanks for showing me this! >> >> If you do not want to attach information to those words then a Set is >> more appropriate: same O(1) lookup but no key value mapping. > A trie might also be a good idea. Some tries were proposed as solutions > to Ruby Quiz #103 (http://rubyquiz.com/quiz103.html) Good idea. But this is only a realistic option if the trie is implemented in C I guess - otherwise the standard String#hash and Set#include? are faster. Kind regards robert -- remember.guy do |as, often| as.you_can - without end