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