[M3devel] code submission

[Olaf Wagner]

Quoting Mika Nystrom <mika at async.caltech.edu>:

> Knuth section 6.3 talks about it; he claims the word is based on
> "information reTRIEval".  Tries can be faster than hash methods
> when most of the words are not to be found in the dictionary, and
> you can tell by reading just one or two characters that you don't
> have that word.  Parsing a data file in the way what I am doing is
> an example: I am only interested in a very small subset of the
> lines.  (The application is, given the complete data set for the
> Toronto Stock Exchange for a month, extract certain records pertaining
> to a small subset of stock tickers.)  Of course, which tickers it
> is changes all the time, so you can't really compile in a special-case
> switch statement either.

> In my application, using the standard Modula-3 TEXT and Text.Hash,
> plus Text<>Tbl was many times slower than AWK.  The trie code is quite
> a bit faster (completely limited by disk speed).

OK, thanks for the explanations. I should have a look at the old
standard books more often. I know prefix trees, but had never
heard the term `trie'. I think we should definitely add it.
I'm still not sure if it should go better into its own package or
into the generics part of libm3. What do the others think?

Olaf
-- 
Olaf Wagner -- elego Software Solutions GmbH
                Gustav-Meyer-Allee 25 / Gebäude 12, 13355 Berlin, Germany
phone: +49 30 23 45 86 96  mobile: +49 177 2345 869  fax: +49 30 23 45 86 95
    http://www.elegosoft.com | Geschäftsführer: Olaf Wagner | Sitz: Berlin
Handelregister: Amtsgericht Charlottenburg HRB 77719 | USt-IdNr: DE163214194