LATEX-L Archives

Mailing list for the LaTeX3 project


Options: Use Classic View

Use Monospaced Font
Show Text Part by Default
Condense Mail Headers

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

Print Reply
Content-Type: text/plain; charset="iso-8859-1"
Date: Fri, 27 Nov 2009 16:26:37 +0000
Reply-To: Mailing list for the LaTeX3 project <[log in to unmask]>
From: "J.Fine" <[log in to unmask]>
Content-Transfer-Encoding: 8bit
In-Reply-To: <[log in to unmask]>
MIME-Version: 1.0
Sender: Mailing list for the LaTeX3 project <[log in to unmask]>
Parts/Attachments: text/plain (34 lines)
Frank wrote:
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).