Re: symbol tables and search tries

Matthias Blume <blume@tti-c.org> wrote:


> Hans, please, do the calculation!


I find it difficult to carry out any computations before first converting
the problem to a proper model within axiomatic set theory. :-)


> It does /not/ give you logarithmic
> time, it gives you constant time (in the amortized sense).
....
> A hash table does not sort, so this line of reasoning is not
> applicable.


There are apparently two data types in play: one with only equality
(equivalence relation), and one sorted (with total order). The containers
(like the hash table) only doing the equality comparison apparently (if
one should believe the posters here :-)) can do it in O(1) time.
The containers doing the sorting (like the balanced tree) can at best do
it in O(log n) time.


Now, a compiler only needing to identify the tokens would then be best off
with the first type. But a parser of some type that also needs to compare
the tokens, would be best off with the second type.


Roughly.


--
    Hans Aberg
[I think we're all in agreement here. For compiling, all you do with symbols
is look them up, and hashes do that well. In more complex enviroments where
you sort them or use them for name completion, tries have advantages. -John]

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