home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2520 < prev    next >
Encoding:
Text File  |  1992-08-29  |  2.4 KB  |  54 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!jvnc.net!yale.edu!ira.uka.de!rz.uni-karlsruhe.de!stepsun.uni-kl.de!uklirb!posthorn!vier!neuhaus
  3. From: neuhaus@vier.informatik.uni-kl.de (Stephan Neuhaus (HiWi Mattern))
  4. Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
  5. Message-ID: <neuhaus.715007061@vier>
  6. Sender: news@posthorn.informatik.uni-kl.de (News system account)
  7. Nntp-Posting-Host: vier.informatik.uni-kl.de
  8. Organization: University of Kaiserslautern, Germany
  9. References: <1992Aug26.183817.7371@reed.edu> <1992Aug27.115551.7958@daimi.aau.dk> <PSU.92Aug27104235@ptero.cs.duke.edu> <1992Aug27.215924.24525@reed.edu>
  10. Date: Fri, 28 Aug 1992 13:04:21 GMT
  11. Lines: 41
  12.  
  13. orpheus@reed.edu (P. Hawthorne) writes:
  14.  
  15. >  Has anyone used frequency of node access data to bias the tree balancing
  16. >rotation operations toward shorter paths?
  17.  
  18. Not quite, but I have used self-organizing linear lists in a program
  19. that spent almost 90% of its time doing lookups, with startling
  20. results.
  21.  
  22. The main data structure was a trie, with the brethren linked together
  23. in a linked list.  The linked lists were about 20--30 elements long,
  24. and the trie was 8--10 levels deep. I have tried both common forms of
  25. self-organizing lists in my program, with roughly the same speedup
  26. compared to unorganized or sorted lists:
  27.  
  28. 1.  When an element is successfully found in the list, move it to the
  29. front of the list so that it may be found faster in subsequent
  30. searches.
  31.  
  32. 2.  When an element is successfully found in the list, exchange it
  33. with its predecessor.
  34.  
  35. The probability distribution for my keys was such that I rarely needed
  36. more than one pointer traversal per list to find the proper element.
  37. With sorted lists, the situation became more complex and hard to
  38. analyze, since the relative ordering of a particular item in a list
  39. was not connected to its frequency in retrievals.  Anyway, I managed
  40. to get a speedup by a factor of 15 (roughly) for shallow tries.
  41.  
  42. Observation: The longer the lists, the more speedup was obtained.
  43. This is quite natural when you think about it for a minute.
  44.  
  45. The probability distribution of my keys was roughly exponential, i.e.,
  46. in a list sorted by frequency of access, item i+1 was p% less likely
  47. to appear in a retrieval operation than item i, where p is independent
  48. of i.
  49.  
  50. Have fun.
  51. -- 
  52. Stephan <neuhaus@informatik.uni-kl.de>
  53. sig closed for inventory.  Please leave your pickaxe outside.
  54.