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/
