Сжатие и сравнение строк

Question

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

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

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

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