perl - 在 Perl 哈希中查找最近的选项

Question

我有一个 hashref，其中的数据与日历年的日期相关联，例如:

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

我可以使用 DateTime 获取一年中的第几天:

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

但是，我正在尝试找出最有效的方法来处理当前日期与散列中的任何日期都不匹配的情况。在这些情况下，我总是想“四舍五入”。例如。今天(今年的第 7 天)，我想加载键为“5”的条目，因为它是最近的“最新”条目。

有没有办法在 hashref 中选择一个最接近 <= $dayOfTheYear 的键？ ？如果我使用 DBD，我可以执行如下查询:

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

但是，如果我可以在 Perl 中本地执行某些操作，我宁愿避免需要创建数据库并调用它。

Answer 1

一种方式，期待多次搜索

use List::MoreUtils qw(last_value);

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

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

对于任何输入，这将返回小于或等于的最后一个元素，因此是感兴趣的键。

仅使用散列的缺点是需要额外的数据结构来构建。当然，任何提供此类查找的图书馆也必须这样做，但是这些图书馆随后会带来其他好东西，并且性能可能会好得多(取决于这样做的频率)。

如果需要为给定的散列很多进行这种“舍入”，那么构建一个查找表几天，将每个与散列中最近的键相关联是有意义的。^{† ‡}

如果@entries降序排列 ( $b <=> $a ) 然后是核心 List::Util::first做到了。

---

^† 例如

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 }
    }   
}; 

这枚举了一年中的几天，如问题中指定的那样。

---

^‡ 如果天数(最多 366 天)以外的事情需要这样做，可能会出现长列表，则可以通过对排序列表进行二进制搜索来提供更好的算法行为( O(log n)).

上面使用的库，List::MoreUtils , 还有 lower_bound与 O(log n)

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

所以这需要一些调整，因为

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 ];