在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.

1. 二进制(半间隔)搜索数组.

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

   绩效成本:

   • O(N * log N) 用于初始分类.
   • O(N)平均一次排序后插入/删除列表中的数据.Perl数组不是链表,所以它不是O(log N).
   • O(log N) 每次搜索.
     
     

   实现:算法非常简单,DIY很容易.像往常一样,CPAN模块存在,可能应该无论如何代替DIY的使用:Search::Binary.

2. 二叉搜索树(BST)

   绩效成本:

   • O(N * log N) 用于初始分类.
   • O(log N) 平均一次排序后插入/删除列表中的数据
   • O(log N) 每次搜索.

   
   

   执行:几种口味上存在CPAN: ,Tree::Binary::Search,.Tree::Treap Tree::RedBlack后两者在算法上具有更好的平均性能和更小的性能波动.

   比较:如果数据发生变化,您必须使用BST以避免重新分类成本.如果您的数据是随机的,并且一旦排序就不会改变,您可以使用BST上的简单二进制搜索,但如果每一个最后一盎司的性能都很重要,BST可以更好地调整(如果您知道查找,BST可以针对更快的平均搜索进行优化,而不是列表二进制搜索基于数据分布的成本 - 请参阅 Wiki的"最佳二进制搜索树"部分,或者如果您的数据分布偏好Treap或Red/Black等特殊树之一.

3. 缩写(短路)扫描查找.

   这些是未排序列表上的线性扫描搜索,一旦找到项目就停止搜索.

   性能:O(N)每次搜索随机数据,但比完整列表搜索更快O(N)(比如说N/2)grep.无需额外费用.

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

   • 智能匹配运算符(~~).问题是它仅在Perl 5.10及更高版本中可用.
   • 你next;曾经找到过自己的循环.
   • List::MoreUtils模块的first()子程序.

   比较:

   • 首先,在上面的3个实现之间,List::MoreUtils::first它比DIY循环更快,因为它是在XS中实现的; 所以它应该在5.10之前的Perl版本中使用.智能匹配可能同样快,但我会在你选择Perl 5.10+中的一个之前对这两个进行基准测试.

   • 其次,将短路搜索与其他方法进行比较,只有3个边缘情况应该使用:

     A. 内存限制.排序列表搜索,BST和散列查找都至少具有内存占用2*N.如果你面对存储器限制(给你的列表大小)足够严重,NVS 2*N内存成为非流通成本障碍,那么你用短路搜索,并及时支付的性能损失.当您批量/逐行处理大型数据集时尤其如此,以避免将整个内容存储在内存中.

     B.如果您的数据是以这样的方式分发和预先排序的,那么VAST的大多数搜索都会在列表的最开头找到它们的采石场.如果是这种情况,它可能会胜过像二进制搜索的BST这样的更高级的方法,尽管它们的O(log N)平均搜索速度明显更快.它仍然难以超越散列查找,但稍后会更多.

     C.如果执行的搜索次数与列表大小相比相当小,则短路搜索优于BST或排序列表搜索,在这种情况下,前两种方法(O(N log N))的初始分类成本将超过搜索节省.由于BST与线性搜索的节省是O(M * N)M是搜索次数,因此,搜索次数M必须小于O(log N)以实现平均节省,但在第二种情况下可能更多平均扫描成本低于O(N)数据分布.

4. 散列查找

   绩效成本:

   • 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与短路搜索一样.例如,除了相同的两个边缘情况之外,你应该几乎总是使用散列图而不是相同的两个边缘情况(数据集使得平均列表扫描变为O(1)而不是O(N)并且搜索的数量与数据集大小的比率使得总成本为搜索少于O(N)哈希创建所需的搜索).

   • 其次,静止图像ON AVERAGE显然比BST或二进制列表搜索快得多.这里唯一可能的边缘情况是你以某种方式偶然发现了一个数据集,该数据集设法使存储桶过载并将额外的"epsilon"成本转化为足够大的重量,使其开始表现不佳O(log N).

     我强烈怀疑它甚至可能是远程可能的,但是再一次,对Perl的哈希映射实现不够了解,以证明即使是最糟糕的数据集也不会发生这种情况.