Re: [FWP] Closest hash value

[John Porter <jdporter@min.net>]

> > "Edward M. Perry" <eperry@learjet.com> writes:
> > 
> > > Here is the problem: given a key ($key), and a hash (%h), I want the value
> > > of the closest hash key. I came up with this which is only moderately fun.
> > > Really it works pretty well, assuming keys are numeric and the hash is
> > > small. Mapping to %temp is weak.  
> > > 
> > > An array seems unreasonable because in reality the keys (or indicies) are
> > > large and the array would be very sparse.
> 
> The real problem is pretty small, about 100 keys, 20 lookups, and speed is
> not really a concern. A B-Tree would be overkill for this problem, but
> probably would be a good solution for a larger data set. Your suggestion
> did get me thinking about good ways to binary search a set of hash keys
> though...Gotta go do it. Thanks.

Here's a thoroughly inefficient but (I think) very fun solution.
I apologize for the hideousness.  :-)



sub closest {
  my( $new_val, $set_hr ) = @_;
  my @vals = ( keys %$set_hr, $new_val );
  my @indexes = sort { $vals[$a] <=> $vals[$b] } ( 0 .. $#vals );
  @vals = @vals[ @indexes ];
  my $i = (sort { $indexes[$b] <=> $indexes[$a] } ( 0 .. $#indexes ))[0];
  my @v = (@vals,@vals,@vals)[map{$#vals+$i+$_}(0..2)];
  return( abs($v[2]-$v[1]) > abs($v[0]-$v[1]) ? $v[0] : $v[2] );
}

#
# test it:
#

my %set = map { $_ => 1 } qw( 21 7 5 9 34 6 87 );
for ( 1, 11, 15, 95 ) {
  print "$_: ", closest($_,\%set), "\n";
}



John Porter


==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe