home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / programm / 3136 < prev    next >
Encoding:
Internet Message Format  |  1992-11-13  |  1.2 KB
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!spool.mu.edu!agate!nima.berkeley.edu!shein
  2. From: shein@nima.berkeley.edu (Soren Hein)
  3. Newsgroups: comp.programming
  4. Subject: Partial sort/Nearest neighbor
  5. Date: 13 Nov 1992 13:20:37 GMT
  6. Organization: U.C. Berkeley -- ERL
  7. Lines: 21
  8. Distribution: world
  9. Message-ID: <1e0a35INN511@agate.berkeley.edu>
  10. NNTP-Posting-Host: nima.berkeley.edu
  11.  
  12. I have a small list (9 or 25 elements) of integers between 0 and 255.  
  13. My goal is to find the average of the K elements which are closest in
  14. absolute value to a given element in the list.  K is typically about
  15. half of the list length. I need the algorithm to be as fast as possible;
  16. space consumption is no problem.
  17.  
  18. What I'm doing at the moment is to create another list whose elements
  19. are the absolute differences between the original elements and the given
  20. element.  Then I sort the new list, keeping track of the permutations.
  21.  
  22. This is needlessly slow, because I don't need the K elements to be in
  23. order, and I don't need the remaining elements to be in order either.
  24.  
  25. [The above problem arises in image processing and is known as
  26. "nearest neighbor filtering".]
  27.  
  28. Please e-mail any suggestions to shein@robotics.berkeley.edu, and
  29. I will summarize if there is interest.
  30.  
  31. Thanks,
  32. /Soren
  33.