Re: symbol tables and search tries

henry@spsystems.net (Henry Spencer)
31 Jan 2006 21:18:30 -0500

          From comp.compilers

Related articles
[8 earlier articles]
Re: symbol tables and search tries haberg@math.su.se (2006-01-31)
Re: symbol tables and search tries henry@spsystems.net (2006-01-31)
Re: symbol tables and search tries find@my.address.elsewhere (Matthias Blume) (2006-01-31)
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)
[6 later articles]
| List of all articles for this month |

From: henry@spsystems.net (Henry Spencer)
Newsgroups: comp.compilers
Date: 31 Jan 2006 21:18:30 -0500
Organization: SP Systems, Toronto, Canada
References: 06-01-117 06-01-120 06-01-132
Keywords: symbols, performance

Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>...The hash function evaluation time should be counted as well. The
>penalty depends on not only n, the table size, but also on m, the token
>length.


A well-balanced tree will get you to the right place with O(log n) tests,
but if the place is occupied, you then need an O(m) comparison to decide
whether the occupant is the symbol being looked up. 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.


*Any* symbol table, no matter what data structure it uses, will have an
O(m) component in a successful lookup, for the same reason.
--
spsystems.net is temporarily off the air; | Henry Spencer
mail to henry at zoo.utoronto.ca instead. | henry@spsystems.net



Post a followup to this message

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