On Tue, Feb 1, 2022 at 2:57 PM Elijah Stone <elro...@elronnd.net> wrote: > 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.
I think you are thinking about scalar access -- operations which focus on a single key and the associated value. And, while that does happen, remember that J also supports operation on the data structure as a whole. > 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. The idea I get here is that you're talking theory which you were taught, and are not constructing specific examples. But what we need here, more than anything, are use cases. > >> (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. Ordered semantics are more restrictive than their absence. > 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. That's not a restriction on the semantics of the implementation, which is what I think we are supposed to be talking about here. > 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. Given that we would be constructing a specification here, *why* would specifying order be problematic? (Let's grant that it would have been a problem in some other context.) Thanks, -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
