perl - 在Perl中对数组进行二进制搜索

Question

我有一个十六进制数字数组，我需要遍历其他数字并检查它们是否出现在该数组中。现在，我正在使用foreach循环，每次循环遍历整个数组。有没有一种方法可以使它更快，方法是首先对数组进行排序，然后对它执行二进制搜索。

目前的代码：

sub is_bad_str{
  my ($str, @keys) = @_;
  my $flag = 0;
  my ($key, $hex_num);
        if ($str =~ m/14'h([0-9a-f][0-9a-f][0-9a-f][0-9a-f])/;){ #'# fixes bad highlighting
  $hex_num = $1;
      }
  if (defined $hex_num){
    foreach $key (@keys){
        if ($hex_num =~ /\Q$key\E/i){
            $flag = 1;
            last;
        }
    }
  }
  if (($flag == 0) && (defined $hex_num)){
    return 1;#Bad str
  }else{
    return 0;#Good str
      }
}

Answer 1

在Perl中，有四种策略可以对一组数据进行有效的批量搜索。

下文概述了完整的分析，但总而言之，哈希查询和更差的BST当然可以提供具有大量搜索次数的平均随机数据集的最佳性能。




数组的二进制（半间隔）搜索。

显然，这是一种标准的算法方法。

绩效成本：


O(N * log N)用于初始排序。
排序后平均O(N)用于在列表中插入/删除数据。 Perl数组不是链接列表，因此它不是O(log N)。
每次搜索O(log N)。




实现：the algorithm非常简单，DIY很容易。像往常一样，存在CPAN模块，并且无论如何应该应该使用CPAN模块代替DIY：Search::Binary。


Binary Search Trees（BST）

绩效成本：


O(N * log N)用于初始排序。
平均O(log N)用于排序后在列表中插入/删除数据
每次搜索O(log N)。




实现：CPAN上存在以下几种类型：Tree::Binary::Search，Tree::Treap，Tree::RedBlack。后两个have better average performance and smaller performance fluctuations, algorithmically。

比较：如果数据将更改，则必须使用BST以避免重新分类费用。如果您的数据是随机的并且一旦排序就永远不会改变，则可以在BST上使用简单的二进制搜索，但是如果性能的每一盎司都可以更好地调整BST（如果您知道查找的结果，BST可以比列表二进制搜索进行更快的平均搜索优化。基于数据分布的成本-请参见Wiki's "Optimal binary search trees" section，或者如果您的数据分布偏爱Treap或Red / Black等特殊树之一）。


缩写（短路）扫描查找。

这些是对未排序列表的线性扫描搜索，找到该项目后将停止搜索。

性能：每次搜索随机数据均使用O(N)，但O(N)（例如，N/2）要比grep之类的完整列表搜索更快。无需额外费用。

实现：在Perl中有3种方法可以实现它们：


Smart match运算符（~~）。问题在于它仅在Perl 5.10及更高版本中可用。
一旦找到，您自己的循环就会执行next;。
List::MoreUtils模块的first()子例程。


比较：


首先，在上述3种实现中，List::MoreUtils::first比DIY循环要快，因为它是在XS中实现的。因此应在5.10之前的Perl版本中使用。智能匹配可能同样快，尽管在Perl 5.10+中选择一个或另一个之前，我会对两者进行基准测试。
其次，将短路搜索与其他方法进行比较，只有3种边缘情况应该使用：

A.内存限制。排序列表搜索，BST和哈希查找都至少具有2*N的内存占用量。如果面临严重的内存限制（给定列表大小），以致N vs 2*N内存成为不可协商的成本障碍，那么您可以使用短路搜索并及时支付性能损失。
当您批量/逐行处理大型数据集时，尤其如此，这样可以避免首先将整个数据存储在内存中。

B.如果您的数据以这样的方式进行分配和预排序，以使VAST大多数搜索将在列表的开头找到它们的采石场。如果是这样，尽管它的O（log N）平均搜索速度明显更快，但它可能会胜过像二进制搜索的BST这样的更出色的方法。仍然很难胜过哈希查找，但稍后会介绍更多。

C.如果执行的搜索数量与列表大小相比很小，则短路搜索优于BST或排序列表搜索，在这种情况下，前两种方法的初始排序成本（O(N log N)）会超过搜索节省量。由于BST与线性搜索的节省量为O(M * N)，其中M为搜索次数，因此，为了实现平均节省，搜索次数M必须小于O（log N），但第二次可能要更多边缘情况，由于数据分布，平均扫描成本小于O(N)。



哈希查询

绩效成本：


O(N) + epsilon用于初始哈希创建（由于可能发生键冲突，因此对于严格意义上的随机大数据集而言，严格来说，这不是O（N）。我对Perl的哈希实现了解得不够多，只能说明它可能会出现对任何哈希图的关注。
排序后平均在列表中插入/删除数据的平均O(1)（由于键冲突，+与初始哈希创建相同的epsilon）。
每次搜索O(1)（加上相同的epsilon）。




实现方式：

my %lookup = map { $_ => 1 } @list; 
my @lookup2{ @list } = (); # Alternative method of creating a hash
sub find { return exists $lookup{$_[0]; }

比较：


首先，与BST和短路搜索相比，将相同的逻辑应用于比较具有散列查找的短路搜索和BST。例如，您应该始终在线性搜索上使用哈希映射，但相同的两种情况除外（数据集使得平均列表扫描变为O(1)而不是O(N)，并且搜索次数与数据集的比率大小使得搜索的总费用少于创建哈希所需的O(N)。
其次，“平均”哈希表显然比BST或二进制列表搜索要快得多。这里唯一可能的极端情况是，您以某种方式偶然进入了一个数据集，该数据集设法使存储桶超载，并将多余的“ε”成本变成足够大的重量，从而开始表现不佳O(log N)。

我强烈怀疑它是否甚至有可能实现，但是同样，对于Perl对hashmap的实现了解不足，甚至无法证明即使是最差的数据集也永远不会发生。