home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / lang / scheme / 2961 < prev    next >
Encoding:
Internet Message Format  |  1993-01-24  |  1.8 KB
  1. Path: sparky!uunet!ferkel.ucsb.edu!taco!gatech!usenet.ins.cwru.edu!agate!spool.mu.edu!howland.reston.ans.net!paladin.american.edu!news.univie.ac.at!hp4at!mcsun!julienas!corton!ilog!davis
  2. From: davis@passy.ilog.fr (Harley Davis)
  3. Newsgroups: comp.lang.scheme
  4. Subject: Re: How to lookup symbols fast?
  5. Message-ID: <DAVIS.93Jan24152042@passy.ilog.fr>
  6. Date: 24 Jan 93 14:20:42 GMT
  7. References: <1je4kvINN5cj@shelley.u.washington.edu>
  8.     <1993Jan19.212543.29200@gallant.apple.com>
  9.     <JAFFER.93Jan20163704@camelot.ai.mit.edu>
  10. Sender: news@ilog.fr
  11. Organization: ILOG S.A., Gentilly, France
  12. Lines: 29
  13. In-reply-to: jaffer@zurich.ai.mit.edu's message of 20 Jan 93 21:37:04 GMT
  14.  
  15.  
  16. In article <JAFFER.93Jan20163704@camelot.ai.mit.edu> jaffer@zurich.ai.mit.edu (Aubrey Jaffer) writes:
  17.  
  18.    (Kenneth Dickey) writes:
  19.       ...
  20.       >Is there anything better than a simple linear search of the
  21.       >symbols?
  22.  
  23.       The rule of thumb is "for less than 100 elements, linear search beats
  24.       hashing".  For 30 entries use an alist & assq.
  25.  
  26.    I tested this out.  The break-even for SCM using SLIB is 250 elements.
  27.    The situation for compiled code would be less (perhaps 100).  Here is
  28.    my code.  I used strings instead of symbols so that hash.scm would use
  29.    OBJECT-HASH.  It is much slower for symbols.  In light of this result,
  30.    I will be changing some of my code back to using alists.
  31.  
  32. This kind of measure is so totally implementation-dependent that
  33. general "rules of thumb" are out of line.  For example, in Le-Lisp
  34. version 16, the break-even point for symbols as keys is a giant 2
  35. elements in the a-list.
  36.  
  37. -- Harley Davis
  38. --
  39.  
  40. ------------------------------------------------------------------------------
  41. nom: Harley Davis            ILOG S.A.
  42. net: davis@ilog.fr            2 Avenue Gallie'ni, BP 85
  43. tel: (33 1) 46 63 66 66            94253 Gentilly Cedex, France
  44.