I want to do a binary search on a list of strings in memory. Basically I
want the bsearch functionality, also implemented in Search::Dict.
Unfortunately that is documented to only work for a list of strings in a
file. http://search.cpan.org/~nwclark/perl-5.8.9/lib/Search/Dict.pm says
in part: <q>
NAME
Search::Dict, look - search for key in dictionary file
SYNOPSIS
use Search::Dict;
look *FILEHANDLE, $key, $dict, $fold;
use Search::Dict;
look *FILEHANDLE, $params;
DESCRIPTION
Sets file position in FILEHANDLE to be first line greater than or equal
(stringwise) to $key. Returns the new file position, or -1 if an error
occurs.</q>
Is there any way to have a FILEHANDLE point to an array in memory?
If so, is anything special needed to use the above module?
I want the array of strings to be in memory for speed. I think that doing
file I/O would be very slow.
I want to search a sorted array to see if which strings, if any, have the
same prefix as my search string. For example, given the search string of
"tempest" I want to find "tempests" and "tempestuous". My word list has
about 250,000 words. Even though only about 7500 will be used to start as
search I think brute force would be too slow. It would take O (n*n) time.
Because I believe in measuring performance I actually wrote the brute force
code. It only uses 2500 strings to strart the search, rather than the 7500
I plan to use. In fact it is very slow. It is still running 15 minutes
later, and I can tell it is only half done.
Alternatively, can someone recommend another perl module for prefix
searching on a moderately large set of strings, e.g. trie or suffix tree or
suffix array, etc.. It must be reliable and easy to use.
Thanks,
Steve
_______________________________________________
Boston-pm mailing list
Boston-pm@mail.pm.org
http://mail.pm.org/mailman/listinfo/boston-pm
