Re: symbol tables and search tries

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
2 Feb 2006 11:34:22 -0500

          From comp.compilers
Related articles
[11 earlier articles]
Re: symbol tables and search tries danwang74@gmail.com (Daniel C. Wang) (2006-01-31)
Re: symbol tables and search tries mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-01-31)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-01-31)
Re: symbol tables and search tries henry@spsystems.net (2006-01-31)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-01-31)
Re: symbol tables and search tries mr.waverlye@verizon.net (Mr.E) (2006-01-31)
Re: symbol tables and search tries mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-02-02)
Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-02-02)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-02)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-02-03)
Re: symbol tables and search tries d148f3wg02@sneakemail.com (Karsten Nyblad) (2006-02-03)
Re: symbol tables and search tries henry@spsystems.net (2006-02-03)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-03)
[3 later articles]
| List of all articles for this month |
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Newsgroups: comp.compilers
Date: 2 Feb 2006 11:34:22 -0500
Organization: cbb software GmbH
References: 06-01-117 06-01-120 06-01-132 06-01-139
Keywords: symbols
Posted-Date: 02 Feb 2006 11:34:22 EST

On 31 Jan 2006 21:18:30 -0500, Henry Spencer wrote:


> In a compiler, successful lookups would be expected to be rather
> more frequent than insertions, so most of the comparisons have to go
> all the way to the end of both strings for a decision.


Yes, but as it was already mentioned in the thread, there might be
sufficiently more than one table to look up. This brings the rate of
failures up.


> *Any* symbol table, no matter what data structure it uses, will have an
> O(m) component in a successful lookup, for the same reason.


True


--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.