Re: symbol tables and search tries

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

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