On Tue, 1 Feb 2022, Raul Miller wrote:
1. What is the efficiency gain from ordered keys?
(a) Ordered access is "close to the hardware" (cache friendly),
1. Dictionaries are specifically about random access. That's the point.
If you want a list of key-value pairs, you can do that already with no
difficulty. I do not think there is reason to believe that _access
patterns_ correspond to any particular statically determinable order.
2. The conceptual order of the keys has fairly little significance. The
implementation strategy for an order-maintaining dictionary will likely
be a hash table mapping keys to pointers (indices), in non-contiguous
fashion, causing you to scramble about in memory _more_ than you
otherwise would--less cache friendly than an unordered implementation.
Regardless, I think that ordered keys can be implemented reasonably
efficiently, and--again--may improve performance for some workloads; but
still do not see why this is an argument for forcing their semantics.
(b) Many of J's verbs are defined on ordered sequences. So demanding
unordered access is demanding that those verbs do not function.
This is indeed a problem. I think in some cases (e.g. / /. i.) you can
get away with using an arbitrary order.
(In general, the more restrictive your semantics are, the more freedom
you have about implementing them, and hence the more efficient you can
be. So this doesn't make sense to me.
I think that you should think about what you said here, in this context.
I assume you have a point, but do not know what it is.
Perhaps it is a miscommunication regarding the meaning of 'restrictive'?
Unordered keys are more restrictive than ordered ones, because they
restrict code that depends on a certain order: it must explicitly specify
it.
2. It is possible to materialize arbitrary orderings on-demand by
indexing with an appropriately ordered array of keys. I do not
think this is a good argument for making the data inherently
ordered.
I am not sure what kind of ordering you think is bad -- there's a
variety of possibilities there.
But there's going to be an order.
That's exactly the problem--no ordering is inherently bad, and some may be
useful--but assuming a particular ordering is problematic. And it is easy
to materialise any ordering you might need.
-E
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
