Re: more corrections for SRFI 132
William D Clinger 10 Mar 2016 20:32 UTC
In my previous message, I mentioned bugs in the vector-stable-sort
and vector-stable-sort! procedures as implemented by the reference
implementation. Those bugs (including a couple in my test program)
are fixed by the following changeset:
https://github.com/larcenists/larceny/commit/b47237d284bf6579acc8f5e4d979388dabe6c58a
The missing procedures vector-find-median, vector-find-median!, and
vector-select! are currently defined in
https://github.com/larcenists/larceny/blob/master/lib/SRFI/srfi/132.sld
By the way, the median element of a vector can be found in linear
time, which is faster than the Ω(n lg n) worst-case performance
mandated by the specification of vector-find-median! and strongly
suggested by the specification of vector-find-median. I assume a
linear-time implementation of vector-find-median would not be
ruled out by SRFI 132, so it might be a good idea to tell users
of SRFI 132 that vector-find-median is likely to be faster than
vector-find-median! for long vectors.
Will