tìm kiếm nhị phân trong một mảng trong Perl

Question

Tôi có một số các số hex và tôi cần phải đi qua các số khác và kiểm tra xem chúng có xuất hiện trong mảng đó hay không. Ngay bây giờ tôi đang sử dụng một vòng lặp foreach mà đi qua toàn bộ mảng mỗi lần. Có cách nào để làm cho nó nhanh hơn bằng cách phân loại mảng lúc đầu, và sau đó thực hiện tìm kiếm nhị phân trên đó.

Mã vào lúc này:

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

Có bốn chiến lược để thực hiện tìm kiếm hàng loạt hiệu quả trong một tập hợp dữ liệu trong Perl.

Phân tích đầy đủ được trình bày bên dưới, nhưng tóm lại, hiệu suất tốt nhất trên tập dữ liệu ngẫu nhiên trung bình với số lượng tìm kiếm đáng kể do khóa băm cung cấp, theo sau là BST tệ hơn nhiều.

---

1. Binary (nửa khoảng) tìm kiếm của một mảng.

   Đây rõ ràng là một cách tiếp cận thuật toán chuẩn.

   Chi phí

   Hiệu suất:

   • O(N * log N) cho phân loại ban đầu.
   • O(N) trung bình cho việc chèn/xóa dữ liệu trong danh sách sau khi được sắp xếp. Mảng Perl KHÔNG được liên kết với danh sách, vì vậy nó không phải là O(log N).
   • O(log N) cho mỗi tìm kiếm.
     
     

   Thực hiện: the algorithm là đơn giản như vậy mà DIY là dễ dàng. Như thường lệ, các mô-đun CPAN tồn tại và có lẽ nên được sử dụng thay cho DIY anyway: Search::Binary.

   ---

2. Binary Search Trees (BSTs) Chi phí

   Hiệu suất:

   • O(N * log N) cho phân loại ban đầu.
   • O(log N) trung bình cho chèn/xóa dữ liệu trong danh sách sau khi được sắp xếp
   • O(log N) cho mỗi tìm kiếm.

   
   

   Thực hiện: nhiều hương vị tồn tại trên CPAN: Tree::Binary::Search, Tree::Treap, Tree::RedBlack. Sau hai số have better average performance and smaller performance fluctuations, algorithmically.

   So sánh: Nếu dữ liệu S change thay đổi, bạn phải sử dụng BST để tránh chi phí sắp xếp lại. Nếu dữ liệu của bạn là ngẫu nhiên và không bao giờ thay đổi khi được sắp xếp, bạn có thể sử dụng tìm kiếm nhị phân đơn giản trên BST nhưng BST có thể được điều chỉnh tốt hơn nếu mỗi ounce cuối cùng của hiệu suất (BST có thể được tối ưu hóa để tìm kiếm trung bình nhanh hơn tìm kiếm nhị phân danh sách nếu bạn biết tra cứu của mình chi phí dựa trên phân phối dữ liệu - xem Wiki's "Optimal binary search trees" section hoặc nếu phân phối dữ liệu của bạn ưu tiên một trong những cây đặc biệt như Treap hoặc Red/Black).

   ---

3. Tra cứu quét viết tắt (viết tắt là ngắn).

   Đây là các tìm kiếm quét tuyến tính trên danh sách chưa được sắp xếp để DỪNG tìm kiếm khi tìm thấy mục.

   Performance: O(N) mỗi tìm kiếm cho dữ liệu ngẫu nhiên, nhưng một nhanh hơn O(N) (nói, N/2) so với một tìm kiếm đầy đủ danh sách như grep. Không có thêm chi phí.

   Thực hiện: Có 3 cách để làm cho họ trong Perl:

   • Smart match điều hành (~~). Vấn đề là nó chỉ có sẵn trong Perl 5.10 trở lên.
   • Vòng lặp của riêng bạn next; một lần được tìm thấy.
   • List::MoreUtils mô-đun của first() chương trình con.

   So sánh:

   • Thứ nhất, giữa 3 triển khai trên, List::MoreUtils::first là nhanh hơn so với vòng DIY bởi vì nó thực hiện trong XS; vì vậy nó nên được sử dụng trong các phiên bản Perl trước 5.10. Trận đấu thông minh có lẽ chỉ là nhanh, mặc dù tôi sẽ đánh giá điểm số hai trước khi bạn chọn một hoặc một trong Perl 5.10+.

   • Thứ hai, so sánh tìm kiếm ngắn mạch với các phương pháp khác, chỉ có 3 trường hợp cạnh nơi mà nó nên được sử dụng:

     A. hạn chế bộ nhớ. Cả hai tìm kiếm danh sách được sắp xếp, BST và tra cứu băm có dấu chân bộ nhớ tại ít nhất 2*N. Nếu bạn phải đối mặt với hạn chế về bộ nhớ (với kích thước danh sách của bạn) đủ nghiêm trọng, thì bộ nhớ N và 2*N trở thành rào cản chi phí không thể thương lượng, sau đó bạn sử dụng tìm kiếm ngắn mạch và trả tiền phạt hiệu suất kịp thời. Điều này đặc biệt đúng khi bạn đang xử lý một tập hợp dữ liệu lớn theo lô/từng dòng, để tránh lưu trữ toàn bộ nội dung trong bộ nhớ ngay từ đầu.

     B. Nếu dữ liệu của bạn được phân phối và được sắp xếp trước sao cho phần lớn các tìm kiếm sẽ tìm thấy mỏ đá của chúng ở đầu danh sách. Nếu đó là trường hợp, nó có thể làm tốt hơn các phương pháp fancier như BST tìm kiếm nhị phân mặc dù tìm kiếm trung bình O (log N) nhanh hơn rõ ràng của họ. Nó vẫn sẽ khó để làm tốt hơn so với tra cứu băm, nhưng nhiều hơn về điều đó sau này.

     C. Tìm kiếm ngắn được ưu tiên so với BST hoặc tìm kiếm danh sách được sắp xếp nếu số lần tìm kiếm được thực hiện khá nhỏ so với kích thước danh sách, trong trường hợp đó chi phí phân loại ban đầu của 2 phương pháp đầu tiên (O(N log N)) sẽ lớn hơn tiết kiệm tìm kiếm. Do tiết kiệm BST so với tìm kiếm tuyến tính là O(M * N) trong đó M là số lần tìm kiếm, nó theo sau số lần tìm kiếm M phải nhỏ hơn O (log N) để nhận ra mức tiết kiệm trung bình, nhưng có thể nhiều hơn trong trường hợp cạnh thứ hai nơi chi phí quét trung bình nhỏ hơn O(N) do phân phối dữ liệu.

   ---

4. tra cứu Hash

   Performance Chi phí:

   • O(N) + epsilon để tạo băm ban đầu (Nó không nói đúng O (N) cho một lớn ngẫu nhiên tập dữ liệu, do va chạm có thể xảy ra. Tôi không biết eno ugh về việc thực hiện băm của Perl để làm rõ điều này ngoài trạng thái rằng nó có thể trở thành mối quan tâm đối với bất kỳ hashmaps nào.
   • O(1) trung bình cho chèn/xóa dữ liệu trong danh sách sau khi được sắp xếp (+ cùng epsilon như tạo băm ban đầu do xung đột chính).
   • O(1) cho mỗi tìm kiếm (cộng với cùng epsilon).
     
     

   Thực hiện:

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

   So sánh:

   • Thứ nhất, cùng một logic áp dụng để so sánh tìm kiếm ngắn mạch với tra cứu băm như với BST so với tìm kiếm ngắn mạch. Ví dụ, bạn nên ALMOST luôn sử dụng hashmaps trên tìm kiếm tuyến tính, trừ trường hợp hai cạnh giống nhau (tập dữ liệu sao cho quét danh sách trung bình trở thành O(1) thay vì O(N) và tỷ lệ số tìm kiếm cho kích thước tập dữ liệu làm cho tổng hợp chi phí tìm kiếm ít hơn O(N) cần thiết để tạo băm).

   • Thứ hai, hashmaps trung bình là rõ ràng nhanh hơn nhiều so với BSTs hoặc danh sách nhị phân tìm kiếm. Trường hợp duy nhất có thể xảy ra ở đây là bạn bằng cách nào đó vấp ngã vào một tập dữ liệu quản lý quá tải các thùng và biến chi phí "epsilon" thừa thành một khối lượng đủ lớn để nó bắt đầu hoạt động kém hơn O(log N). Tôi chắc chắn rằng nó thậm chí còn có khả năng điều khiển từ xa, nhưng một lần nữa, không biết đủ về việc triển khai các hashmaps của Perl để chứng minh rằng nó sẽ không bao giờ xảy ra ngay cả khi tập dữ liệu tồi tệ nhất.

Answer 2

Nếu bạn chỉ cần đi để làm một tìm kiếm, sau đó phân loại sẽ mất nhiều thời gian hơn so với thực hiện một quét tuyến tính duy nhất, vì vậy bạn có thể cũng chỉ gắn bó với Looping trên mảng. Đối với một mảng nhỏ hoặc nếu bạn có thể có nhiều kết quả phù hợp, bạn cũng có thể muốn xem hàm grep; nó dễ sử dụng hơn một chút, nhưng nó sẽ luôn kiểm tra toàn bộ danh sách các trận đấu ứng cử viên thay vì dừng lại khi tìm thấy một trận đấu.

Nếu bạn định tìm kiếm nhiều lần, đặt giá trị của mảng vào băm và tìm kiếm băm sẽ nhanh hơn tìm kiếm mảng, ngay cả khi bạn sắp xếp và thực hiện tìm kiếm nhị phân (giả sử bạn có thể đủ khả năng chi phí bộ nhớ, nhưng bạn gần như chắc chắn có thể).