RE: [FWP] Closest hash value

[lr@hpl.hp.com]

> From: Ronald J Kimball [mailto:rjk@linguist.dartmouth.edu]
> Sent: Friday, July 16, 1999 11:17
> To: Edward M. Perry
> Cc: fwp@technofile.org
> Subject: Re: [FWP] Closest hash value
>
> On Fri, Jul 16, 1999 at 01:00:21PM -0500, Edward M. Perry wrote:
> >
> > 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.
> >
> > $key  = 5;
> > %h    = (1=>'one', 2=>'two', 4=>'four', 8=>'eight');
> >
> > %temp = map { abs($_-$key) => $_ } keys %h;
> > $val  = $h{$temp{(sort({$a<=>$b} keys %temp))[0]}};
> >
> > Any ideas?
>
> You don't need %temp; just sort directly.
>
> $val = (sort {abs($a - $key) <=> abs($b - $key)} keys %h)[0];
>
> Of course, you could use an Orcish Maneuver or a Schwartzian Transform
for
> the sort if you wanted.

I rejected any 'sort' because it is an O(N * logN) solution, whereas
scanning the keys in sequence is an O(N) solution.  Of course, Edward
does say 'the hash is small', so it doesn't matter ... YET!

--
Larry Rosler
Hewlett-Packard Laboratories
http://www.hpl.hp.com/personal/Larry_Rosler/
lr@hpl.hp.com



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