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

"G. Branden Robinson" <[email protected]> Tue, 25 Aug 2026 21:58:37 -0500
Newsgroups	gmane.comp.shells.bash.bugs
Message-ID	<20260826025837.3tupxnrod2o6scec@illithid>
At 2026-08-25T17:03:29-0400, Greg Wooledge wrote:
> It's a common feature in practically every programming language that
> hashes or associative arrays or dictionaries do not preserve or
> enforce any kind of ordering when you request the keys.  You get them
> in an arbitrary order.  If you want the keys to be sorted somehow,
> that's done in a second step.  (Yes, there may be exceptions, but
> they're not the norm, which is my point.)

Just in case anyone reading the list would benefit from the CS-theoretic
basis behind the foregoing...

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

* Associative arrays don't usually work by storing the key itself as the
  "index", because keys can be of variable size.  a["giraffe"] and
  a["cat"] would create problems in organizing the storage for the
  array efficiently.

  So what most implementations do is "hash" the key, using clever
  bit-fiddling techniques to produce an integer of fixed length that
  becomes the index.  An implementation sets aside a big arena of memory
  just as it would for a numerically indexed array, reserving enough
  room for the full range of possible hash values.  This can be costly
  of storage, but maintains a constant-time lookup no matter what the
  key value is.  (The supplied key is hashed with the same algorithm
  when the lookup is done, so that you retrieve the correct value.)

  There are piles and piles of literature on various approaches to "hash
  maps" a.k.a. associative arrays, and many tradeoffs that can be made
  in efficiency of insertion, deletion, and update.  Hash collisions,
  where two distinct keys map to the same integer, are a common problem.
  There are such things as generators for "perfect hash functions" that
  are guaranteed not to collide, but for them to work the key needs to
  be of bounded size or the entire key space needs to be known in
  advance (which amounts to the same thing).  Those are restrictions
  that programming languages--including Bash, which Chet unaccountably
  disqualified as a "programming language" earlier today--generally care
  not to impose on their users.

  (I'm a purist--if your language is Turing-complete, it's a programming
  language to me.  Thus, Chet maintains a programming language.)

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.

If you want to find a proper authority for the foregoing, any reputable
introductory book on data structures will serve.  If I had a
recommendation, I'd share one, but I don't.  Every data structures book
I can remember dealing with is either (1) too mathematical for the
beginner [Aho, Hopcroft, and Ullman kicked me away with steel-toed
boots] (2) presumes to teach you how to do everything in C [bad pedagogy
IMO, but I _know_ people will fight me on that; at least AHU had the
decency to write in Pascal...]; or (3) is too superficial, meaning that
it covers _only_ the basics and doesn't start showing you things that a
language's standard library or built-in features won't necessarily make
available to you.  At _some_ point in one's career, one has to implement
one's own data structures and algorithms to deal with them.  (That's a
good time to pick up AHU.)

While composing this mail, I've looked over No Starch Press's _Data
Structures the Fun Way_, and it seems okay.  Uses Python, which is
nicely clear as pseudocode.  Gets beyond first-semester material.

> Personally, I think we're getting close to the line between a shell
> and a programming language.  If your shell script needs to extract the
> keys of an associative array in lexicographical order, then it might
> be the case that your shell script really ought to be redone in a more
> powerful programming language.

Riffing on the above Turing point, I wouldn't even say "more powerful".
We can transform anything to a sequence of x86 MOV instructions.[1]  I'd
say "one whose idioms are a closer match for your problem domain".

It is naïve for a person to suppose that they will only ever need to
know one (or two, or n) programming languages (PLs).  You can improve
your ability to solve problems by learning almost any PL that anyone has
ever heard of.  Even if you never get to use a certain PL "in anger",
your receptive mind will absorb knowledge and perspectives that will
make you a more effective engineer.

Let's have diversity, equity, and inclusion in the PL space.  ;-)

Regards,
Branden

[1] https://github.com/xoreaxeaxeax/movfuscator

    If your mind is sick like mine, you will find the "control flow
    graph" figure hysterically funny.
signature.asc (application/pgp-signature, 833 B)