在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)對於每個搜索。
     
     

   實施：the algorithm就是這麼簡單，DIY很容易。像往常一樣，CPAN模塊存在，可能應該無論如何代替DIY：Search::Binary。

   ---

2. Binary Search Trees（BSTS）

   性能成本：

   • O(N * log N)用於初始排序。
   • O(log N)平均插入/刪除列表中的數據一旦排序
   • O(log N)爲每個搜索。

   
   

   實施：Tree::Binary::Search，Tree::Treap，Tree::RedBlack：幾種口味上存在CPAN。後兩個have better average performance and smaller performance fluctuations, algorithmically。

   比較：如果數據會發生變化，你必須使用BST，以避免重新排序的成本。如果數據是隨機的並且一旦排序就不會改變，那麼可以使用BST進行簡單的二分搜索，但是如果每最後一盎司的性能問題可以更好地調整BST（BST可以針對快速平均搜索進行優化，而不是列表二進制搜索，如果您知道查找基於數據分佈的成本 - 請參閱Wiki's "Optimal binary search trees" section，或者您的數據分佈偏好Treap或Red/Black等特殊樹）。

   ---

3. 縮（短路）掃描查找。

   這些是對未排序列表進行線性掃描搜索，一旦找到該項目，停止搜索。

   性能：O(N)每次搜索的隨機數據，但更快的O(N)（比如，N/2）比全列表搜索類似grep。沒有額外的費用。

   實施：有3種方式做他們在Perl：

   • 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與2*N內存成爲不可協商的成本障礙，那麼您使用短路搜索並及時支付性能損失。 當您正在逐行處理大批量數據時，尤其如此，以避免首先將所有內容存儲在內存中。

     B.如果您的數據是按照VAST大多數搜索的結果在列表的最開始發現其採石場的方式進行分發和預先排序的。如果是這樣的話，儘管它們的O（log N）平均搜索速度明顯更快，但它可能會優於像二進制搜索的BST這樣的發燒友方法。它仍然很難超越散列查找，但更多的在後面。

     C.如果執行的搜索次數與列表大小相比相當小，在這種情況下，前兩種方法（O(N log N)）的初始排序成本將超過搜索節省。由於BST與線性搜索的節省是O(M * N)其中M是搜索次數，因此M的搜索次數M必須小於O（logN）以實現平均節省，但在第二個邊緣情況下可能會更多由於數據分佈，平均掃描成本小於O(N)。

   ---

4. 哈希查找

   性能開銷：

   • O(N) + epsilon初始哈希創建（這不是嚴格意義上講O（N）的隨機大數據集，由於可能的關鍵衝突。我不知道eno呃關於Perl的散列實現來闡明這一點，而不是說它可能成爲任何hashmaps的關注點。
   • O(1)一旦排序後插入/刪除列表中的數據的平均值（+與由於關鍵衝突導致的初始散列創建相同的ε）。
   • O(1)爲每個搜索（加上相同的epsilon）。
     
     

   實施：

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

   比較：

   • 首先，相同的邏輯適用於將短路搜索與散列查找與BST與短路搜索進行比較。例如，你應該總是使用包含HashMap了線性搜索，用相同的兩個邊緣情況除外（數據集是這樣的：平均目錄掃描成爲O(1)代替O(N)和搜索的數據集大小排名的比例，使總創建散列所需的搜索成本小於O(N)）。

   • 其次，包含HashMap平均明顯高於BSTS或二進制列表搜索快得多。這裏唯一可能的邊緣情況是，您不知何故陷入了一個數據集，該數據集設法使存儲桶超負荷，並將該額外的「epsilon」成本轉化爲足夠大的重量，從而啓動表現不佳的O(log N)。

     我強烈懷疑這是否是甚至遠程可能的，但同樣的，不知道有足夠的瞭解Perl的實現包含HashMap的證明，它永遠不會發生，即使是最壞的數據集。

Answer 2

如果你只是打算做一個搜索，然後排序將需要更長的時間比執行單一的線性掃描，所以你可能也只是與遍歷堅持陣列。對於一個小陣列，或者如果您可以有多個匹配，您可能還需要查看grep函數;使用起來更簡單一些，但它會一直檢查候選匹配的整個列表，而不是在找到匹配時停止。

如果要多次搜索，將數組的值放入哈希中並執行哈希查找將比搜索數組的速度更快，即使將其排序並執行二進制搜索（假設您可以負擔得起記憶成本，但你幾乎肯定可以）。