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
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.
The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302).