Velocity Reviews > Perl > Most efficient way to do set-comparison

# Most efficient way to do set-comparison

Krishna Chaitanya
Guest
Posts: n/a

 03-13-2009
Hi all,

If set A defined elements a,b,c (a set of permissible program options,
let's say), and we receive from user options in set B.

I want to make sure that user options in B are exactly same as those
defined in A .... nothing more, nothing less and completely
identical....this represents some kinda set operation if I'm not
wrong...

A U B = A
A int B = A

How to do this most efficiently in Perl...?

Peter Makholm
Guest
Posts: n/a

 03-13-2009
Krishna Chaitanya <(E-Mail Removed)> writes:

> If set A defined elements a,b,c (a set of permissible program options,
> let's say), and we receive from user options in set B.

Many set operations can be implemented quite easy by using hash'es
where the keys are the elements in the sets.

//Makholm

Krishna Chaitanya
Guest
Posts: n/a

 03-13-2009
let's say), and we receive from user options in set B.
>
> Many set operations can be implemented quite easy by using hash'es
> where the keys are the elements in the sets.

Yep...I could make it out, but what is the most efficient way....using
any trick in the book of Perl? I could come up with this:

Listing 1
==========
use warnings;
use strict;

my %legalopts = (a => 1, b => 1, c => 1);

my %opts = (a => 1, c => 1); # failure would be that some elements are
missing (i.e. 'b')
# my %opts = (a => 1, b => 2, c => 3, d => 4); # failure would be that
extra options are present (i.e. 'd')

my @del_list = delete @opts{keys %legalopts};

\$num_def = grep {!/^\$/} map { defined \$_ } @del_list;
die "Some options are missing in opts" unless @del_list == \$num_def;

if (scalar keys %opts)
{
print "Extra elements found in opts: ";
print "\$_ " foreach keys %opts;
print "\n";
die;
}

Pls. tell me if any better way exists...

Guest
Posts: n/a

 03-13-2009
Krishna Chaitanya <(E-Mail Removed)> wrote:
> Hi all,
>
> If set A defined elements a,b,c (a set of permissible program options,
> let's say), and we receive from user options in set B.
>
> I want to make sure that user options in B are exactly same as those
> defined in A .... nothing more, nothing less and completely
> identical....this represents some kinda set operation if I'm not
> wrong...

You want the "symmetric difference" to be empty.

> A U B = A
> A int B = A
>
> How to do this most efficiently in Perl...?

perldoc -q difference

How do I compute the difference of two arrays?
How do I compute the intersection of two arrays?

--
email: perl -le "print scalar reverse qq/moc.noitatibaher\100cmdat/"

Guest
Posts: n/a

 03-13-2009
Krishna Chaitanya wrote:
> let's say), and we receive from user options in set B.
>> Many set operations can be implemented quite easy by using hash'es
>> where the keys are the elements in the sets.

>
> Yep...I could make it out, but what is the most efficient way....using
> any trick in the book of Perl? I could come up with this:
>
> Listing 1
> ==========
> use warnings;
> use strict;
>
> my %legalopts = (a => 1, b => 1, c => 1);
>
> my %opts = (a => 1, c => 1); # failure would be that some elements are
> missing (i.e. 'b')
> # my %opts = (a => 1, b => 2, c => 3, d => 4); # failure would be that
> extra options are present (i.e. 'd')
>
> my @del_list = delete @opts{keys %legalopts};
>
> \$num_def = grep {!/^\$/} map { defined \$_ } @del_list;
> die "Some options are missing in opts" unless @del_list == \$num_def;
>
> if (scalar keys %opts)
> {
> print "Extra elements found in opts: ";
> print "\$_ " foreach keys %opts;
> print "\n";
> die;
> }
>
> Pls. tell me if any better way exists...

\$ perl -le '
%legalopts = (a=>1, b=>1, c=>1); %opts = (a=>1, c=>1);
@L = sort keys %legalopts; @O = sort keys %opts;
print "@L" eq "@O" ? "Ok" : "Not equal"
'
Not equal
\$

--
Email: http://www.gunnar.cc/cgi-bin/contact.pl

smallpond
Guest
Posts: n/a

 03-13-2009
On Mar 13, 9:05 am, Krishna Chaitanya <(E-Mail Removed)> wrote:
> Hi all,
>
> If set A defined elements a,b,c (a set of permissible program options,
> let's say), and we receive from user options in set B.
>
> I want to make sure that user options in B are exactly same as those
> defined in A .... nothing more, nothing less and completely
> identical....this represents some kinda set operation if I'm not
> wrong...
>
> A U B = A
> A int B = A
>
> How to do this most efficiently in Perl...?

Set::Scalar has an is_equal method, and overloads ==

Guest
Posts: n/a

 03-13-2009
> Krishna Chaitanya wrote:
>> let's say), and we receive from user options in set B.
>>> Many set operations can be implemented quite easy by using hash'es
>>> where the keys are the elements in the sets.

>>
>> Yep...I could make it out, but what is the most efficient way....using
>> any trick in the book of Perl? I could come up with this:
>>
>> Listing 1
>> ==========
>> use warnings;
>> use strict;
>>
>> my %legalopts = (a => 1, b => 1, c => 1);
>>
>> my %opts = (a => 1, c => 1); # failure would be that some elements are
>> missing (i.e. 'b')
>> # my %opts = (a => 1, b => 2, c => 3, d => 4); # failure would be that
>> extra options are present (i.e. 'd')
>>
>> my @del_list = delete @opts{keys %legalopts};
>>
>> \$num_def = grep {!/^\$/} map { defined \$_ } @del_list;
>> die "Some options are missing in opts" unless @del_list == \$num_def;
>>
>> if (scalar keys %opts)
>> {
>> print "Extra elements found in opts: ";
>> print "\$_ " foreach keys %opts;
>> print "\n";
>> die;
>> }
>>
>> Pls. tell me if any better way exists...

>
> \$ perl -le '
> %legalopts = (a=>1, b=>1, c=>1); %opts = (a=>1, c=>1);

Fails with:

%opts = ('a b'=>1, c=>1);

> @L = sort keys %legalopts; @O = sort keys %opts;
> print "@L" eq "@O" ? "Ok" : "Not equal"
> '
> Not equal

--
email: perl -le "print scalar reverse qq/moc.noitatibaher\100cmdat/"

Guest
Posts: n/a

 03-13-2009
> Gunnar Hjalmarsson <(E-Mail Removed)> wrote:
>>
>> \$ perl -le '
>> %legalopts = (a=>1, b=>1, c=>1); %opts = (a=>1, c=>1);

>
> Fails with:
>
> %opts = ('a b'=>1, c=>1);
>
>> @L = sort keys %legalopts; @O = sort keys %opts;
>> print "@L" eq "@O" ? "Ok" : "Not equal"
>> '
>> Not equal

Ouch! This should fix that:

\$ perl -le '
%legalopts = (a=>1, b=>1, c=>1); %opts = (a=>1, b=>1);
@L = sort keys %legalopts; @O = sort keys %opts;
print "@L" eq "@O" && @L == @O ? "Ok" : "Not equal"
'
Not equal
\$

OTOH you might object again and ask what happens if:

%legalopts = ("a b"=>1, c=>1); %opts = (a=>1, "b c"=>1);

I give up. This simplified approach is not safe, unless you can preclude
those odd combinations based on the rest of the code.

--
Email: http://www.gunnar.cc/cgi-bin/contact.pl

Dr.Ruud
Guest
Posts: n/a

 03-14-2009

> \$ perl -le '
> %legalopts = (a=>1, b=>1, c=>1); %opts = (a=>1, c=>1);
> @L = sort keys %legalopts; @O = sort keys %opts;
> print "@L" eq "@O" ? "Ok" : "Not equal"
> '
> Not equal

I hate suggestions like that, because the stringifications of the arrays
can be equal when the arrays aren't.

--
Ruud

Dr.Ruud
Guest
Posts: n/a

 03-14-2009
Krishna Chaitanya wrote:

> If set A defined elements a,b,c (a set of permissible program options,
> let's say), and we receive from user options in set B.
>
> I want to make sure that user options in B are exactly same as those
> defined in A .... nothing more, nothing less and completely
> identical....this represents some kinda set operation if I'm not
> wrong...
>
> A U B = A
> A int B = A
>
> How to do this most efficiently in Perl...?

See List:Util and List::MoreUtils.

Or call this:

sub cmp_set {
my %a; @a{ @{\$_[0]} } = (); delete @a{ @{\$_[1]} };
my %b; @b{ @{\$_[1]} } = (); delete @b{ @{\$_[0]} };
if ( %b ) {
return 2 if %a; # dissimilar
return -1;
}
return %a ? 1 : 0;
}

--
Ruud