Find nearest option in a Perl Hash

user_656780 0
Viewed 128

I have a hashref that has data tied to days of the calendar year, for example:

 my $calendarEntries = { '1' => 'Entry 1', '5' => 'Entry 2', '15' => 'Entry 3' };

I can obtain the day of the year using DateTime:

state $moduleDateTime = require DateTime;
my $dt = DateTime->now('time_zone' => 'America/Chicago'); 
my $dayOfTheYear = $dt->strftime('%j');

However, I'm trying to figure out the most efficient way to handle situations where the current day does not match any of the days in the hash. I'd like to always "round down" in those situations. E.g. today (which is the 7th day of the year), I'd like to load the entry with the key '5', since it is the most "recent" entry.

Is there a way to select a key in a hashref that is the closest candidate for being <= $dayOfTheYear? If I were using DBD, I could do a query like this:

 'SELECT entry WHERE `key` <= ' . $dayOfTheYear . ' ORDER BY `key` DESC LIMIT 1'

But, I'd rather avoid needing to create a database and call it, if I can do something natively in Perl.

perl datetime
3 Answers

One way, expecting many searches

use List::MoreUtils qw(last_value);

my @entries = sort { $a <=> $b } keys %$calendarEntries;

my $nearest_le = last_value { $day >= $_ } @entries;

This returns the last element that is less or equal, for any input, so the key of interest.

The drawback of using simply a hash is that one needs an extra data structure to build. Any library that offers this sort of lookup must do that as well, of course, but those then come with other goodies and may be considerably better performing (depending on how often this is done).

If this 'rounding' need be done a lot for a given hash then it makes sense to build a lookup table for days, associating each with its nearest key in the hash.† ‡

If @entries is sorted descending ($b <=> $a) then the core List::Util::first does it.

† For example

my %nearest_le;

my @keys = sort { $a <=> $b } keys %$calendarEntries;

for my $day (1..366) { 
    for my $k (@keys) { 
        if ($k <= $day) { 
            $nearest_le{$day} = $k; 
        }
        else { last }
    }   
};

This enumerates days of the year, as specified in the question.

‡ If this were needed for things other than the days (366 at most), where long lists may be expected, a better algorithmic behavior is afforded by binary searches on sorted lists (O(log n)).

The library used above, List::MoreUtils, also has lower_bound with O(log n)

Returns the index of the first element in LIST which does not compare less than val.

So this needs a few adjustments, for

use List::MoreUtils qw(lower_bound);

my @keys = sort { $a <=> $b } keys %$calendarEntries;

my $nearest_le = exists $calendarEntries->{$day} 
    ? $day 
    : $keys[ -1 + lower_bound { $_ <=> $day } @keys ];
user_46533790

A nice simple solution.

use List::Util qw( max );

max grep { $_ <= $dayOfTheYear } keys %$calendarEntries

Notes:

  • Best to make sure $calendarEntries->{ $dayOfTheYear } doesn't exist first.
  • You'll need to handle the case where there is no matching key.

It's faster than sorting unless you perform many searches. But even then, we're only dealing with at most 365 keys, so simplicity is key here.

user_5899240

The simplest solution is to simply look up the value for your date, and if it is not found, go down until you find a value. In this sample, I included a rudimentary error handling.

use strict;
use warnings;
use feature 'say';

my $calendarEntries = { '1' => 'Entry 1', '5' => 'Entry 2', '15' => 'Entry 3' };
my $find = shift // 7;       # for testing purposes
my $date = get_nearest_below($calendarEntries, $find);
if (defined $date) {
    say "Nearest date below to '$find' is '$date'";
} else {                     # error handling
    warn "Nearest date below not found for '$find'";
}

sub get_nearest_below {
    my ($href, $n) = @_;
    while ($n > 0) {     # valid dates are > 0
        return $n if defined $href->{$n};   # find a defined value
        $n--;            # or go to the next key below
    }
    return undef;        # or return error if nothing is found before 0
}

Output:

$ foo.pl
Nearest date below to '7' is '5'

$ foo.pl 12
Nearest date below to '12' is '5'

$ foo.pl 123
Nearest date below to '123' is '15'

$ foo.pl 0
Nearest date below not found for '0' at foo.pl line 13.
user_7254180
Related