[Caml-list] Searching large lists

[Caml-list] Searching large lists

[Andrew Lawson]

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

=====
Andrew Lawson
andrew@absentis.com
 www.absentis.com

__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com
-------------------
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

Re: [Caml-list] Searching large lists

[Mark Wotton]

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

Re: [Caml-list] Searching large lists

[Jerome Vouillon]

On Thu, Nov 08, 2001 at 06:06:57AM -0800, Andrew Lawson wrote:
>      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?

The Str library is really slow.

For Unison (http://www.cis.upenn.edu/~bcpierce/unison/), we wrote our
own regular expression library to get acceptable performances.

You should try PCRE (http://sourceforge.net/projects/pcre-ocaml/) or maybe RE
(http://sourceforge.net/projects/libre/).

If you compile to native code, the RE library should be the fastest in
your case (probably about 5 to 10 times faster than PCRE).  It is
still under development though, so some features are missing.

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