most efficient way to implement "A without B"

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++;
}
[download]

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;
[download]

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

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; };` [download] No sorting needed. After Compline, Zaxo	[reply] [d/l]
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	[reply]
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 ) );` [download] Read more... (4 kB) the lowliest monk	[reply] [d/l] [select]
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 %_; }` [download]	[reply] [d/l]