How to compare hash value

[Anonymous Monk]

Myhash value is composed of an array, and for each array have different amount of element, like:

$myhash{$key1}=@value1;#@value1='abd, bcd, cde, def, efg'
$myhash{$key2}=@value2;#@value2='abd, def'
$myhash{$key3}=@value3;#@value3='efg, cde, tgh'
....

I want to group those have the same elements(not only the amount but also the value) hash value together, I do not care about the order. Like if

@value6='cde, tgh,efg',

then I will group @value3 and @value6together. How should I compare them? Please help and Thanks!!

[merlyn]

"Arrays are for ordering, hashes are for searching."

That's a good thought to keep in mind. Again, presuming what the others have presumed in this thread, that you actually have a hash of arrayrefs leading to the arrays of your data, you are trying to "search" an "array". You can do that badly once, but if you have to do it repeatedly, I suggest you restructure your data as:

my %myhash = (
  key1 => { map {$_ => 1} qw(abd bcd cde def efg) },
  key2 => { map {$_ => 1} qw(abd def} },
  key3 => { map {$_ => 1} qw(efg cde tgh) },
);

because then you can quickly find all first level keys that have "efg" in the second level with:

my @winners = grep $myhash{$_}{efg}, keys %myhash;

Hopefully, this gives you an idea about how to restructure it. Now if you actually need the ordering at the second level, there are hybrid solutions. But if all you need is to search that second level, then use hashes there.

And, if you need to turn this "inside out", finding all first-level keys for each second-level item, the syntax is a bit messy but the algorithm is straightforward:

my %inside_out;
for my $first_key (keys %myhash) {
  for my $second_key (keys %{$myhash{$first_key}}) {
    $inside_out{$second_key}{$first_key} = 1;
  }
}
for my $second_key (keys %inside_out) {
  print "$second_key => ",
    join(", ", sort keys %{$inside_out{$second_key}}), "\n";
}

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

[Improv]

I don't think your code is doing what you want. Examine the following:

LIAM:~$ perl
push(@a, 'a');
push(@a, 'b');
$foo{stuff} = @a;
print $foo{stuff} . "\n";

gives the result of 2. This is because you're assigning into the hash value the result of (scalar @a). If you really want to go with a hash of lists, your code should look more like

$myhash{$key1}=\@value1

Instead, you probably should be using a hash of hashes, e.g.

$myhash{$key1} = {'abd' => 1, 'bcd' => 2, ...};

This will prevent duplicate elements from messing up your set. Then, you can use sort and keys together to do the compare. Here's a subroutine that does what I think you're looking for:
Read more... (2 kB)

[broquaint]

Myhash value is composed of an array, and for each array have different amount of element, like ...

If you're setting up your hash values as you are in your example code then you won't get what you expected, the hash value will only contain the first element of the array e.g

my @ar   = qw/ foo bar baz /;
my %hash = ( one => @ar );
print $hash{one};

__output__

foo

This is because hash values can only store scalar variables, so you need to assign the hash value to an array reference e.g

my @ar   = qw/ foo bar baz /;
my %hash = ( one => \@ar );
print @{ $hash{one} };

__output__

foobarbaz

As for the comparison code you can use davorg's Array::Compare

use Array::Compare;

my %hash = (
  one => [ qw/ foo bar baz / ],
  two => [ qw/ baz foo bar / ],
);

print "the same"
  if Array::Compare->new()->perm(@hash{qw/one two/});

__output__

the same

Or even the Test::More utility method eq_array e.g

use Test::More;

## assuming data in above example

print "the same"
  if eq_array([sort @{ $hash{one} }], [sort @{ $hash{two} } ]);

__output__

the same


HTH

_________
broquaint

[Ovid]

I'm not sure what you mean when you say you want to group the arrays together. Are you adding a new hash entry, pushing them on an array somewhere?

Since I don't understand your grouping, I'll just tackle the other part of your question. One way to compare arrays would be to create a "stringify" function:

# note that having a sub for this is overkill, but if you 
# need more functionality, it's easy to encapsulate here (such
# as making it case-insensitive to independant of order)

sub stringify { local $" = ""; return "@{$_[0]}" }

if (stringify([sort @array1]) eq stringify([sort @array2])) {
    # arrays are the same
}

At that point, to find all keys that have identical values:

my %matches;
while (my ($key,$value) = each %somehash) {
    # stringified arrays as keys
    push @{$matches{stringify([sort @$value])}} => $key;
}

The above code snippet probably doesn't do what you want, but it might give you a starting point. Each stringified array will now point to a list of keys that match it.

Cheers,
Ovid

New address of my CGI Course.
Silence is Evil (feel free to copy and distribute widely - note copyright text)

[Jasper]

This (simple and easy) method has a tendency to fall down sometimes. If you had 'abc', 'def' in one array, and 'a', 'b', 'c', 'd', 'e', 'f' in another, joining with the empty string will make the strings equal. The simple solution would be to make $" something bizarre, and not likely to appear in the array, like "bcd". Only joking! Maybe ":::", or something.

If you can't be sure of what's in the arrays, comparison of Data::Dumper output of the sorted array might work?

Jasper

[Ovid]

Whoops! I hadn't thought of that. Nice catch.

Cheers,
Ovid

New address of my CGI Course.
Silence is Evil (feel free to copy and distribute widely - note copyright text)

[nothingmuch]

To get over that you must encapsulate Sigma, so that a condition like that does not arise. If you convert to a smaller subset and then use out of band data that will be safe (example - convert to hex and join with spaces). Also safe is escaping - because that's basically just creating a wide charset, which is a larger Sigma, enabling data out of the UTF or ASCII sigma. This is possibly faster, and more memory efficient.

If you join("\\",map { quotemeta($_) } @array); you will get a safe value, because quotemeta ensures that a single \ will never appear in the values.

-nuffin
zz zZ Z Z #!perl

[nothingmuch]

In order to compare plural values you have to normalize them - this means ordering them for comparison.

You have a minor error in your code - you're adding array counts, not elements, to the hash.

Start out by making an array of arrays:

my @array = (
    [ sort @value1 ],
    [ sort @value2 ],
    # ... and so forth
);

So that you have an array of normalized arrays, and then sort the large one and filter out duplicates like so:

my $prev = [];
@array = grep {
    my $i = 0;
    my $ret = 0;
    $ret = 1 if $#$prev != $#$_;
    while ($ret && $i <= $#$prev and $i <= $#$_){
        $ret = 1 if $prev->[$i] ne $_->[$i];
    }
    $ret;
} sort {
    my $i = 0;
    my $ret = 0;
    loop: while (1) {
        if ($i <= $#{$a} and $i <= $#{$b}){ # test if we still have so
+mething to compute
            $ret = $a->[$i] cmp $b->[$i]; # compute the difference of 
+this element
            last loop if $ret; # if there's a difference return
            $i++;
        } else { # if the arrays are equal to this point in terms of e
+lements, but not in length, we decide on the longer one
            $ret = $#{$a} <=> $#{$b}; # determine by length
            last loop;
        }
    }
    $ret;
} @array;

This will only return array unique arrays. Then you simply assign to your hash:

$myhash{$key1} = $array[0];
$myhash{$key2} = $array[1];



-nuffin
zz zZ Z Z #!perl

[Jaap]

Well.. assuming you mean this:

%myhash = (
key1 => [abd, bcd, cde, def, efg],
key2 => [abd, def],
key3 => [efg, cde, tgh],
key6 => [cde, tgh, efg],
);

You could loop through all the keys of %myhash, sort the value array and compare it to all other elements.

This would scale to n(n-1) which is roughly n² so it's very slow.

[tye]

    my %merge;
    for my $key (  keys %myhash  ) {
        push $merge{join $;, sort @{$myhash{$key}}}, $key;
    }

assuming $; doesn't appear in any of your values.

Update: Use the corrected code below. Thanks, Adam. I'll leave the @{} out above for continuity.

                - tye

[Adam]

Tye, you are pushing onto a scalar. Perl usually prefers for you to push things onto an array. :)

>perl -Mstrict -we "my $foo = []; push $foo, 'bar'"
Type of arg 1 to push must be array (not private variable) at -e line 1, at EOF
Execution of -e aborted due to compilation errors.

>perl -Mstrict -we "my %h; push $h{foo}, 'bar'"
Type of arg 1 to push must be array (not hash element) at -e line 1, at EOF
Execution of -e aborted due to compilation errors.

I think what you wanted to say here was:

    my %merge;
    for my $key (  keys %myhash  )
    {
        push @{ $merge{ join $;, sort @{ $myhash{$key}} } }, $key;
    }

I like it though, and it helps me solve an e-mail consolidation problem I had been working on.
-Adam

[slife]

"You will be miserable until you learn the difference between scalar and list context"

Programming Perl 3rd Ed p69

You almost certainly do not want to do this:

$myhash{$key1}=@value1

as $myhash{$key1} will contain the count of the number of elements in @value1

You will probably want to use references for this:

either:

$myhash{$key1}=\@value1;

or:

$myhash{$key1}=[ qw(abd bcd cde def efg) ];

perldoc perlreftut and perldoc perldsc refer.

As to your question, you may wish to review perldoc  perlfaq4, particularly How do I test whether two arrays or hashes are equal?, for some pointers on where to start.

[LAI]

Hmm... let's see...

my %temphash;
while (($key,\@val) = each %myhash) {
   $temphash{join sort @val} = $key;
}
undef %myhash;
while (($key,$val) = each %temphash) {
   $myhash{$val} = split $key;
}

Note: This is untested and will likely go through a couple of Updates.

LAI

__END__