Re: The "asort" extension (Was: feature proposal: expand associative arrays in lexicographic order ...)

On 8/25/26 10:58 PM, G. Branden Robinson wrote:

> * Numerically indexed arrays can find an element by _index_ value in
>    constant time, because their location in memory is typically a
>    multiple of the size of one element times the index.  So you can
>    retrieve element a[1] or a[453] or a[n] in the same amount of time,
>    other things being equal.
> 
>    (A linked list would require linear time in `n`, because the
>    implementation can start only at the beginning, and has to follow
>    up to `n` pointers until encountering a match.)

That applies to singly-linked lists without using any auxiliary data.
There are things you can do to make O(n) the worst case, and make it
much faster for common access patterns, and bash uses them.

>    that programming languages--including Bash, which Chet unaccountably
>    disqualified as a "programming language" earlier today

I didn't. Certainly the message you're replying to did.

> The bottom line is that sorting an associative array is computationally
> expensive--in time, in storage requirements, or both--and not necessary
> for a great many applications of that kind of data structure.

It makes sense to have this feature, if it's implemented at all, as
something the user/programmer requests using a new expansion.

-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
		 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    [email protected]    http://tiswww.cwru.edu/~chet/