Front page | perl.beginners | Postings from February 2009

Re: How to speed up two arrays compare.

From:
kevin liu
Date:
February 11, 2009 08:08
Subject:
Re: How to speed up two arrays compare.
Message ID:
9618a85a0902110807r43d33459g502203d1344b3ac0@mail.gmail.com
```On Wed, Feb 11, 2009 at 11:22 PM, John W. Krahn <jwkrahn@shaw.ca> wrote:

> 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
>
> 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 ).

But how could this be, I have got the best algorithm from Rob, but I
don't know why a binary search would be O( n * logm )