Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

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...


Bug reports:  FAQ:
To unsubscribe, mail  Archives: