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="us-ascii"
Date: Sat, 28 Nov 2009 17:25:39 +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 (31 lines)
Lars wrote:
==
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.
==

I don't see how key length comes into it.  Suppose I start with an empty dictionary and add to it 100 entries, which are not known to be different.  If determining if a dictionary already has a key is linear in the number of items in the dictionary, then the running time for building a dictionary of size n is at least order n^2.

What's the cost of discovering if a dictionary has a key?  I suspect that the best that can be done in any language is log n, while for TeX macros it is n.

Thus, the cost of create a dictionary with n entries is of order n log n in most languages, and of order n^2 for TeX macros.

Thank you for correcting my syntax for allocating fontdimen memory.

--
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