Сжатие и сравнение струн

Question

Недавно я начал писать программу для сравнения последовательности ДНК. Поскольку алфавит состоит только из четырех букв (ATCG), сжатие каждого символа до 2 бит показалось, что оно будет предлагать более быстрое сравнение (два символа одинаковые или разные). Однако, когда я запускал тестовые сравнения, сравнение было намного быстрее, чем сравнение бит (на ~ 30%). Сжатие выполнялось в обеих программах как контроль. Что мне здесь не хватает? Есть ли более эффективный способ сравнения бит? стр. Я также пробовал вектор, но он был немного медленнее, чем битрейт.

// File: bittest.cc 
// Test use of bitset container 

#include <ctime> 
#include <iostream> 
#include <bitset> 
#include <vector> 
#include <string> 
using namespace std; 

void compress(string&, bitset<74>&); 
void compare(bitset<74>&, bitset<74>&); 

int main() 
{ 
    // Start timer 
    std::clock_t start; 
    double difference; 
    start = std::clock(); 

    for(int i=0; i<10000000; ++i){ 
     string frag1="ATCGACTGACTGACTGACTGACTGACTGACTGACTGA"; 
     string frag2="AACGAACGAACGAACGAACGAACGAACGAACGAACGA"; 
     int a=37; 
     bitset<74> bits1; 
     bitset<74> bits2; 
     compress(frag1, bits1); 
     compress(frag2, bits2); 
     compare(bits1, bits2); 
    } 

    difference = (std::clock() - start)/(double)CLOCKS_PER_SEC; 
    int minutes = difference/60; 
    int seconds = difference - minutes * 60; 

    if (seconds < 10){ 
     cout << "\nRunning time: " << minutes << ":0" << seconds << endl << endl; 
    }else{ 
     cout << "\nRunning time: " << minutes << ":" << seconds << endl << endl; 
    } 

    return 0; 
} 

void compress(string& in, bitset<74>& out){ 
    char c; 
    int b=0; 
    for(int i=0; i<in.length(); ++i){ 
     c=in[i]; 
     b=2*i; 
     switch(c){ 
     case 'A': 
      break; 
     case 'C': 
      out.set(b+1); 
      break; 
     case 'G': 
      out.set(b); 
      break; 
     case 'T': 
      out.set(b); 
      out.set(b+1); 
      break; 
     default: 
      cout << "Invalid character in fragment.\n"; 
     } 
    } 
} 

void compare(bitset<74>& a, bitset<74>& b){ 
    for(int i=0; i<74; ++i){ 
     if(a[i] != b[i]){ 
     } 
    } 
} 

И Жгут струна ...

// File: bittest.cc 

#include <ctime> 
#include <iostream> 
#include <bitset> 
#include <vector> 
#include <string> 
using namespace std; 

void compress(string&, bitset<74>&); 
void compare(string&, string&); 

int main() 
{ 
    // Start timer 
    std::clock_t start; 
    double difference; 
    start = std::clock(); 

    for(int i=0; i<10000000; ++i){ 
     string frag1="ATCGACTGACTGACTGACTGACTGACTGACTGACTGA"; 
     string frag2="AACGAACGAACGAACGAACGAACGAACGAACGAACGA"; 
     int a=37; 
     bitset<74> bits1; 
     bitset<74> bits2; 
     compress(frag1, bits1); 
     compress(frag2, bits2); 
     compare(frag1, frag2); 
    } 

    difference = (std::clock() - start)/(double)CLOCKS_PER_SEC; 
    int minutes = difference/60; 
    int seconds = difference - minutes * 60; 

    if (seconds < 10){ 
     cout << "\nRunning time: " << minutes << ":0" << seconds << endl << endl; 
    }else{ 
     cout << "\nRunning time: " << minutes << ":" << seconds << endl << endl; 
    } 

    return 0; 
} 

void compress(string& in, bitset<74>& out){ 
    char c; 
    int b=0; 
    for(int i=0; i<in.length(); ++i){ 
     c=in[i]; 
     b=2*i; 
     switch(c){ 
     case 'A': 
      break; 
     case 'C': 
      out.set(b+1); 
      break; 
     case 'G': 
      out.set(b); 
      break; 
     case 'T': 
      out.set(b); 
      out.set(b+1); 
      break; 
     default: 
      cout << "Invalid character in frag.\n"; 
     } 
    } 
} 

void compare(string& a, string& b){ 
    for(int i=0; i<37; ++i){ 
     if(a[i] != b[i]){ 
     } 
    } 
} 

Answer 1

Рассмотрим два сравнения процедуры:

void compare(bitset<74>& a, bitset<74>& b){ 
    for(int i=0; i<74; ++i){ 
     if(a[i] != b[i]){ 
     } 
    } 
} 

и

void compare(string& a, string& b){ 
    for(int i=0; i<37; ++i){ 
     if(a[i] != b[i]){ 
     } 
    } 
} 

Сразу видно, что один выполняет Петля 74 раз, а другой выполняет Петля 37 раз. Итак, уже начинающийся с точки зрения слабости подход с битрейтом.

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

Если вы замените ваш bitset с char[], что является достаточно большим, чтобы вместить все данные, вручную установить биты себя в подпрограммах сжатия, , а затем сравнить char[] массива байт за один раз или больше, вы можете вероятно, значительно улучшает скорость выполнения процедур сравнения. Будет ли скорость достаточной для преодоления затрат на процедуры сжатия? Это трудно сказать и частично зависит от того, сколько сравнений вы можете сделать с каждой сжатой формой.

Если вы можете выполнить сравнение, используя int или более крупные типы данных, вы, вероятно, можете пойти значительно быстрее, поскольку современные процессоры обычно быстрее получают доступ к 4-байтам или 8-байтам за один раз, чем к 1 байту за раз. Большинство strcmp(3) или memcmp(3) подпрограммы оптимизированы для выполнения огромных, выровненных читает. Если вы используете memcmp(3) для сравнения, у вас будет наилучшая возможность идти на максимальной скорости - и это касается как сжатых, так и несжатых версий.

Answer 2

Процессор ничего не меньше, чем байт, что восемь битов загрузки. Поэтому, когда ваша программа обрабатывает пару бит, CPU фактически загружает восемь бит, а затем маскирует неиспользованные шесть. Операция маскирования занимает процессорное время.

Вы должны обменять эффективность использования памяти на время выполнения. Который вы предпочитаете ваш выбор.