Obsługa bitu dla znalezienia różnicy łańcuchów

Question

Poniższy ciąg próbował znaleźć różnicę między dwoma ciągami. Ale to jest strasznie powolny, gdyż iteracji długość sznurka:

#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; 
} 

istnieje szybka alternatywa to zrobić? W Perlu możemy mieć następujące podejście:

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

który much2 szybciej niż iteracji pozycję.

Zastanawiam się, co jest odpowiednikiem tego w C++?

Answer 1

Zabawa z 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

oczywistych punktów, które mogłyby sprawiają, że szybciej:

1. Przepuścić ciągi jako odniesienia const, a nie według wartości
2. Użyj operatora indeksowania [], aby uzyskać znaki, a nie wywołanie metody
3. kompilacji z optymalizacją na

Answer 3

spróbować zastąpić pętli przez:

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

To powinno być o wiele szybsze, ponieważ nie są tworzone żadne nowe ciągi.

Answer 4

Stosować iteratory:

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: Modyfikacja oryginalnego kodu być tak sprawna jak 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; 
} 

Druga opcja wykorzystuje niektóre algorytmy STL do podnoszenia ciężkiego.

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

Używasz ciągów.

Jak wyjaśniono tutaj The hunt for the fastest Hamming Distance C implementation jeśli można użyć char * moi experiements stwierdzić, że dla GCC 4.7.2 w sprawie Intel Xeon X5650 najszybszym funkcji ogólnego przeznaczenia odległość Hamminga obliczenie dla małych strun (tablice char) wynosi:

// 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; 
} 

Jeśli problem pozwala ustawić górny limit na odległość, tak, że nie dbam o większych odległościach i granica ta jest zawsze mniejsza niż długość struny, powyższy przykład może być furhterly zoptymalizowana do:

// 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; 
} 

Nie jestem pewien, czy const ma nic odnośnie prędkości, ale używam go tak czy inaczej ...