C++ Accélération des appels multiples de substr() ou de fonctions équivalentes pour l'analyse d'une grande chaîne de caractères

Question

J'essaie d'analyser de grandes chaînes de caractères que j'ai chargées en mémoire depuis un fichier. J'analyse des séquences d'ADN (stockées sous forme de chaîne) avec une fenêtre glissante de longueur variable. Le problème est que les chaînes sont si grandes qu'il faut un temps très long pour les parcourir. Je ne sais pas si c'est possible, mais est-il possible d'accélérer le processus d'une manière ou d'une autre ?

Je veux dire que je m'attendais à ce que les entrées/sorties dominent mon application et j'ai donc changé ma lecture ligne par ligne pour lire tout le fichier en mémoire en une seule fois, mais après avoir testé mon code, j'ai découvert qu'il passait la plupart du temps dans une boucle comme celle-ci :

size_t currentCharNumber = 0;
int16_t windowSize = 50;
//seq is a string of length 249250621
while(seq.length() - currentLinePos < windowSize)
{
   string temp = seq.substr(currentLinePos, windowSize);
   //do stuff to temp
   ++currentLinePos;
}

Il ne faut que quelques secondes pour charger la séquence en mémoire à partir d'un fichier, mais il faut ~30 minutes pour analyser la séquence (même après avoir commenté le traitement sous l'appel substr()). Est-ce qu'il y a quelque chose qui m'échappe et qui ajoute beaucoup de surcharge ou est-ce que c'est probablement dû à la taille de mes données ?

Serait-il utile de mentionner que je peux ignorer les sous-chaînes comportant des caractères autres que ATCG ? Je veux dire que je fais ce filtrage dans mon code mais seulement après avoir obtenu les chaînes de substr.

C'est la première fois que je poste, et mon C++ est un peu rouillé. Tout commentaire serait grandement apprécié.

Answer 1

Vous pourriez envisager de passer de l'utilisation d'un string pour maintenir votre fenêtre coulissante à l'aide d'un std::deque<char> . Le site deque est optimisé pour l'insertion et la suppression de valeurs à chaque extrémité, et est donc un bon candidat ici. Vous pouvez commencer par charger les 50 premiers caractères dans le fichier deque et vous pourrez alors ajuster votre boucle comme ceci :

/* Initialize the window to the first windowSize characters. */
std::deque<char> window(seq.begin(), seq.begin() + windowSize);

/* Repeatedly process each window. */
for (size_t i = windowSize; i < seq.length(); ++i) {
    /* Do something to window */

    /* Drop the first character from the window, then add the next character
     * of the sequence.
     */
    window.pop_front();
    window.push_back(seq[i]);     
}

Le temps de construction de chaque fenêtre est donc de O(1) au lieu de O(k), où k est le nombre de caractères de la fenêtre. Cela pourrait réduire considérablement le temps d'exécution, puisque le nombre de caractères dans votre fenêtre est assez important.

J'espère que cela vous aidera !

Answer 2

Vous pouvez délimiter votre fenêtre de glissement par deux pointeurs dans la chaîne originale et travailler avec cela au lieu de copier toute la plage dans une chaîne séparée. Si std::string La construction est une charge supplémentaire, évitez-la.

Vous pouvez également réutiliser le même std::string à chaque fois (en supposant que la taille de la fenêtre soit constante), mais cela vous coûterait quand même une opération de copie (qui peut être négligeable pour les petits rapports fenêtre/longueur, cependant).

Answer 3

Appels à std::string::substr peut entraîner des allocations excessives de mémoire dynamique et, à tout le moins, la copie de tampons. Souvent, vous pouvez réduire la nécessité de substr en modifiant votre algorithme pour utiliser des itérateurs de suppression de chaîne à la place.