рассчитать, насколько две строки похожи?

Question

рассчитать, насколько две строки похожи?

У меня есть функция, которая вычисляет дисперсию двух данных строк. Есть ли более быстрый метод (или алгоритм), чтобы сделать такую вещь?

Пожалуйста, имейте в виду, что каждая буква моих строк загружена ДНК, что означает, что это одна из букв A, T, C или G:

unsigned __int8 dis(char* FirstString, char* SecondString)
{
unsigned __int8 distanceIndex = 0;
for (unsigned __int8 i = 0; i < l; i++)
{
if (FirstString[i] != SecondString[i])
distanceIndex++;
}
return distanceIndex;
}

1

algorithm c++cpu-speed processing-efficiency

Решение

Другие решения

Это алгоритм O (n).

Наиболее эффективным алгоритмом для сравнения равенства (или расстояния в этом случае) между двумя строками является O (n).

1

Вы можете сэкономить if:

unsigned __int8 dis(char* FirstString, char* SecondString)
{
unsigned __int8 distanceIndex = 0;
for (unsigned __int8 i = 0; i < l; i++)
{
distanceIndex += FirstString[i] != SecondString[i];
}
return distanceIndex;
}

но я сомневаюсь, что это существенно

0

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

Я не уверен, может ли компилятор оптимизировать это для вас.

0

Источник

Accepted Answer

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

Все ваши последовательности 13
символ долго. Последовательности ДНК содержат только буквы ATCG, который может быть закодирован в пределах 2 бит. Вы можете хранить каждую последовательность ДНК в пределах 32-битного значения, позволяя компьютеру выполнять сравнение параллельно:

XOR-объединить значения, чтобы получить битовые различия
сдвиг и ИЛИ объединяют нормализованные поднаборы И (нечетные биты, четные биты) в
преобразовать битовые различия в нуклеобазные различия
подсчитать установленные биты, чтобы получить расстояние последовательности ДНК

В зависимости от архитектуры компьютера может быть функция подсчета битов
реализовано в процессоре. Более подробно есть ответы на вопрос: Как
подсчитать количество установленных бит в 32-битном
целое число?

Вот основная функция:

int distV(const unsigned va, const unsigned vb)
{
const unsigned x = va ^ vb;
const unsigned bn = ((x & 0xaaaaaaaa) >> 1 ) | (x & 0x55555555);
return __builtin_popcount(bn);
}

Увидеть полная демонстрация GCC-4.3.2 который использует последовательности длины 16. Я измерил прирост производительности в 4 раза для самого сравнения (исключая кодировку).

3