From: Gavin Sinclair <gsinclair@...>
Date: 2002-12-18T23:34:31+09:00
Subject: Re: hash vs. array (dictionary lookup)

From: "Shannon Fang" <xrfang@hotmail.com>


>
> However, since the dictionary lookup operation will
> be quite heavy, I am thinking of using a hash instead
> of array. I tried the following code:
>
> f=File.new("dict.txt")
> text=f.sysread(File.size("dict.txt"))
> words=text.split(/\n/)
> lexicon={}
> words.each do |word|
> lexicon[word]=0
> end
>
> Disaster! It took me about 15 seconds to load the
> dictionary. Problem is that the #each method took too
> much time.

This code took 3 or 4 seconds to complete on my 900MHz PIII with 256Mb RAM.

  h = {}
  x = ["abd123"] * 90000
  x.each_with_index do |y, i|
    h[y + i.to_s] = 1
  end
  puts h.size


> I have 2 questions:
>
> 1. Is it worth to use hash instead of array with binary
> search?

I'd say so.  Hashes are extremely fast in general, and I presume the same in
Ruby.  Looking up strings in a hash is very fast [O(1)], and faster than a
binary search [O(log2 n)].

> 2. If I want to use hash, how to minimize the dictionary
> load time? BTW, I tried to convert the dict.txt file into
> a ruby command, i.e., dictionary={'first'=>0,'second'=>0,
> ...}, but system hangs when I tried to eval(text) after
> sysread... :(

I wouldn't bother with evaling like that.  Prefer an elegant solution to a fast
solution (which I highly doubt eval is) until your program is complete enough
for you to start worrying about execution times.

> Thanks a lot!
> Shannon


Gavin