Re: symbol tables and search tries

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
31 Jan 2006 09:58:00 -0500

          From comp.compilers

Related articles
[6 earlier articles]
Re: symbol tables and search tries vmakarov@redhat.com (Vladimir Makarov) (2006-01-31)
Re: symbol tables and search tries clint@0lsen.net (Clint Olsen) (2006-01-31)
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)
[8 later articles]
| List of all articles for this month |

From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Newsgroups: comp.compilers
Date: 31 Jan 2006 09:58:00 -0500
Organization: cbb software GmbH
References: 06-01-117 06-01-120
Keywords: symbols, performance

On 31 Jan 2006 00:33:59 -0500, RLake@oxfam.org.uk wrote:


> Having said that, I don't think that a hash table is the best
> data structure for an IDE, although it probably is for a
> compiler. An IDE will want to be able to do things like
> tab-completion, which would militate for a data structure
> which facilitates prefix searches, such as a trie or
> PATRICIA tree.


I agree. 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.


Further, what hash tables cannot do is parsing the source with an
unknown right bound of the token. I.e. trees don't need a tokenizer to
be run first. A tree (or other ordered structure) can itself act as a
tokenizer, making nice things like closest match, wild-cards etc. This
all boils down to the "native" order of tokens, hash tables lack. It
was already mentioned by some other poster. So it depends...


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