Operación de bit para encontrar la diferencia de cadena

Question

La siguiente cadena de la mía intentó encontrar la diferencia entre dos cadenas. Pero es terriblemente lento, ya que iterar la longitud de la cadena:

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

¿Hay una alternativa rápida para hacer eso? En Perl que puede tener el siguiente enfoque:

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

que es muCH2 más rápido que la iteración de la posición.

Me pregunto cuál es su equivalente en C++?

Answer 1

la diversión con el TEL:

#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

Algunos puntos obvios que podrían hacer que sea más rápido:

1. Pase las cadenas como referencias const, no por el valor
2. Utilice el operador de indexación [] para obtener caracteres, no es una llamada a un método
3. Compilar con la optimización de

Answer 3

tratar de sustituir el bucle por:

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

Esto debería ser mucho más rápido porque no se crean nuevas cadenas.

Answer 4

Use iteradores:

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: Modificar el código original para ser tan eficiente como 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; 
} 

Segunda opción: utilice algunos de los algoritmos de STL para realizar el trabajo pesado.

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

Utiliza cadenas.

como se explica aquí The hunt for the fastest Hamming Distance C implementation si se puede usar char * mis experiements concluyen que para gcc 4.7.2 en una Intel Xeon X5650 la función más rápida de uso general para el cálculo de la distancia de Hamming pequeñas cadenas (arrays de char) es:

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

Si su problema le permite establecer un límite superior a distancia, de modo que no se preocupan de mayores distancias y este límite es siempre menor que la longitud de las cuerdas, el ejemplo anterior puede ser furhterly optimizado para:

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

No estoy seguro de si const hace nada con respecto a la velocidad, pero lo uso todos modos ...