home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / programm / 3185 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  4.9 KB
  1. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!agate!nima.berkeley.edu!shein
  2. From: shein@nima.berkeley.edu (Soren Hein)
  3. Newsgroups: comp.programming
  4. Subject: SUMMARY: Partial sort/Nearest Neighbor
  5. Date: 19 Nov 1992 08:00:54 GMT
  6. Organization: U.C. Berkeley -- ERL
  7. Lines: 92
  8. Distribution: world
  9. Message-ID: <1efhjmINNg6q@agate.berkeley.edu>
  10. NNTP-Posting-Host: nima.berkeley.edu
  11.  
  12. This is a summary of responses to my posting "Partial sort/Nearest Neighbor".
  13. The problem was the following:
  14.  
  15.    I have a small list (N = 9 or 25 elements) of integers between 0 and 255.  
  16.    My goal is to find the average of the K elements which are closest in
  17.    absolute value to a given element in the list.  K is typically about
  18.    half of the list length. I need the algorithm to be as fast as possible;
  19.    space consumption is no problem.
  20.  
  21. Sincere thanks to the many people who responded:
  22.  
  23.    Doug Moore        (dougm@cs.rice.edu)
  24.    Dave Dodson       (dodson@bach.convex.com)
  25.    Bob Stearns       (is@groucho.dev.uga.edu)
  26.    Chow Gloria       (chow@roquefort.cerisi.fr)
  27.    David desJardins  (desj@ccr-p.ida.org)
  28.    Jan Stout         (wsbusup4@urc.tue.nl)
  29.    Alex Martelli     (martelli@cadlab.sublink.org)
  30.    lloyd allison     (lloyd@bruce.cs.monash.edu.au)
  31.    Greg Doherty      (greg@cs.uow.edu.au)
  32.  
  33. To keep this posting short, I will not quote the individual responses
  34. verbatim, and I will not explicitly credit each idea to the persons
  35. (usually more than one) who suggested each idea.  Also, I will use words
  36. more appropriate for the equivalent problem of finding the K smallest
  37. elements of a list.  
  38.  
  39. --- Selection sort:  The standard method first finds the smallest element,
  40. then the smallest of the remaining elements etc.  This can be terminated
  41. once the K smallest elements have been found.  The running time should
  42. be O(K*N). This algorithm sorts the first K elements as a by-product,
  43. and this extra effort is not required.
  44.  
  45. --- Insertion sort:  The standard method assumes that the j-1 first
  46. elements are sorted, and inserts the j'th element in the correct place,
  47. for j between 2 and N.  This can be modified to only keep a list of K
  48. sorted elements; if the j'th element is too big, it is thrown away
  49. rather than inserted.  The running time should be O(K*N).  This
  50. algorithm also sorts the first K elements as a by-product, and this
  51. extra effort is not required.
  52.  
  53. --- Heap sort: Keep only a heap of size K rather than N.  Elements that
  54. are too big are thrown away rather than inserted.  The running time is
  55. O(N lg K).  This algorithm does not do more sorting than it needs to,
  56. although it could be argued that there is some (unnecessary?) effort
  57. involved in returning the K smallest elements in the form of a heap,
  58. when a flat list would do.
  59.  
  60. --- Quick sort:  One reader referred me to Knuth (where else?), section
  61. 5.2.2. exercise 31.  This in turn pointed to two papers by Hoare.
  62. The one I found most useful was 
  63.    C. A. R. Hoare, "Proof of a Program: FIND", CACM,
  64.    Volume 14, Number 1, pp. 39-45, Jan. 1971
  65. which has a short routine that partially sorts a list so that the Kth
  66. element is in the right place, the elements to the left are <= the Kth
  67. element, and the elements to the right are >= the Kth element.  [This
  68. routine is used, conceptually, in quick sort.] This appears to me to do
  69. only what's needed, and I have lifted the routine from the paper.  The
  70. running time could be O(N), but I'm not sure.
  71.  
  72. --- Hashing / radix sort:  Keep a count array of 256 elements, initialized
  73. to zero.  For each list element, increment the count array at the position
  74. corresponding to the value of the list element.  Then we can work our
  75. way outwards from any desired value until we have the K closest elements.
  76. [This method is based on the list elements being small integers.]
  77. My main reservation is that setting the count array to zero may take too
  78. long.  If this can be done efficiently in hardware, it seems like a good
  79. choice.  Running time is 256+O(N).
  80.  
  81. --- Fancy method:  Find the Kth largest element using a linear time
  82. algorithm.  [This is fancy because the linear-time algorithm for doing
  83. so is apparently quite complicated.  I don't yet have a reference for
  84. it.]  Then add up all the elements <= the Kth element in linear time,
  85. and take the average.
  86.  
  87. --- "Home made" method:  Find all elements between two bounds.  If there
  88. are too many, reduce the bounds; if there are too few, widen the bounds.
  89. This might work well, but its quality would depend on the choice of
  90. initial bounds.  Also, I don't know of any performance analysis.
  91.  
  92. --- Miscellaneous:  I also received a couple of literature references which
  93. I haven't yet tracked down, and the advice that for short list, simple
  94. methods may beat more complicated ones.
  95.  
  96. ===
  97.  
  98. My choice for now is the partial quicksort algorithm, but I admit I
  99. haven't yet had time to compare the time consumption with all the
  100. competitors. The code for the partial quicksort is simple and
  101. non-recursive;  I'll send it to anybody interested.
  102.  
  103. /Soren
  104.