Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: Comparing Two arrays

by Zaxo (Archbishop)
on Sep 19, 2002 at 15:56 UTC ( [id://199209]=note: print w/replies, xml ) Need Help??


in reply to 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

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]

In Section Seekers of Perl Wisdom

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://199209]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others contemplating the Monastery: (4)
As of 2024-04-19 18:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found