home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2525 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  1.8 KB
  1. Path: sparky!uunet!usc!sol.ctr.columbia.edu!destroyer!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  2. From: dave@cs.arizona.edu (Dave Schaumann)
  3. Newsgroups: comp.programming
  4. Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
  5. Message-ID: <1992Aug28.180854.14457@organpipe.uug.arizona.edu>
  6. Date: 28 Aug 92 18:08:54 GMT
  7. References: <1992Aug26.183817.7371@reed.edu> <1992Aug27.115551.7958@daimi.aau.dk> <PSU.92Aug27104235@ptero.cs.duke.edu> <1992Aug27.215924.24525@reed.edu> <neuhaus.715007061@vier>
  8. Sender: news@organpipe.uug.arizona.edu
  9. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  10. Organization: University of Arizona
  11. Lines: 29
  12. In-Reply-To: neuhaus@vier.informatik.uni-kl.de (Stephan Neuhaus (HiWi Mattern))
  13.  
  14. In article <neuhaus.715007061@vier>, neuhaus@vier (Stephan Neuhaus (HiWi Mattern)) writes:
  15. >orpheus@reed.edu (P. Hawthorne) writes:
  16. >
  17. >>  Has anyone used frequency of node access data to bias the tree balancing
  18. >>rotation operations toward shorter paths?
  19. >
  20. >Not quite, but I have used self-organizing linear lists in a program
  21. >that spent almost 90% of its time doing lookups, with startling
  22. >results.
  23. >
  24. [...]
  25. >1.  When an element is successfully found in the list, move it to the
  26. >front of the list so that it may be found faster in subsequent
  27. >searches.
  28. >
  29. >2.  When an element is successfully found in the list, exchange it
  30. >with its predecessor.
  31.  
  32. >[...]I managed to get a speedup by a factor of 15 (roughly) for shallow
  33. >tries. [keys access probability had exponential distribution]
  34.  
  35. It seems reasonable that this would also work well for equal probability
  36. of key access if you have a situation where the access of a key means it
  37. will likely be accessed again soon.  (for example, variables in programs
  38. generally have this property: you have an access in the declaration, then
  39. several more accesses following as the variable is used.)
  40.  
  41. -- 
  42. What signature?
  43.