Re: symbol tables and search tries

"Daniel C. Wang" <danwang74@gmail.com>
31 Jan 2006 09:56:18 -0500

          From comp.compilers

Related articles
[5 earlier articles]
Re: symbol tables and search tries RLake@oxfam.org.uk (2006-01-31)
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)
[9 later articles]
| List of all articles for this month |

From: "Daniel C. Wang" <danwang74@gmail.com>
Newsgroups: comp.compilers
Date: 31 Jan 2006 09:56:18 -0500
Organization: Compilers Central
References: 06-01-085 06-01-111 06-01-112 06-01-127
Keywords: symbols, performance

Perhaps, the suggestion that a search tree might be faster than a hash
tree came from this paper.


    http://www.cs.princeton.edu/~rs/strings/


It's worth pointing out that if you expect your lookup to fail most of
the time. a search tree can be more efficient than hashing, simply
because it doesn't need to examine the entire input string to
determine it's not in the tree. Any reasonable hashing scheme has to
examine the entire string.


With respect to compilers, I suspect hashing is more
efficient. However, I think there are legitimate situations where a
tree search may be more efficient.


Post a followup to this message

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