Email list hosting service & mailing list manager

there is no correct way to use list-sort! or list-stable-sort! William D Clinger (09 Mar 2016 12:31 UTC)
more corrections for SRFI 132 William D Clinger (10 Mar 2016 17:06 UTC)
Re: more corrections for SRFI 132 William D Clinger (10 Mar 2016 19:37 UTC)
Re: more corrections for SRFI 132 William D Clinger (10 Mar 2016 20:32 UTC)
benchmarking the SRFI 132 reference implementation William D Clinger (10 Mar 2016 23:20 UTC)
Re: more corrections for SRFI 132 William D Clinger (12 Mar 2016 03:07 UTC)
Re: more corrections for SRFI 132 Alex Shinn (12 Mar 2016 23:26 UTC)
Re: more corrections for SRFI 132 John Cowan (13 Mar 2016 22:02 UTC)

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