Re: more corrections for SRFI 132 Alex Shinn 12 Mar 2016 23:26 UTC
On Sat, Mar 12, 2016 at 12:06 PM, William D Clinger <xxxxxx@ccs.neu.edu> wrote: > In a previous message, I wrote: > >> The specification of vector-select! is missing an ordering predicate. >> It is also said to run "in O(k) time", which is impossible because it >> must examine start-end elements, which is arbitrarily larger than k. > > Now that I have implemented that procedure, I think it's a really > strange procedure for this SRFI to be specifying. Another way of naming it is top-k. Finding the smallest (or largest) k elements of a collection is so useful I find I rarely write a program these days that doesn't use it. Most of the time, but not always, I find I want to further sort those elements (i.e. a partial sort). The implementation you provide is O(n log n), whereas the implementation I posted to the list in January is O(n). Partial sorting would be O(n + k log k). -- Alex