Hoạt động bit để tìm sự khác biệt về chuỗi

Question

Chuỗi sau đây của tôi đã cố gắng tìm sự khác biệt giữa hai chuỗi. Nhưng nó chậm khủng khiếp vì nó lặp lại độ dài của chuỗi:

#include <string> 
#include <vector> 
#include <iostream> 
using namespace std; 


int hd(string s1, string s2) { 
    // hd stands for "Hamming Distance" 
    int dif = 0; 

    for (unsigned i = 0; i < s1.size(); i++) { 
     string b1 = s1.substr(i,1); 
     string b2 = s2.substr(i,1); 

     if (b1 != b2) { 
      dif++; 
     } 
    } 

    return dif; 
} 

int main() { 

    string string1 = "AAAAA"; 
    string string2 = "ATATT"; 
    string string3 = "AAAAA"; 

    int theHD12 = hd(string1,string2); 
    cout << theHD12 << endl; 

    int theHD13 = hd(string1,string3); 
    cout << theHD13 << endl; 
} 

Có cách nào thay thế nhanh không? Trong Perl, chúng tôi có thể có cách tiếp cận sau:

sub hd { 
    return ($_[0]^$_[1]) =~ tr/\001-\255//; 
} 

nhanh hơn nhiều so với lặp lại vị trí.

Tôi tự hỏi điều gì tương đương với nó trong C++?

Answer 1

Fun với STL:

#include <numeric> //inner_product 
#include <functional> //plus, equal_to, not2 
#include <string> 
#include <stdexcept> 

unsigned int 
hd(const std::string& s1, const std::string& s2) 
{ 
    // TODO: What should we do if s1.size() != s2.size()? 
    if (s1.size() != s2.size()){ 
     throw std::invalid_argument(
      "Strings passed to hd() must have the same lenght" 
    ); 
    } 

    return std::inner_product(
     s1.begin(), s1.end(), s2.begin(), 
     0, std::plus<unsigned int>(), 
     std::not2(std::equal_to<std::string::value_type>()) 
    ); 
} 

Answer 2

Một số điểm rõ ràng mà có thể làm cho nó nhanh hơn:

1. Vượt qua chuỗi như tài liệu tham khảo const, không phải bởi giá trị
2. Sử dụng toán tử chỉ mục [] để có được nhân vật, không phải là một phương pháp gọi
3. Compile với tối ưu hóa trên

Answer 3

Cố gắng thay thế cho vòng lặp theo:

for (unsigned i = 0; i < s1.size(); i++) { 
    if (b1[i] != b2[i]) { 
      dif++; 
    } 
} 

Điều này sẽ nhanh hơn rất nhiều vì không có chuỗi mới nào được tạo.

Answer 4

Sử dụng vòng lặp:

int GetHammingDistance(const std::string &a, const std::string &b) 
{ 
    // Hamming distance is not defined for strings of different lengths. 
    ASSERT(a.length() == b.length()); 

    std::string::const_iterator a_it = a.begin(); 
    std::string::const_iterator b_it = b.begin(); 

    std::string::const_iterator a_end = a.end(); 
    std::string::const_iterator b_end = b.end(); 

    int distance = 0; 
    while (a_it != a_end && b_it != b_end) 
    { 
     if (*a_it != *b_it) ++distance; 
     ++a_it; ++b_it; 
    } 

    return distance; 
} 

Answer 5

Choice 1: Sửa đổi mã ban đầu của bạn là như effecient như possable.

int hd(string const& s1, string const& s2) 
{ 
    // hd stands for "Hamming Distance" 
    int dif = 0; 

    for (std::string::size_type i = 0; i < s1.size(); i++) 
    { 
     char b1 = s1[i]; 
     char b2 = s2[i]; 

     dif += (b1 != b2)?1:0; 
    } 

    return dif; 
} 

Tùy chọn thứ hai sử dụng một số thuật toán STL để thực hiện việc nâng hạng nặng.

struct HammingFunc 
{ 
    inline int operator()(char s1,char s2) 
    { 
     return s1 == s2?0:1; 
    } 
}; 

int hd(string const& s1, string const& s2) 
{ 
    int diff = std::inner_product(s1.begin(),s1.end(), 
            s2.begin(), 
            0, 
            std::plus<int>(),HammingFunc() 
           ); 
    return diff; 
} 

Answer 6

Bạn sử dụng chuỗi.

Như đã giải thích ở đây The hunt for the fastest Hamming Distance C implementation nếu bạn có thể sử dụng char * experiements tôi kết luận rằng cho Gcc 4.7.2 trên một Intel Xeon X5650 chức năng mục đích chung Hamming khoảng cách tính toán nhanh nhất cho nhỏ chuỗi (mảng char) là:

// na = length of both strings 
unsigned int HammingDistance(const char* a, unsigned int na, const char* b) { 

    unsigned int num_mismatches = 0; 
    while (na) { 
     if (*a != *b) 
      ++num_mismatches; 

     --na; 
     ++a; 
     ++b; 
    } 

    return num_mismatches; 
} 

Nếu vấn đề của bạn cho phép bạn thiết lập một giới hạn khoảng cách trên, do đó bạn không chăm sóc cho khoảng cách lớn hơn và giới hạn này luôn nhỏ hơn so với chuỗi chiều dài, ví dụ trên có thể furhterly tối ưu hóa để:

// na = length of both strings, dist must always be < na 
unsigned int HammingDistance(const char* const a, const unsigned int na, const char* const b, const unsigned int dist) { 

    unsigned int i = 0, num_mismatches = 0; 

    while(i <= dist) 
    { 
     if (a[i] != b[i]) 
      ++num_mismatches; 

     ++i; 
    } 

    while(num_mismatches <= dist && i < na) 
    { 
     if (a[i] != b[i]) 
      ++num_mismatches; 

     ++i; 
    } 

    return num_mismatches; 
} 

Tôi không chắc chắn nếu const không bất cứ điều gì liên quan đến tốc độ, nhưng tôi sử dụng nó anyways ...