Frank wrote:
===
Lars Hellström writes:

 > Following up on that: As a proof of concept, I implemented (for
 > TeX3/LaTeX2e) such a \DictGet command last night; see attached files
 > (<6K with source documentation and tests). Complexity is linear in the
 > size of dictionary values, but worst-case quadratic in the average size
 > of a key.

helpful for playing around and checking alternatives, thanks.

As to the approach you outlined, I wonder if we should go in this
direction.
===

The quadratic running time may be poison.  Once that feature is there, users may use it heavily.

It would be sensible to estimate the running time for a dictionary with 100 keys.

Here's an alternative suggestion.  When TeX boots, do a
  \fontdimen\nullfont = 100000
to get sufficient linear memory.  Now write a 'Turing machine' or 'CPU' that will use this linear memory (in TeX macros of course).  One will then be able to implement a linear time dictionary.

You might find this suggestion a little unusual but after investigation I think you will find that it gives a better architecture and performance than a pure TeX macros approach.

I look forward to discussing this.

--
Jonathan


The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302).