Re: [Haskell-cafe] Optimizing a title matcher

On 9/27/06, Johan Tibell wrote:

On 9/27/06, Lyle Kopnicky wrote:

...

Hi folks,

It turns out Haskell is vindicated. It's my algorithm that was slow. As Robert Dockins pointed out, the double nested loop is just going to take a long time.

As evidence, it turns out my C++ version is just as slow as the Haskell version.

So, I'm going to go back to Haskell, but be more selective about which titles from the reference table I choose to match against, for any given import title.

Thanks, Lyle

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

I have no idea if this helps but perhaps a Directed Acyclic Word Graphs (DAWG) could be useful? It can be used for prefix matching for example.

- Johan

Uhm, so this a form of trie as mentioned before.