Front page | perl.beginners | Postings from February 2009

## Re: How to speed up two arrays compare.

From:
John W. Krahn
Date:
February 11, 2009 11:11
Subject:
Re: How to speed up two arrays compare.
Message ID:
499322BB.7030409@shaw.ca
```kevin liu wrote:
> On Wed, Feb 11, 2009 at 11:22 PM, John W. Krahn <jwkrahn@shaw.ca> wrote:
>>
>> 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 )

The algorithm Rob gave you is O( n + m ) which is usually better than O(
n * log m ) for the worst case.

An explanation of binary search can be found at:
http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary or:
http://en.wikipedia.org/wiki/Binary_search

>> If the elements of @nwarray1 were in a hash then you could reduce your
>> worst case to O( n ).

As to whether the algorithm Rob presented is the "best" algorithm, that
depends on the data being used and how often this operation needs to be
preformed.

For example, the algorithm I presented above has a best case of O( 1 )
while the one Rob presented has a best case of O( n + m ).

John
--
Those people who think they know everything are a great
annoyance to those of us who do.        -- Isaac Asimov

```