Выявление участков кода, требующих оптимизации

 

Запуск программы по моделированию ПЦР показал, что для большого массива праймеров (массив из более 100000 строк) требуется значительное время на ее выполнение. Поэтому было решено провести профилирование данной программы, путем измерения времени выполнения отдельных подпрограмм и функций, с целью выявления наиболее затратных по времени выполнения участков кода. Для этого была использована функция prof, имеющая следующую структуру:

 

void prof(char * str, int i, struct timeval * B){

struct itimerval A;

struct timeval tmp;

if (getitimer(ITIMER_PROF, &A)){

perror("getitimer");

exit(1);

}

tmp.tv_usec=B->tv_usec-A.it_value.tv_usec;

tmp.tv_sec=B->tv_sec-A.it_value.tv_sec;

if (tmp.tv_usec<0){

tmp.tv_usec+=1000000;

tmp.tv_sec--;

}

fprintf(stderr, "%d %s: %d.%d - %d.%d\n", i, str, A.it_value.tv_sec,

A.it_value.tv_usec,

tmp.tv_sec, tmp.tv_usec);

*B=A.it_value;

}

…

struct stat st;

struct itimerval A;

struct timeval B;

struct write_rec W;

A.it_interval.tv_sec=0x7fffffff;

A.it_interval.tv_usec=0;

A.it_value=A.it_interval;

B=A.it_value;

signal(SIGPROF, SIG_IGN);

…

prof("Before strstr", i, &B);

pend=search(penter+l, inv, l);

prof("After strstr", i, &B);

 

Для профилирования программа запускалась в тестовом режиме, когда анализировался не весь массив праймеров, а только первые 100 строк. В результате было выявлено, что наибольшее время при работе программы затрачивается на выполнение библиотечной функции strstr для точного поиска подстроки в строке. Время, затрачиваемое на выполнение всех функций strstr в программе, составило более 99% от общего времени выполнения программы.

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

 

Обзор алгоритмов точного поиска подстроки в строке

 

Как было показано ранее, скорость алгоритма поиска теоретических ПЦР-фрагментов лимитируется временем выполнения библиотечной функции strstr, которая осуществляет поиск подстроки (последовательности праймера) в строке (последовательность геномной ДНК). Поэтому было решено провести оптимизацию этого участка кода, путем замены библиотечной функции на более производительную.

Были выбраны два основных направления, по ускорению функции поиска подстроки в строке:

· поиск наиболее быстрых алгоритмов;

· реализация алгоритма поиска подстроки на ассемблере.

На данный момент существует множество алгоритмов точного поиска подстроки в строке. Известны теоретические оценки производительности этих алгоритмов (асимптотическая временная вычислительная сложность), такие как среднее теоретическое время поиска и теоретическое время поиска в худшем случае. Тем не менее, реальная производительность конкретного алгоритма может сильно различаться, в зависимости от условий поиска.

Нуклеотидные последовательности традиционно принято относить к «плохим» данным для поиска, так как они имеют очень маленький размер алфавита – 4 основных символа, и очень большую длину. И хотя форматы хранения последовательностей нуклеиновых кислот допускают наличие и других символов, обычно их содержание не превышает 0,001% и они не оказывают влияния на скорость алгоритмов поиска.

В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ. «иголка»), а строку, в которой ведётся поиск – как haystack (англ. «стог сена»).

В последующих алгоритмах будут встречаться следующие основные обозначения:

· Искомый образец (needle) - строка x = x [ 0... m - 1 ],ее длина m;

· Текст (haystack)- строка y = y [ 0... n - 1 ], ее длина n;

· Алфавит (множество символов, из которых составлены текст и образец) - S, в нем s различных символов;

· Слово u - префикс слова w, если существует слово v: w = uv;

· Слово v - суффикс слова w, если существует слово u: w = uv;

· Слово z - подстрока слова w, если существуют u и v: w = uzv;

· Символ O – верхнее ограничение сложности алгоритма.

В программах также будут использованы следующие функции и константы:

· константа SIGMA - размер алфавита;

· константа WORD - размер компьютерного слова в битах, обычно 32;

· константа XSIZE - размер образца;

· функции MIN / MAX - минимум / максимум.

Пример задания соответствующих функций и констант:

#define MIN(a,b) ((a) < (b)? (a): (b))

#define MAX(a,b) ((a) > (b)? (a): (b))

#define XSIZE 4200

#define SIGMA 256

#define WORD 32

 

Примитивный алгоритм

 

Примитивный алгоритм или алгоритм грубой силы, заключается в проверке всех позиций текста с 0 по n - m на предмет совпадения с началом образца. Если совпадает - смотрим следующую букву и т.д., если же не совпадает, то смещаемся на один символ в строке y и начинаем сравнение заново. Этот алгоритм не нуждается в предварительной обработке и дополнительных затратах памяти:

 

char* hospool(char *y, char *x, int m){

char* yy;

int i, j;

yy=y;

i=0;

while (y[i]!= '\0'){

for (j=0; j < m; ++j){

if (y[i+j]!= x[j])

break;

}

if (j==m){

yy=y+i;

return (yy);

}

i++;

}

return NULL;

}

 

Данный алгоритм имеет среднее время поиска равное 2*n, и худшее время поиска - O(n * m)