LATEX-L Archives

Mailing list for the LaTeX3 project


Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Lars Hellström <[log in to unmask]>
Reply To:
Mailing list for the LaTeX3 project <[log in to unmask]>
Sat, 28 Nov 2009 16:45:32 +0100
text/plain (55 lines)
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 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.

Lars Hellström