Front page | perl.beginners |
Postings from February 2009
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
Thread Previous
|
Thread Next