Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!pt.cs.cmu.edu!dsl.pitt.edu!pitt!willett!ForthNet
From: ForthNet@willett.pgh.pa.us (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: Conventions and "tricks" used in Forth
Message-ID: <1882.UUL1.3#5129@willett.pgh.pa.us>
Date: 21 Oct 90 01:58:28 GMT
Organization: String, Scotch tape, and Paperclips.  (in Pgh, PA)
Lines: 27


 Date: 10-09-90 (10:26)              Number: 4037 (Echo)
   To: RAY DUNCAN                    Refer#: NONE
 From: JONAH THOMAS                    Read: NO
 Subj: HASHING THE DICTIONARY        Status: PUBLIC MESSAGE

 > use a 4 KB hash table and chain the collisions.  We have found that
 > even with several thousand words in the dictionary, FIND only
 > requires an average of <2 name comparisons.

   OK!  I was thinking about using a sort of binary tree and a
 comparison to cut the search time down to o[log2(n)] from o[n].  But
 it doubled the size of the links.  With a 4K hash table you'd break
 even on size at about 2000 words, and it only gets better from
 there.  With <2 comparisons you do better on time as soon as the
 dictionary gets big enough that a lot of string comparisons take
 longer than <2 hash compares.  That might be fairly small.
   The only advantages left for the tree are the ease of thinking
 (which is a one-time thing) and re-use of the code (which is
 trivial).  Thanks for stopping me before I actually wasted time
 getting it working!  8-)
 ---
  ~ NET/Mail : The MATRIX (5 Nodes/1.2 Gig) Birmingham, AL (205) 323-2016  
  ~ RNet 1.05M:* Metrolink - Front Porch BBS 404-695-1889 HST -Regional HUB
-----
This message came from GEnie via willett through a semi-automated process.
Report problems to: dwp@willett.pgh.pa.us or uunet!willett!dwp