Perl Hash:如果值在一个范围内，则获取键

Question

我有一个像这样有100K个键(主键)的二维散列，我需要得到主键——只有在满足特定条件时才能得到水果的名称;

like -如果价格在35到55之间;期望输出橙和葡萄.

有一个独特价格范围的列表(计数数百)，我需要每个范围内的水果列表。

对每个价格范围一次又一次地遍历哈希需要花费大量时间。有没有一种方法可以让我们快速完成，而不是在每个价格范围内循环遍历整个哈希?

哈希格式:

$fruits{"Mango"}{color}=Yellow
$fruits{"Mango"}{price}=80
$fruits{"Orange"}{color}=Orange
$fruits{"Orange"}{price}=40
$fruits{"Grape"}{color}=Green
$fruits{"Grape"}{price}=50

Answer 1

下面是一个示例，说明如何通过按数字顺序对价格进行一次扫描。这应该比对每个价格范围扫描一次整个哈希要快:

package Main;
use v5.20.0;
use feature qw(say);
use strict;
use warnings;
use experimental qw(signatures);
{
my %fruits;
$fruits{Mango}{color}  = "Yellow";
$fruits{Mango}{price}  = 80;
$fruits{Orange}{color} = "Orange";
$fruits{Orange}{price} = 40;
$fruits{Grape}{color}  = "Green";
$fruits{Grape}{price}  = 50;
my @ranges = ( [35, 55], [45, 55], [2, 85] );
my $self = Main->new(
fruits => %fruits,
ranges => @ranges
);
$self->init_mapping_arrays();
my $names = $self->get_fruit_names_for_all_ranges();
}

sub init_mapping_arrays( $self ) {
my @prices;
my @names;
for my $fruit (keys %{ $self->{fruits} }) {
push @names, $fruit;
push @prices, $self->{fruits}{$fruit}{price};
}
my @idx = map { $_->[0] }
sort { $a->[1] <=> $b->[1] } map { [$_, $prices[$_]] } 0..$#prices;
$self->{prices} = [@prices[@idx]];
$self->{names} = [@names[@idx]];
}
sub get_fruit_names_for_all_ranges ($self) {
my @names;
my $prices = $self->{prices};
my $ranges = $self->{ranges};
for my $i (0..$#$prices) {
for my $range (0..$#$ranges) {
if (   ($ranges->[$range][0] <= $prices->[$i])
&& ($ranges->[$range][1] >= $prices->[$i]))
{
push @{$names[$range]}, $self->{names}[$i];
}
}
}
return @names;
}
sub new( $class, %args ) { bless %args, $class }

如果这还不够快，可以通过对范围进行排序来进一步优化get_fruit_names_for_all_ranges()子。

Answer 2

如果对水果进行排序，则两次二分查找将很快找到水果。

sub search_cmp 
my @fruits = (
{ name => "Orange", price => 40, ... },
...
);
my @ranges = (
[ 35, 55 ],
...   
);
my @sorted_fruits = sort { $a->{price} <=> $b->{price} } @fruits;
for my $range (@ranges) {
my $i = binsearch { $a <=> $b->{price} } $range[0], @sorted_fruits, 0;
$i = ~$i if $i < 0;
my $j = binsearch { $a <=> $b->{price} } $range[1], @sorted_fruits, $i;
$j = ~$j - 1 if $j < 0;
say "[$range->{min}, $range->{max}]: @fruits[$i..$j]";
}

sub _unsigned_to_signed { unpack('j', pack('J', $_[0])) }
sub binsearch(&$@;$$) {
my  $compare = $_[0];
#my $value   = $_[1];
my  $array   = $_[2];
my  $min     = $_[3] // 0;
my  $max     = $_[4] // $#$array;
return -1 if $max == -1;
my $ap = do { no strict 'refs'; *{caller().'::a'} };  local *$ap;
my $bp = do { no strict 'refs'; *{caller().'::b'} };  local *$bp;
*$ap = ($_[1]);
while ($min <= $max) {
my $mid = int(($min+$max)/2);
*$bp = ($array->[$mid]);
my $cmp = $compare->()
or return $mid;
if ($cmp < 0) {
$max = $mid - 1;
} else {
$min = $mid + 1;
}
}
return _unsigned_to_signed(~$min);
}

---

性能分析

最好的最坏情况是O(R * F)，因为每个范围都可以匹配所有水果。

要求替换的OP描述的朴素方法是O(R * F)。那么它是尽可能快的吗?不，因为朴素方法总是采用最坏的情况。

在实践中，如果我们可以假设每个范围只匹配几个水果，我们可以从上面得到更好的结果:O((F + R) log F)