J.Fine skrev:
> 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.
Note that even this implementation is strongly linear in the number of
dictionary entries; to notice the quadratic term behaviour you'd rather
have to consider a dictionary where all keys are 100 characters long 
and even then you might discover that linear terms dominate the
complexity, since the inner loop of what contributes that quadratic
term to the complexity is TeX grabbing tokens for a macro argument.
> Here's an alternative suggestion. When TeX boots, do a
> \fontdimen\nullfont = 100000
I suppose you mean \fontdimen 100000\nullfont=1sp. I wouldn't be
surprised if there is a 15bit limit on fontdimen numbers though; there
certainly is such a limit if you get them from a TFM.
> to get sufficient linear memory. Now write a 'Turing machine' or
> 'CPU' that will use this linear memory (in TeX macros of course).
Oooh! That must be the corniest idea I've seen for months. :) Impressive!
> 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.
While I generally enjoy exploring new TeX programming tricks, I don't
see how this would buy you _anything_ for the problem at hand. What
this (ab)use of the the fontdimens of \nullfont would provide is a
compact <number> > <number> table accessed by saying
\fontdimen <number> \nullfont
but that's pretty much it. You can use the table for storing the
transition function of a finite automaton, by combining input symbol
and current state into an <integer constant>, but setting that up and
then reacting to the state change will take a couple of macro
expansions at least, so I doubt you're much better off than if doing it
purely in terms of macros. There's certainly no extratight inner loop
that you could take advantage of.
If one feels like implementing some new mathematical function  like
xor, the float placement bitfiddling, or GF(16) arithmetic  in TeX
then this is probably a useful trick, but otherwise not.
Lars Hellström
