Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

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.


Comment on most efficient way to implement "A without B"
Select or Download Code
Replies are listed 'Best First'.
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,

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.


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

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 %_; }

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2015-11-29 10:47 GMT
Find Nodes?
    Voting Booth?

    What would be the most significant thing to happen if a rope (or wire) tied the Earth and the Moon together?

    Results (750 votes), past polls