bug-bash
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: The "asort" extension (Was: feature proposal: expand associative arr


From: Chet Ramey
Subject: Re: The "asort" extension (Was: feature proposal: expand associative arrays in lexicographic order ...)
Date: Wed, 26 Aug 2026 09:20:47 -0400
User-agent: Mozilla Thunderbird

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    chet@case.edu    http://tiswww.cwru.edu/~chet/



reply via email to

[Prev in Thread] Current Thread [Next in Thread]