On 2020-10-08 21:28 +0200, Marc Nieper-Wißkirchen wrote:
>> It's true that RnRS doesn't prescribe that vector access and
>> mutation are O(1), any more than it specifies the same for pairs or
>> records.  That is because the matter has always been taken for
>> granted.  A Scheme that provided O(n) vectors would be (in the opinion
>> of anyone who used vectors for Real World purposes) a broken Scheme.
>> (Strings are another matter).
>
> O(n) would be, in fact, strange. But O(log n) is not. If your Scheme's
> memory allocator only returns memory blocks whose size is, say, a
> power of 16, it makes sense to break down a vector of length N into
> O(log N) pieces. As long as the O-factor is low, that's a fine
> implementation. Or if the largest contiguous block has an upper limit
> so that a vector is modeled with a tree structure with vectors at its
> leaves. (Makes sense for very large vectors and is, in fact, the
> implementation model of virtual memory with a paging scheme.)

Yes.  This is one reason why I'm rather sad that vector-set! can't be
linear update--there are plenty of immutable implementations of vectors
which can guarantee O(log n) access.

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>

"Simplicity does not precede complexity, but follows it."
--Alan J. Perlis