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

Re: How to speed up two arrays compare.

Thread Previous | Thread Next
From:
Raymond Wan
Date:
February 11, 2009 23:03
Subject:
Re: How to speed up two arrays compare.
Message ID:
4993C9C7.6070301@kuicr.kyoto-u.ac.jp

Hi Kevin and all,


John W. Krahn wrote:
> 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 ).


Kevin, seems you're getting lots of help already but I'll just add a little that may or may not help you.

What is the "best" algorithm depends on the precise definition of the problem.  Do you want to just know if everything in array2 is in array1?  If so, then once you know it isn't, then you can exit.  Or do you want to know how many items in one list are in the other; once we get to counting, then you will have to look at both lists.

Or, do you know beforehand that the two lists are sorted or are you willing to sort them?  If so, what you can do may change as well...

Ray


Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About