Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

most efficient way to implement "A without B"

by telcontar (Beadle)
on Apr 09, 2005 at 17:55 UTC ( #446267=perlquestion: print w/ replies, xml ) Need Help??
telcontar has asked for the wisdom of the Perl Monks concerning the following question:

Let's say you have two lists, @a and @b, and all elements of @b are contained in @a. How do you get "@a without @b"? Of course, one could sort both lists, iterate through the elements of @a, have an index for @b, and push elements in @a to an array @c if the element in @a is not at that position in @b. But that seems rather tedious. For instance,
@b = sort {$a <=> $b} @b; @a = sort {$a <=> $b} @a; print "@b\n"; for (@a) { if (defined($b[$i])) { if (not $_ == $b[$i]) { push @c, $_ } else { $i++ } } else { push @c, @a[($j..$#a)]; last; } $j++; }

I'm sure this can be done in a somewhat more efficient (perl-ish *g) way ... like this:
@c = grep { defined($b[0]) and !($b[0] eq $_) or !shift @b } sort {$a <=> $b} @a;

This should work if @b is already sorted. I'm sure it can be done in better ways .. I'm brand-new at Perl after all.

John

Comment on most efficient way to implement "A without B"
Select or Download Code
Re: most efficient way to implement "A without B"
by Zaxo (Archbishop) on Apr 09, 2005 at 18:07 UTC

    A hash is the usual way to improve the efficiency of lookup.

    my @a_not_b = do { my %b; @b{@b} = (); grep { not exists $b{$_} } @a; };
    No sorting needed.

    After Compline,
    Zaxo

Re: most efficient way to implement "A without B"
by bobf (Monsignor) on Apr 09, 2005 at 19:45 UTC

    It might be worthwhile to take a look at the List:: modules on CPAN, specifically List::Util and List::Compare. List::Util provides functions like min, max, and sum. List::Compare provides intersection, union, and (of relevance to the posted question) ways to determine which elements appear in one list but not the other.

    Zaxo provided a very nice (and probably more efficient) solution, but the List:: modules will come in handy if you have to do more complicated functions.

    HTH

Re: most efficient way to implement "A without B"
by sh1tn (Priest) on Apr 09, 2005 at 20:01 UTC
    my @a_not_b; { local @_{@a} = (); delete @_{@b}; @a_not_b = keys %_; }


Re: most efficient way to implement "A without B"
by tlm (Prior) on Apr 09, 2005 at 20:25 UTC

    In addition to Zaxo's solution, consider implementing your "lists" as the keys of hashes to begin with (actually this is just packaging Zaxo's solution for easy reuse). Then all these membership questions become relatively easy to code. E.g., your "@A without @B" is basically a relative complement:

    use strict; use warnings; sub relative_complement { return list_2_hashref( grep !exists $_[ 1 ]->{ $_ }, keys %{ $_[ 0 ] + } ); } sub list_2_hashref { return +{ map +( $_ => 1 ), @_ }; } my $diff = relative_complement( list_2_hashref( @A ), list_2_hashref( @B ) );

    the lowliest monk

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://446267]
Approved by Joost
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (6)
As of 2014-11-21 03:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (104 votes), past polls