[geeks] Programming question.

[David Cantrell]

On Tue, Apr 02, 2002 at 10:11:10AM -0500, alex j avriette wrote:
> erm, typo:
> > my @missing = map { grep { $_ } @lista } @listb;
> thats not @missing, its @common. for missing, you'd use 'not grep'

Did you actually try that before posting?

Each element of @listb gets mapped in turn to the results of
grep { $_ } @lista.  In that, $_ takes in turn each element of @lista, so
you get a list of all the true elements of @lista.  So ...

my @a = (1,3,5,7,9);
my @b = (0,1,2,3,4,5,6,7,8,9);

my @common = map { grep { $_ } @a } @b;

gives us ...

@common = (1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9,1,3,5,7,9); # all true elements of @a, repeated scalar(@b) times

which unless I'm very much mistaken is not what you intended.  You thought
that the value of $_ inside that grep would be each item of @listb in turn,
when it ain't.  And even if it were, it would still be hideously inefficient,
as you'd still be comparing each element of @lista to each element of @listb,
which is O(n^2).

Your bug fix doesn't work either.  It does exactly the same, then applies a
not to each resulting list.  Not only makes sense in scalar context, so
each list is converted to a scalar, then notted.  Those resulting scalars
are then made into a list.  Which with my test data, returned a very nice -
but unwanted - list of false values.  And is still of order O(n^2).

My solution not only gives the right result, but is as near as damnit O(n).

I suppose it could be contracted somewhat:

my %a = map { ($_, 1) } @a;
@c = grep { !defined $a{$_} } @b; # or something like that

Which is slightly more efficient (but not much) and, IMO, harder to read.

-- 
Grand Inquisitor Reverend David Cantrell | http://www.cantrell.org.uk/david

  This is nice.  Any idea what body-part it is?