Am Do., 8. Okt. 2020 um 21:13 Uhr schrieb John Cowan <xxxxxx@ccil.org>:
>
>
>
> On Thu, Oct 8, 2020 at 1:27 PM Adam Nelson <xxxxxx@nels.onl> wrote:
>>
>> Yes, I'll address that in the next draft. I didn't realize that Scheme vectors could have non-O(1) access or mutation, but, if they can, then the most flexvectors can promise is that they have the same random-access performance.
>
>
> This is all over different threads, but I'll just say it here:
>
> 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.)

Marc