String-Komprimierung und Vergleich

Question

Kürzlich begann ich ein Programm zum Vergleich der DNA-Sequenz zu schreiben. Da das Alphabet nur aus vier Buchstaben (ATCG) besteht, schien es bei einem Komprimieren jedes Zeichens auf 2 Bits schneller zu sein (zwei gleiche oder unterschiedliche Zeichen). Wenn ich jedoch einen Test lief, waren Char-Vergleiche viel schneller als Bit-Vergleiche (um ~ 30%). Die Kompression wurde in beiden Programmen als Kontrolle durchgeführt. Was fehlt mir hier? Gibt es eine effizientere Möglichkeit, Bits zu vergleichen? p.s. Ich habe auch versucht Vektor, aber es war ein bisschen langsamer als 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]){ 
     } 
    } 
} 

und die String-Gurtzeug ...

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

Betrachten wir die beiden Vergleichsroutinen:

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

und

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

Rechts von der Fledermaus, dass man 74 wie oft die Schleife ausgeführt wird und der andere ist die Ausführung der Schleife 37 mal sehen können. Der Bitset-Ansatz beginnt also schon bei einer Schwächeposition.

Betrachten Sie nun die Arten von Daten, auf die zugegriffen wird; der Zugriff auf einzelne Bytes ist relativ schnell; Der Zugriff auf einzelne Bits von jeder Datenstruktur kann ein einzelnes Bit in einem ganzen Byte oder vielleicht sogar eine größere Wortgröße speichern. Wenn es Bits in einzelnen Bits speichert, müssen einige Bitmaskierungsoperationen eingeführt werden, und diese alle nehmen ebenfalls Verarbeitungsleistung. Wenn die Bits in Bytes gespeichert sind, vergleichen Sie tatsächlich nur halbe jedes Zeichens auf jedem Bit. Wenn die Bits in Wörtern oder größer gespeichert werden, erhöhen Sie die Größe des Datencaches der CPU - und nehmen möglicherweise etwas, das vollständig in eine Cachezeile passt, zu mehreren Cachezeilen. Das ist ein Potenzial für gigantische Geschwindigkeitsstrafen, obwohl auf Eingaben dieser kleine, es ist wahrscheinlich nicht allzu schrecklich noch.

Wenn Sie Ihren bitset mit einem char[] ersetzen, die groß genug ist, alle Ihre Daten zu halten, manuell die Bits selbst in den Kompressionsroutinen gesetzt, und dann ein Byte zu einem Zeitpunkt die char[] Array vergleichen oder größer, können Sie wahrscheinlich die Geschwindigkeit der Vergleichsroutinen drastisch zu verbessern. Wird die Beschleunigung ausreichen, um die Kosten der Komprimierungsroutinen zu überwinden? Das ist schwer zu sagen und hängt zum Teil davon ab, wie viele Vergleiche man mit jeder komprimierten Form machen kann.

Wenn Sie Ihren Vergleich mit int oder größeren Datentypen durchführen können, können Sie wahrscheinlich sogar wesentlich schneller gehen, da moderne CPUs in der Regel schneller auf 4 Byte oder 8 Byte gleichzeitig als 1 Byte gleichzeitig zugreifen können. Die meisten strcmp(3) oder memcmp(3) Routinen sind optimiert, um große, ausgerichtete liest. Wenn Sie memcmp(3) verwenden, um Ihren Vergleich zu machen, haben Sie die beste Chance auf Höchstgeschwindigkeit zu gehen - und das gilt sowohl für die komprimierte als auch die unkomprimierte Version.

Answer 2

Die CPU wird nicht alles, was kleiner ist als ein Byte laden, die acht Bits. Wenn Ihr Programm also ein Bitpaar behandelt, lädt die CPU tatsächlich acht Bits und maskiert dann die unbenutzten sechs Bits. Die Maskierungsoperation benötigt Prozessorzeit.

Sie müssen die Speichereffizienz gegen die Ausführungszeit tauschen. Was Sie bevorzugen, ist Ihre Wahl.