Getting Max Value from Different Hashes

neversaint has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: Getting Max Value from Different Hashes by Corion (Patriarch) on Aug 01, 2005 at 14:03 UTC
How about using List::Util ? `my $max_val = max map { values %$_ } $hash_w, $hash_x, $hash_y, $hash_ +z;` [download]	[reply] [d/l]
Re^2: Getting Max Value from Different Hashes by diotalevi (Canon) on Aug 01, 2005 at 15:03 UTC
Corion, your method is straightforward but suffers because it makes a copy of every value at once. You could still use max() but only have one hash copy present at a time just by switching to reduce(). `my @hashes = ( $hash_w, $hash_x, $hash_y, $hash_z ); my $max = max( values %{shift @hashes } ); $max = reduce { max( $_[0], values %{$_[1]} ) } @hashes;` [download]	[reply] [d/l]
Re^3: Getting Max Value from Different Hashes by polettix (Vicar) on Aug 01, 2005 at 15:56 UTC
I hope that the OP was not seriuos about the efficiency issue - this is why such an optimisation over 4 values seems weird to me :) Flavio perl -ple'$_=reverse' <<<ti.xittelop@oivalf Don't fool yourself.	[reply]
Re^4: Getting Max Value from Different Hashes by diotalevi (Canon) on Aug 01, 2005 at 16:03 UTC
Re^5: Getting Max Value from Different Hashes by polettix (Vicar) on Aug 01, 2005 at 16:13 UTC
Re: Getting Max Value from Different Hashes by Limbic~Region (Chancellor) on Aug 01, 2005 at 14:19 UTC
neversaint, You should never resort to sorting to find the max or min value of a list unless the side effect of sorting has a benefit later on. Use a high or low water mark algorithm. Corion has suggested a fine one that, when possible, uses a C implementation that makes it really fast. Unfortunately - it doesn't completely answer your question since it only gives you the max value and not which hash it came from. I question why you have 4 distinct hashes if each one only contains a single key. It seems to make more sense to have a single level hash or if absolutely necessary - a hash of hashes (HoH). For the moment, I will concede that there may be some valid, yet unspoken, reason to have things the way you do. `use List::Util 'max'; my @h_refs = ($hash_w, $hash_x, $hash_y, $hash_z); my ($max, $max_i); for ( 0 .. $#h_refs ) { my $max_v = max values %{ $h_refs[$_] }; if ( ! defined $max \|\| $max_v > $max ) { ($max, $max_i) = ($max_v, $_); } } print "The max value is $max\n"; print "It is in the hash referenced by index $max_i\n";` [download] Cheers - L~R After re-reading the question for the 3rd time, I am not sure "which hash" is actually part of the question and was just an innoculous comment - shrug	[reply] [d/l]
Re^2: Getting Max Value from Different Hashes by polettix (Vicar) on Aug 01, 2005 at 15:52 UTC
Corion's solution solves the problem - the OP never talks about knowing where the winner value comes from, and his working-but-inefficient-and-inelegant (OP's words!) solution proves this IMHO. Maybe you got misleaded by his example: `300 # from z` [download] Update: stroke fool observation. I'll read the whole answer next time :) Flavio perl -ple'$_=reverse' <<<ti.xittelop@oivalf Don't fool yourself.	[reply] [d/l]
Re^3: Getting Max Value from Different Hashes by Limbic~Region (Chancellor) on Aug 01, 2005 at 16:03 UTC
frodo72, Perhaps you missed the bottom sentence where I stated that after re-reading the question 3 times I was no longer under the impression that the comment was anything more than a comment. It was small and an after-thought and easily missed. Cheers - L~R	[reply]
Re^4: Getting Max Value from Different Hashes by polettix (Vicar) on Aug 01, 2005 at 16:14 UTC
Re^2: Getting Max Value from Different Hashes by neversaint (Deacon) on Aug 02, 2005 at 01:51 UTC
Dear Limbic and all, You should never resort to sorting to find the max or min value of a list unless the side effect of sorting has a benefit later on. Thanks so much for those valuable insights. I am intrigued with your statement above. I wonder why it is so? Also this comment: ... when possible, uses a C implementation that makes it really fast I thought the built in sort function "is" implememented under "C" already? right? --- neversaint and everlastingly indebted.......	[reply]
Re^3: Getting Max Value from Different Hashes by Eimi Metamorphoumai (Deacon) on Aug 02, 2005 at 11:55 UTC
You should never resort to sorting to find the max or min value of a list unless the side effect of sorting has a benefit later on. Thanks so much for those valuable insights. I am intrigued with your statement above. I wonder why it is so? Because `sort` has to find the order of all the elements, not just find the largest one. So if you've got 1000 items, it's spending all its time putting the 999 you don't care about in the right order. (Actually, it takes O(n log n) to sort a list, but only O(n) to find the maximal element using a simple scan.) ... when possible, uses a C implementation that makes it really fast I thought the built in sort function "is" implememented under "C" already? right? Well, yes, but if you specify a block to sort by, it has to go back into perl to call that on every pair of elements. IIRC, there are a few blocks that have been hardcoded (`{$a <=> $b}`, `$b cmp $a`, etc), but if all you care about is a single value, there's no point in sorting everything to get it.	[reply] [d/l] [select]
Re^3: Getting Max Value from Different Hashes by Limbic~Region (Chancellor) on Aug 02, 2005 at 12:35 UTC
neversaint, Eimi Metamorphoumai has already done a great job of answering your question. I just wanted to try and make something clear as I made the poor mistake of assuming something would be obvious. Using a water mark algorithm is the best way of finding a max/min value in an unsorted list. List::Util provides such an algorithm that uses a C implementation when and where possible. This isn't comparing apples and apples since both are in C. One is doing far less work (as was pointed out by Eimi Metamorphoumai). So unless you need the values sorted for some other reason later on, don't use sort for this. Cheers - L~R	[reply]
Re: Getting Max Value from Different Hashes by blazar (Canon) on Aug 01, 2005 at 14:16 UTC
Given 4 distinct hashes with only one key-value, how can we find the maximum value, efficiently? Yes, the values of these hashes will be differrent in different running. `my $hash_w = { w => 100 }; my $hash_x = { x => 200 }; my $hash_y = {}; # no value, but in other cases it can have one my $hash_z = { x => 300 };` [download] Hmmm, you do not have "4 distinct hashes", but "4 distinct hasherefs", and the fact that they have each "only one key-value" seems to me to be mostly irrelevant. However I cannot help pointing out that the snippet above suggests you may have chosen your data structures poorly. Whatever, `my @values=map values %$_, $hash_w, $hash_x, $hash_y, $hash_z;` [download] will give you all the values. Now these are only four values, so a whole sort wouldn't probably be too penalizing, but it would still be more than is actually needed. So you could either roll your own `max` sub or use that from List::Util.	[reply] [d/l] [select]
Re: Getting Max Value from Different Hashes by polettix (Vicar) on Aug 01, 2005 at 15:48 UTC
Apart from the comment by Limbic~Region above, be sure to remember that sort assumes lexicographical order by default. This means that 20 would come after 100. If you want to do numeric comparison instead, you'd use the spaceship operator: `my $max_val = (sort { $a <=> $b } @all)[0];` [download] Flavio perl -ple'$_=reverse' <<<ti.xittelop@oivalf Don't fool yourself.	[reply] [d/l]
Re: Getting Max Value from Different Hashes by Anonymous Monk on Aug 01, 2005 at 14:17 UTC
My guess is that the biggest gain you could make is by not storing four values in four different hashes. The overhead of having references to four tiny hashes just dwarves whatever you win by selecting the appropriate way of finding the maximum of four values.	[reply]
Re^2: Getting Max Value from Different Hashes by Anonymous Monk on Aug 01, 2005 at 15:47 UTC
Don't guess! Benchmark! use List::Util; use Benchmark 'cmpthese'; our($h0, $h1, $h2, $h3); our @vals = map {int rand 100} 1 .. 4; $$h0{key0} = $vals[0]; $$h1{key1} = $vals[1]; $$h2{key2} = $vals[2]; $$h3{key3} = $vals[3]; our($m1, $m2, $m3, $m4, $m5, $m6); cmpthese -1 => { h1 => '$m1 = List::Util::max values %$h0, values %$h1, values %$h2, values %$h3', h2 => '$m2 = List::Util::max map {values %$_} $h0, $h1, $h2, $h3' +, h3 => '$m3 = (sort values %$h0, values %$h1, values %$h2, values %$h3)[-1]', h4 => '$m4 = (sort map {values %$_} $h0, $h1, $h2, $h3)[-1]', l1 => '$m5 = List::Util::max @vals', l2 => '$m6 = (sort @vals)[-1]', }; __END__ Rate h4 h2 h3 h1 l2 l1 h4 160777/s -- -37% -46% -66% -68% -89% h2 255999/s 59% -- -13% -46% -49% -83% h3 295080/s 84% 15% -- -38% -42% -80% h1 477204/s 197% 86% 62% -- -6% -68% l2 506415/s 215% 98% 72% 6% -- -66% l1 1483834/s 823% 480% 403% 211% 193% -- [download] Your guess it right though. Even the fastest solution using hashes (in combination with `List::Util::max`) is slower than sorting the list and taking the last element.	[reply] [d/l]
Re: Getting Max Value from Different Hashes by anonymized user 468275 (Curate) on Aug 01, 2005 at 16:58 UTC
To avoid having to keep on testing against a weird initial value or undefined (-infinity not being allowed), this method is inelegant but seems efficient: `my $max = max( values( %hash_w ) ); # first one separately for my $href ( \%hash_x, \%hash_y, \%hash_z ) { my $try = max( values( %$href ) ); ( $try > $max ) and $max = $try; }` [download] One world, one people	[reply] [d/l]