Re: symbol tables and search tries

henry@spsystems.net (Henry Spencer)
3 Feb 2006 18:40:07 -0500

          From comp.compilers

Related articles
[16 earlier articles]
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)
Re: symbol tables and search tries haberg@math.su.se (2006-02-03)
Re: symbol tables and search tries anton@mips.complang.tuwien.ac.at (2006-02-06)
Re: symbol tables and search tries Suif.liyuan@gmail.com (jjyynmb) (2006-02-24)
| List of all articles for this month |

From: henry@spsystems.net (Henry Spencer)
Newsgroups: comp.compilers
Date: 3 Feb 2006 18:40:07 -0500
Organization: SP Systems, Toronto, Canada
References: 06-01-117 06-01-132 06-01-139 06-02-007
Keywords: symbols
Posted-Date: 03 Feb 2006 18:40:07 EST

Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>> In a compiler, successful lookups would be expected to be rather
>> more frequent than insertions...
>
>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.


If you've got a bunch of tables to deal with, but no requirement for
prefix search or sorted table dump, one way of getting rid of the O(m)
issues is to hash each input string as part of scanning, and put it into a
single master hash table, whose purpose is to store each distinct string
only once. That makes string equality comparisons O(1) rather than O(m):
you can just compare pointers and never look at the strings themselves.
All the other tables just hold pointers.
--
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.