kevin liu wrote:
Hi everybody:
Hello,
I have two arrays(@nwarray0 and @nwarray1) in my program and i want
to make sure that
all the elements in @nwarray0 could be found in @nwarray1.
Here is my implementation:
-------------------------------------------------------
foreach my $srctemp ( @nwarray0 ) {
foreach my $tgttemp ( @nwarray1 ) {
if ( $tgttemp eq $srctemp ) {
$found = 1;
last;
}
}
if ( $found == 1 ) {
$found = 0;
next;
}
else {
return 1;
}
}
--------------------------------------------------------
But this algorithm takes a long time to compare, could you please
help to improve this piece of
code to less the time needed?
The best you can do with two arrays is exit as soon as an element of
@nwarray0 is not found in @nwarray1:
my $found = 1;
SEARCH:
foreach my $srctemp ( @nwarray0 ) {
foreach my $tgttemp ( @nwarray1 ) {
if ( $tgttemp ne $srctemp ) {
$found = 0;
last SEARCH;
}
}
}
But this will still take O( n * m ) if all the elements of @nwarray0 are
in @nwarray1.
If the elements of @nwarray1 are sorted then you could a binary search
on it and reduce your worst case to O( n * log m ).
If the elements of @nwarray1 were in a hash then you could reduce your
worst case to O( n ).
John
--
Those people who think they know everything are a great
annoyance to those of us who do. -- Isaac Asimov
--
To unsubscribe, e-mail: beginners-unsubscr...@perl.org
For additional commands, e-mail: beginners-h...@perl.org
http://learn.perl.org/
