Самый быстрый способ определить, отличаются ли две строки одним символом

Question

Я пишу алгоритм C++, который берет две строки и возвращает true, если вы можете мутировать из строки a в строку b, меняя один символ на другой. Две строки должны быть одинаковыми по размеру и могут иметь только одну разницу. Мне также нужен доступ к индексу, который изменился, и характер strA, который был изменен. Я нашел рабочий алгоритм, но он выполняет итерацию через каждую пару слов и работает слишком медленно на любом большом количестве входных данных.

bool canChange(std::string const& strA, std::string const& strB, char& letter) 
{ 
    int dif = 0; 
    int position = 0; 
    int currentSize = (int)strA.size(); 
    if(currentSize != (int)strB.size()) 
    { 
     return false; 
    } 
    for(int i = 0; i < currentSize; ++i) 
    { 
     if(strA[i] != strB[i]) 
     { 
      dif++; 
      position = i; 
      if(dif > 1) 
      { 
       return false; 
      } 
     } 
    } 
    if(dif == 1) 
    { 
     letter = strA[position]; 
     return true; 
    } 
    else return false; 
} 

Любые советы по оптимизации?

Answer 1

Насколько велик ваш вклад?

Я думаю, что strA [i], strB [i] имеет служебный вызов функции, если он не встроен. Поэтому убедитесь, что вы выполнили свой тест производительности с включенной вставкой и скомпилированы с выпуском. В противном случае попробуйте получить байты как char * с помощью strA.c_str().

Если все это не удается, и оно все еще недостаточно быстро, попробуйте сломать строку в куски и использовать memcmp или strncmp на кусках. Если нет разницы, переходите к следующему фрагменту, пока не дойдете до конца или не найдете разницу. Если разница найдена, сравните свой байт по байту, пока не найдете разницу. Я предлагаю этот маршрут, потому что memcmp часто быстрее, чем ваши тривиальные реализации, поскольку они могут использовать расширения SSE процессора и т. Д., Чтобы делать очень быстрые сравнения.

Кроме того, существует проблема с вашим кодом. Вы предполагаете, что strA длиннее strB и проверяет длину A для аксессуаров массива.

Answer 2

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

Предлагаю использовать функции стандартной библиотеки и не пытаться подсчитать количество несоответствий. Например;

#include <string> 
#include <algorithm> 

bool canChange(std::string const& strA, std::string const& strB, char& letter, std::size_t &index) 
{ 
    bool single_mismatch = false; 
    if (strA.size() == strB.size()) 
    { 
     typedef std::string::const_iterator ci; 
     typedef std::pair<ci, ci> mismatch_result; 

     ci begA(strA.begin()), endA(strA.end()); 

     mismatch_result result = std::mismatch(begA, endA, strB.begin()); 

     if (result.first != endA) // found a mismatch 
     { 
      letter = *(result.first); 
      index = std::distance(begA, result.first); 

      // now look for a second mismatch 

      std::advance(result.first, 1); 
      std::advance(result.second, 1); 

      single_mismatch = (std::mismatch(result.first, endA, result.second).first == endA); 
     } 
    } 
    return single_mismatch; 
} 

Это работает для всех версий. Его можно немного упростить в C++ 11.

Если приведенное выше значение возвращает true, то одно несоответствие было найдено.

Если возвращаемое значение равно false, то либо строки имеют разные размеры, либо количество несоответствий не равно 1 (либо строки равны, либо имеют более одного несоответствия).

letter и index остается неизменными, если строки имеют разную длину, или точно равны, но в остальном идентифицировать первое несоответствие (значение символа в strA и index).

Answer 3

Если вы хотите оптимизировать для практически идентичных строк, вы можете использовать векторные инструкции x86 SSE/AVX. Ваша основная идея выглядит отлично: перерыв, как только вы обнаружите второе различие.

Чтобы найти и сравнить отличия символов, такая последовательность, как PCMPEQB/PMOVMSKB/test-and-branch, вероятно, хороша. (Используйте встроенные функции C/C++ для получения этих векторных инструкций). Когда ваш векторный цикл обнаруживает ненулевые различия в текущем блоке, POPCNT битмаски, чтобы увидеть, только что вы обнаружили первое различие или обнаружили две отличия в одном блоке.

Я объединил непроверенную и не совсем полную версию AVX2 того, что я описываю. Этот код предполагает, что длина строк кратно 32. Остановка на ранней стадии и обработка последнего фрагмента с эпилогом очистки - это упражнение для читателя.

#include <immintrin.h> 
#include <string> 

// not tested, and doesn't avoid reading past the end of the string. 
// TODO: epilogue to handle the last up-to-31 left-over bytes separately. 
bool canChange_avx2_bmi(std::string const& strA, std::string const& strB, char& letter) { 
    size_t size = strA.size(); 
    if (size != strB.size()) 
     return false; 

    int diffs = 0; 
    size_t diffpos = 0; 
    size_t pos = 0; 
    do { 
     uint32_t diffmask = 0; 
     while(pos < size) { 
      __m256i vecA = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(& strA[pos])); 
      __m256i vecB = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(& strB[pos])); 
      __m256i vdiff = _mm256_cmpeq_epi8(vecA, vecB); 
      diffmask = _mm256_movemask_epi8(vdiff); 
      pos += 32; 
      if (diffmask) break; // gcc makes worse code if you include && !diffmask in the while condition, instead of this break 
     } 
     if (diffmask) { 
      diffpos = pos + _tzcnt_u32(diffmask); // position of the lowest set bit. Could safely use BSF rather than TZCNT here, since we only run when diffmask is non-zero. 
      diffs += _mm_popcnt_u32(diffmask); 
     } 
    } while(pos < size && diffs <= 1); 

    if (diffs == 1) { 
     letter = strA[diffpos]; 
     return true; 
    } 
    return false; 
} 

Уродливый break вместо включения, что в состоянии while по-видимому, помогает gcc generate better code. do{}while() также соответствует тому, как я хочу, чтобы asm вышел. Я не пробовал использовать цикл for или while, чтобы узнать, что сделает gcc.

Внутренний цикл действительно туго так:

.L14: 
     cmp  rcx, r8 
     jnb  .L10  # the while(pos<size) condition 
.L6: # entry point for first iteration, because gcc duplicates the pos<size test ahead of the loop 

     vmovdqu ymm0, YMMWORD PTR [r9+rcx]  # tmp118,* pos 
     vpcmpeqb  ymm0, ymm0, YMMWORD PTR [r10+rcx]  # tmp123, tmp118,* pos 
     add  rcx, 32 # pos, 
     vpmovmskb  eax, ymm0  # tmp121, tmp123 
     test eax, eax  # tmp121 
     je  .L14  #, 

В теории, это должно работать на одной итерации в 2 часах (Intel Haswell). В цикле есть 7 совпадающих доменов. (Будет 6, но 2-reg addressing modes apparently can't micro-fuse on SnB-family CPUs.) Поскольку два из uops - это нагрузки, а не ALU, эта пропускная способность может быть достижима на SnB/IvB.

Это должно быть исключительно хорошо для полета над областями, где две строки идентичны. Накладные расходы на правильную обработку произвольной длины строки сделают это потенциально медленнее, чем простая скалярная функция, если строки коротки и/или имеют несколько различий на ранней стадии.