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

"G. Branden Robinson" <[email protected]> Wed, 26 Aug 2026 09:44:53 -0500

Newsgroups	gmane.comp.shells.bash.bugs
Message-ID	<20260826144453.cvtjs6czdgkbpv2e@illithid>

At 2026-08-26T09:20:47-0400, Chet Ramey wrote:
> 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.

Right.  I didn't want to complicate the discussion.

I was trying to hint at the irreducible (or, at any rate,
as-yet-unreduced) complexity of the problems.

I don't know what the world universe look like if all operations were
O(n), let alone O(1).  ;-)

> >    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.

Whoops!  I thought I saw an unreasonably modest claim from you.  My bad!

> > 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.

Definitely agree.  Most languages lack such auxiliary properties
precisely because they're so often unnecessary.  And everything that is
implemented costs something somewhere.

Python programmers get, or used to get, exposed to `.sorted()` early.
It's one of those things that certainly comes up _often_, but it's not
a property you want to freight the type itself with because of all the
cases where the cost is unjustified.

Maybe `asort`, or Bash's loadable builtins generally, could benefit from
additional visibility in documentation.  It was certainly a long time in
my case--years--before I became aware that they even existed.

Regards,
Branden

signature.asc (application/pgp-signature, 833 B)