Битовая операция для нахождения строковой разницы

Question

Следующая моя строка пыталась найти разницу между двумя строками. Но это ужасно медленно, так как итерирует длину строки:

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

Есть ли быстрая альтернатива для этого? В Perl у нас может быть следующий подход:

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

, что намного на 2 быстрее, чем итерация позиции.

Интересно, что это эквивалентно в C ++?

Answer 1

Попробуйте заменить цикл for на:

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

Это должно быть намного быстрее, потому что новые строки не создаются.

Answer 2

Веселье с 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 3

Использовать итераторы:

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 4

Вариант 1. Измените исходный код, чтобы он был максимально эффективным.

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

Второй вариант использования некоторых алгоритмов STL для выполнения тяжелой работы.

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 5

Вы используете строки.

Как объяснено здесь Охота за самой быстрой реализацией Hamming Distance C если вы можете использовать char *, то мои эксперименты заключают, что для Gcc 4.7.2 на Intel Xeon X5650 самая быстрая функция вычисления расстояния Хэмминга общего назначения для маленьких строк ( массив символов):

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

Если ваша проблема позволяет вам установить верхний предел расстояния, так что вам не нужны большие расстояния, и этот предел всегда меньше, чем длина строк, приведенный выше пример может быть дополнительно оптимизирован для:

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

Я не уверен, что const что-то делает со скоростью, но я все равно использую это ...

Answer 6

Некоторые очевидные моменты, которые могут сделать это быстрее:

1. Передавать строки как константные ссылки, а не по значению
2. Используйте оператор индексации [] для получения символов, а не вызов метода
3. Компиляция с оптимизацией на