home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / lang / scheme / 2946 < prev    next >
Encoding:
Internet Message Format  |  1993-01-22  |  2.3 KB
  1. Path: sparky!uunet!timbuk.cray.com!raistlin!uc.msc.edu!noc.msc.net!news.gac.edu!nntp-server!max
  2. From: max@Kolmogorov.gac.edu (Max Hailperin)
  3. Newsgroups: comp.lang.scheme
  4. Subject: Re: How to lookup symbols fast?
  5. Date: 22 Jan 93 09:34:14
  6. Organization: Gustavus Adolphus College, St. Peter, MN
  7. Lines: 34
  8. Message-ID: <MAX.93Jan22093414@Kolmogorov.gac.edu>
  9. References: <1je4kvINN5cj@shelley.u.washington.edu>
  10.     <1993Jan19.212543.29200@gallant.apple.com>
  11. Reply-To: Max Hailperin <max@nic.gac.edu>
  12. NNTP-Posting-Host: kolmogorov.gac.edu
  13. In-reply-to: kend@newton.apple.com's message of 19 Jan 93 21:25:43 GMT
  14.  
  15. In article <1993Jan19.212543.29200@gallant.apple.com>
  16. kend@newton.apple.com (Kenneth Dickey) writes:
  17.  
  18.    In article <1je4kvINN5cj@shelley.u.washington.edu> Charles Bass,
  19.    chuckb@stein.u.washington.edu writes:
  20.    >We are writing a simple pattern matching program in scheme and
  21.    >would like to speed up some of the internal "stuff".  We have a
  22.    >table of 20 or 30 functions that our evaluate uses to determine
  23.    >which function/rule-set to apply.
  24.    ...
  25.    >Is there anything better than a simple linear search of the
  26.    >symbols?
  27.  
  28.    The rule of thumb is "for less than 100 elements, linear search beats
  29.    hashing".  For 30 entries use an alist & assq.
  30.  
  31. Yes, but if read has already read in something as a symbol and the
  32. "symbol" data type in your particular variant of Scheme has a spare
  33. slot in it's representation (say, the property-list slot), then the
  34. hashing has *already been done* by read.  Assuming you only put a few
  35. properties on each symbol's property list (i.e. much less than 30),
  36. and that property lists are linearly searched much like assq
  37. (typically true, though often the details are a bit different, i.e.
  38. alternating key and data elements rather than a list of pairs), this
  39. has got to be faster than searching an alist of length 30.  Moreover,
  40. it will typically grow more gracefully, since you are more likely to
  41. multiply by a large factor the number of symbols in the table than the
  42. number of tables (i.e. properties).
  43.  
  44. Yes, I know that property lists are archaic and not a standard feature
  45. of the Scheme language, but many implementations do have them and if
  46. Bass was using such an implementation, and if he really was of
  47. necessity starting from *symbols* as he stated (i.e. pre-hashed by
  48. read), then there seems like little point in redoing read's work.
  49.