Ramprasad A Padmanabhan wrote:
>
> I know this is more of an algorithm question but please bear with me.
>
> In my program I am checking wether a emailid exists in a list
> I have in the complete_list a string like
> $complete_string="<[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> ...
> <[EMAIL PROTECTED]>";
Why store it in a string and not an array?
> # that is a string of emailids sorted
>
> Now I want to find out if another ID "<[EMAIL PROTECTED]>" exists in this list
>
> How is it possible to optimize the search given that the complete list
> string is sorted in order
The fastest string search method IIRC is Boyer-Moore and variants
thereof. Perl provides the index() function for searching strings which
may be fast enough for your purposes. If you had stored the sorted list
in an array then you could have used a binary search which is very
efficient.
> The alternative I am considering is
> 1) Create a hash array with each of the ids as keys and just use the
> exits function
This is also very efficient as long as the keys are unique.
> like
> my %hash=();
> while($complete_list=~/(\<.*?\>)/g){ $hash{$1}=1 };
Or:
my %hash = map { $_ => 1 } $complete_list =~ /<[^>]*>/g
> ....
> if(exists($hash{$emailid})) {
> # FOUND id in string
> }
>
> Is this the best way
The hash has faster lookups but uses more memory then a single string.
> Is there no way directly to use the string
If all the entries in the string were the same length (space padded)
then you could use a binary search on the string.
John
--
use Perl;
program
fulfillment
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
