Sat, 28 Nov 2009 16:45:32 +0100
text/plain; charset=ISO-8859-1; format=flowed
> 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 15-bit 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 extra-tight inner loop
that you could take advantage of.
If one feels like implementing some new mathematical function -- like
xor, the float placement bit-fiddling, or GF(16) arithmetic -- in TeX
then this is probably a useful trick, but otherwise not.