LATEX-L Archives

Mailing list for the LaTeX3 project

LATEX-L@LISTSERV.UNI-HEIDELBERG.DE

Options: Use Classic View

Use Proportional 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
direction.
===

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.

--
Jonathan


The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302).

ATOM RSS1 RSS2