Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Searching large lists
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Mark Wotton <mrak@c...>
Subject: Re: [Caml-list] Searching large lists
On Thu, 8 Nov 2001, Andrew Lawson wrote:

> Hi all
>      I have a list containing up to 100,000 strings
> between 10 and 200 characters in length. I want to
> produce a list of those that match a regular
> expression. It seems that the obvious way is to
> List.filter with a predicate returning true if the
> string matches, however in my case this can take up to
> 15 seconds. Has anyone got any ideas for speeding this
> up?
> 
>      thanks
> 
>            Andrew

This would probably require rewriting whatever you're using to do the
regexes, but if you use a trie to store all the strings, you could
maintain a list of nodes which matched at each stage of the regex. This
should be a fair bit faster...

mrak


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr