Re: Comparing Two arrays

This is a faq, but here goes:

my @array1 = ("q", "w", "e", "r", "t", "z");
my @array2 = ("q", "w", "e", "r", "t", "y");

my %hash;
@hash{@array2} = () x @array2;
my @not_there = grep { ! exists $hash($_} } @array1;
[download]

exists is used to prevent autovivication of new keys from @array1 in %hash.

Update: This method's run time is O(NlogN) or therabouts, while your attempt is O(N**2). ++fruiture for spotting a thinko, corrected.

After Compline,
Zaxo

Comment on Re: Comparing Two arrays Download Code

Replies are listed 'Best First'.
Re: Re: Comparing Two arrays by sauoq (Abbot) on Sep 19, 2002 at 18:49 UTC
This method's run time is O(NlogN) or therabouts, while your attempt is O(N2). I think your method is actually O(N+M) as you iterate each array once and johnirl's is O(NM) because he iterates one array for each element in the other. The difference in array size might be significant. That is why I used two different variables: N and M. Update:* A short /msg exchange with Zaxo prompted me to point out that searches and updates on hashes are expected to be O(1). That is, assuming that the hash function is a good one for your data. I believe it is a reasonable assumption to make here. -sauoq "My two cents aren't worth a dime.";	[reply]

Replies are listed 'Best First'.

Re: Re: Comparing Two arrays
by sauoq (Abbot) on Sep 19, 2002 at 18:49 UTC

This method's run time is O(NlogN) or therabouts, while your attempt is O(N**2).

I think your method is actually O(N+M) as you iterate each array once and johnirl's is O(N*M) because he iterates one array for each element in the other.

The difference in array size might be significant. That is why I used two different variables: N and M.

Update: A short /msg exchange with Zaxo prompted me to point out that searches and updates on hashes are expected to be O(1). That is, assuming that the hash function is a good one for your data. I believe it is a reasonable assumption to make here.

-sauoq
"My two cents aren't worth a dime.";

[reply]