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

I have a list of numbers in a hash array "num" and need to be able to look up the number that is closest to a given input number, "x". In other words:
$num{'15'}=1;
$num{'20'}=2;
$num{'25'}=3;
$num{'30'}=4;
$x=28;

[download]
How would I write code to return the number 4 given x=28? Or alternatively if x=16 then I would return 2. I also need to return the higher number if x falls in between two numbers. The only way solution I can think of is to use if statements, but I will have about a dozen numbers in the hash and writing if statements would take a while.

Thanks.

Replies are listed 'Best First'.
Re: List of Numbers
by Abigail-II (Bishop) on Jan 18, 2003 at 20:53 UTC
    If you have to do many queries, I would sort the keys, and then perform binary search on the sorted list.

    Abigail

[reply]
Re: List of Numbers
by gjb (Vicar) on Jan 18, 2003 at 20:29 UTC

    If it's no coincidence that 15 gets mapped to 1, 20 to 2, etc, i.e. all multiples of some number and the corresponding values increasing, then you could view the problem a little differently. There's a linear relation between (15, 1), (20, 2), (25, 3),... which can be expressed by y = x/5 - 2. All values you give satisfy this equation as can be verified easily.

    Now we can compute the corresponding number for $x simply as: 

      $number = ceil($x/5 - 2);

    [download]

    Hope this helps, -gjb-

[reply]
[d/l]
[select]
      Sorry I was just using 15,20,25 as examples. Any number could populate the hash and the resulting value in the hash could be anything as well.
[reply]
Re: List of Numbers
by BrowserUk (Patriarch) on Jan 18, 2003 at 20:50 UTC

    If the rest of your intervals are steps of 5 then a little math manipulation does most of the work. 

    my %num = (15=>1, 20=>2, 25=>3, 30=>4);

print $_, ' maps to ', $num{ ( 1 + int( ($_ - 1) / 5) ) * 5}, $/ for 1
+0 .. 31
10  maps to  Use of uninitialized value in print 
11  maps to  1
12  maps to  1
13  maps to  1
14  maps to  1
15  maps to  1
16  maps to  2
17  maps to  2
18  maps to  2
19  maps to  2
20  maps to  2
21  maps to  3
22  maps to  3
23  maps to  3
24  maps to  3
25  maps to  3
26  maps to  4
27  maps to  4
28  maps to  4
29  maps to  4
30  maps to  4
31  maps to  Use of uninitialized value in print

    [download]
    Then you only need if statements to catch those below a minimum or greater than the highest key.

    Update The the light of the additional info you provided above, you could use this (if the size of the hash is fairly small). 

    for my $num (10,15,16,22,27,30,31) { 
    print $num, $num{
        ( 
            grep{ $_ >= $num } 
            sort{ $a <=> $b } keys %num 
        )[0]}, 
        $/; 
}

    [download]

    Again, you would need a conditional to cover those larger than the highest.

    Examine what is said, not who speaks.

    The 7th Rule of perl club is -- pearl clubs are easily damaged. Use a diamond club instead.

[reply]
[d/l]
[select]
Re: List of Numbers
by fruiture (Curate) on Jan 18, 2003 at 20:39 UTC

    If there are no further rules for the integer hash keys, it looks like:

    ++$x until exists $num{ $x } or $x > 99

    [download]

    But if there are mathematical rules for the keys, you can probably find a better way.

    --
    http://fruiture.de
[reply]
[d/l]
Re: List of Numbers
by graff (Chancellor) on Jan 20, 2003 at 05:27 UTC
    Here's a solution structured as a subroutine; the "main" portion just uses your example data, and when run at the command line, it uses the first argument after the script name as the value of "$x": 
    #!/usr/bin/perl

$num{'15'}=1;
$num{'20'}=2;
$num{'25'}=3;
$num{'30'}=4;

$x=shift;  # take value from @ARGV

print value_sought( $x ), $/;

sub value_sought
{
    my $x = shift;  # take value from @_
    foreach my $k ( sort { $a <=> $b } keys %num )
    {
        return $num{$k} if ( $x < $k );
    }
    return "$x is larger than available num keys";
}

    [download]
    But, as Abigail suggested in an earlier reply, if you're doing frequent searches over a large set of hash keys, you may want to optimize this a bit -- sort the keys into an array, check the value of $x against the middle element of that array, then the middle of the upper half or lower half as appropriate, until you hone in on the right key value; in the majority of cases, the correct element will be found in fewer iterations this way.

    (If the set of hash keys is fairly static -- you do a lot of searches over the same set of hash keys -- then having the array will also help by not having to sort the hash keys every time you do a search.)

[reply]
[d/l]
Re: List of Numbers
by OM_Zen (Scribe) on Jan 18, 2003 at 21:20 UTC
    Hi,

    The 
                 map { ($x < $_)?
                   print "[$num{$_}]\n;:
                   ($x = ($_ + $num_before) /2)?
                   print "[$num($_)]\n";:
                   next;
                   $num_before = $_;}sort keys %num;

    [download]
    shall I guess give the mathematical implementation for the logic (just wrote not tested)
[reply]
[d/l]
      Backslash found where operator expected at t line 4, near "]\"
        (Missing operator before \?)
String found where operator expected at t line 4, at end of line
        (Missing semicolon on previous line?)
syntax error at t line 4, near "print "["
  (Might be a runaway multi-line "" string starting on line 2)
Can't find string terminator '"' anywhere before EOF at t line 4.

      [download]
      That's not even with warnings and strictures. Not to mention next doesn't work in map blocks.

      Makeshifts last the longest.

[reply]
[d/l]

Back to Seekers of Perl Wisdom