develooper Front page | perl.beginners | Postings from February 2009

Re: How to speed up two arrays compare.

Thread Previous | Thread Next
John W. Krahn
February 11, 2009 11:11
Re: How to speed up two arrays compare.
Message ID:
kevin liu wrote:
> On Wed, Feb 11, 2009 at 11:22 PM, John W. Krahn <> wrote:
>> 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;
>> 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 )
> Could you please help to explain? Thank you in advance.

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: or:

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

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

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

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About