NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/programm/3140

Text File | 1992-11-14 | 1.5 KB | 38 lines

Newsgroups: comp.programming
Path: sparky!uunet!ukma!nntp.msstate.edu!emory!athena.cs.uga.edu!groucho.dev.uga.edu!is
From: [e-mail] (Bob Stearns)
Subject: Re: Partial sort/Nearest neighbor
Message-ID: <[e-mail]>
Sender: [e-mail]
Organization: University of Georgia
References: <[e-mail]>
Date: Fri, 13 Nov 1992 20:04:17 GMT
Lines: 26

In article <[e-mail]> [e-mail] (Soren Hein) writes:
>I have a small list (9 or 25 elements) of integers between 0 and 255.
>My goal is to find the average of the K elements which are closest in
>absolute value to a given element in the list.  K is typically about
>half of the list length. I need the algorithm to be as fast as possible;
>space consumption is no problem.
>
Try the following:
   Initialize S to the empty list, heap representation
   Let T be your original set
   for t in T do
     if |S|<k, insert t-t_0 into s, in sorted order by magnitude
     if |S|>k then
       if |t-t_0| < |S[k]| then
          remove S[K] and insert |t-t_0| into k in sorted order by magnitude
   end
   average S for your new value.
This seems to do the trick in O(nlogk) time. Another approach, which
should approach O(n), is a modified Quick Sort algorithm. You only have
to continue to curry the partition containing k, using the absolute
value function as your comparison operator.
--
Bob Stearns
University of Georgia
[e-mail]
[phone]