Bonjour à tous,

Voilà je travail actuellement sur un programme qui analyse un graphe de séquences d'ADN en entrée et effectue des calculs dessus.
Comme l'ADN ne comporte que 4 nucléotides ('A', 'C', 'G' et 'T') j'ai développé une suite de méthodes permettant de stocker 3 nucléotides sur un octet (type unsigned char) afin de gagner de la mémoire. Une séquence est donc représenté par un tableau de unsigned char.
Le système marche comme cela : chaque nucléotide utilise 2 bits de l'octet ( A = 00, C = 01, G = 10, T=11). Les 6 bits de poids fort (les plus a gauche) de l'octet codent donc 3 nucléotides. Les 2 bits restants indique le décalage (dans le cas ou un char ne stock pas 3 caractères) : 11 = ce char contient 3 nucléotides, 10 = ce char ne contient que deux nucléotides, 01 = ce char ne contient qu'une nucléotide. Pour des raisons lié aux structures que j'utilise dans mon programme, l'option "ce char contient 3 nucléotides" n'est pas représenté par 0 car la séquence "AAA" sera alors représenté par 00000000, qui est le caractère \0. Enfin, toute séquence se termine par le caractère '\0' comme dans un vrai string.

J'ai écrit deux versions de mon programme, l'une avec ce système et l'autre sans ce système (où donc une nucléotide = un char et une séquence = un tableau de char). Mon problème est le suivant : le programme qui utilise de simples string consomme moins de mémoire que celui qui utilise mon système pour coder 3 nucléotides sur un octet

Je tiens a préciser quelques petites choses :
- Mes deux programmes sont certifiés 0 fuites mémoires par Valgrind
- Pour mesurer la consommation mémoire, j'ai utilisé la commande smem au sein de mon programme et l'outil tstime, en regardant à chaque fois le RSS (Resident Set Size).
- Je ne suis pas un grand spécialiste du C

Voici le code de mon système (system.c) :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sequence.h"
#include <math.h>
 
#define MASK_0 3
#define MASK_1 12
#define MASK_2 48
#define MASK_3 192
#define MASK_1_2_3 252
#define MASK_0_1_2_3 255
 
unsigned char* createSequence(char *str){
    int lg, dec, lg_str, current_dec;
    char* seq;
 
        lg_str = strlen(str);
        dec = lg_str%3;
 
        //Calcul de la longueur du tableau de caractère
        if (dec == 0) lg = lg_str/3;
        else lg = lg_str/3+1;
 
        //Initialisation du tableau de caractère
        seq = calloc(lg+1, sizeof(unsigned char));
 
        if (seq != NULL){
 
            if (dec == 0) dec = 3;
            current_dec = 3;
 
            //On parcours le chaine en entrée et tous les 4 caractères, on insère dans le tableau après tranformation.
            int i, k;
            for (i=0; i<lg; i++){
                if (i==lg-2) current_dec = dec;
 
                for (k=0; k<current_dec; k++){
                    switch(str[i*3+k]){
                        case 'a':
                        case 'A': seq[i] = (seq[i]<<2) | 0;
                                  break;
                        case 'c':
                        case 'C': seq[i] = (seq[i]<<2) | 1;
                                  break;
                        case 'g':
                        case 'G': seq[i] = (seq[i]<<2) | 2;
                                  break;
                        case 't':
                        case 'T': seq[i] = (seq[i]<<2) | 3;
                                  break;
                        case ' ':
                        case '\n':
                        case '\0': break;
                        default : printf("Invalid character encountered : - Operation aborted");
                                  exit(0);
                    }
 
                    if (current_dec != 3) seq[i] = (seq[i]<< (8-dec*2));
                }
 
                seq[i] = (seq[i]<<2) | MASK_0;
            }
            seq[i-1] = ((seq[i-1] & MASK_1_2_3) << (6-dec*2)) | dec;
            seq[lg] = '\0';
 
            return seq;
        }
        else {
            fprintf (stderr, "Memoire insufisante\n");
            exit (EXIT_FAILURE);
        }
}
 
int seqlen(unsigned char* seq){
    int lg = strlen(seq);
    int dec = seq[lg-1] & MASK_0;
 
    if (dec == 3) return lg*3;
    return (lg-1)*3+dec;
}
 
int seqcmp(unsigned char* seq1, int position1, unsigned char* seq2, int position2, int costMismatch){
 
    int offset2=position2%3, offset1 = position1%3;
    int nb1, nb2;
 
 
    switch (offset1){
        case 0: nb1 = seq1[position1/3] & MASK_3;
        case 1: nb1 = seq1[position1/3] & MASK_2;
        case 2: nb1 = seq1[position1/3] & MASK_1;
        default: return -1;
    }
 
    switch (offset2){
        case 0: nb2 = seq2[position2/3] & MASK_3;
        case 1: nb2 = seq2[position2/3] & MASK_2;
        case 2: nb2 = seq2[position2/3] & MASK_1;
        default: return -1;
    }
 
    if (offset2>offset1){
        if (nb2 == pow(3,offset2-offset1)*nb1) return 0;
        return costMismatch;
    }
    if (nb2 == pow(3,offset1-offset2)*nb1) return 0;
    return costMismatch;
}
 
unsigned char* reverseSequence(unsigned char* seq, int complement){
    int i, lg, dec;
    int seq_lg = seqlen(seq);
 
    //Calcul de la longueur du tableau de caractère
    if (seq_lg%3 == 0) lg = (seq_lg/3);
    else lg = (seq_lg/3)+1;
 
    dec = seq_lg%3;
    if (dec == 0) dec = 3;
 
    char *newSeq = calloc(lg+1, sizeof(unsigned char));
 
    if (newSeq != NULL){
        if (complement==0){
            for (i=0; i<lg; i++){
                newSeq[i] = ~(seq[i]) & MASK_1_2_3 | MASK_0;
            }
            newSeq[i-1] = (newSeq[i-1] & (MASK_0_1_2_3 << 8-dec*2)) | dec;
            newSeq[lg] = '\0';
            return newSeq;
        }
 
        for (i=0; i<lg/2; i++){
            newSeq[i] = reverseCompChar(seq[lg-i-1]);
            newSeq[lg-i-1] = reverseCompChar(seq[i]);
        }
 
        if (lg%2 == 1) newSeq[i] = reverseCompChar(seq[i]);
 
        newSeq[lg-1] = newSeq[lg-1] | MASK_0;
        newSeq[lg] = '\0';
 
        if (seq_lg%3 != 0){
            char* res = subSequence(newSeq, 3-(seq_lg%3), lg*3-1);
            free(newSeq);
            return res;
        }
 
        return newSeq;
    }
    else {
        fprintf (stderr, "Insufficient memory\n");
        exit (EXIT_FAILURE);
    }
}
 
unsigned char* subSequence(unsigned char* seq, int posDeb, int posFin){
 
    int i, decTmp = (posDeb%3)*2, k=0, lg, newSeq_lg, seq_lg, dec;
    unsigned char tmp1;
    char* newSeq;
 
    //Calcul de la longueur du tableau de caractère
    newSeq_lg = posFin-posDeb+1;
    seq_lg = seqlen(seq);
    dec = newSeq_lg%3;
 
    if (dec == 0) lg = newSeq_lg/3;
    else lg = newSeq_lg/3+1;
    newSeq = calloc(lg+1,sizeof(unsigned char));
 
    if (newSeq != NULL){
        for (i = posDeb/3; i<posFin/3; i++){
            tmp1 = (seq[i] & MASK_1_2_3) << decTmp;
            if (seq_lg > 3) tmp1 = tmp1 | (seq[i+1] >> (6-decTmp));
            newSeq[k] = tmp1 & MASK_1_2_3 | MASK_0;
            k++;
        }
 
        if (posDeb%3!=0) newSeq[k] = (seq[i] & MASK_1_2_3) << decTmp;
        else{
            if ((lg != 1) || (lg==1 && ((posDeb/3)==(posFin/3)))){
                if (dec == 0) newSeq[k] = (seq[i] & MASK_1_2_3)/* & MASK_0_1_2_3*/;
                else newSeq[k] = (seq[i] & MASK_1_2_3) & (MASK_0_1_2_3 << 8-dec*2);
            }
        }
 
        if (dec == 0) dec = 3;
        if (dec!=0) newSeq[lg-1] = newSeq[lg-1] | dec;
        newSeq[lg] = '\0';
 
        return newSeq;
    }
    else {
        fprintf (stderr, "Insufficient memory\n");
        exit (EXIT_FAILURE);
    }
}
 
unsigned char* concatSequence(unsigned char* seq1, unsigned char* seq2){
    int lgTab1, lgTab2, i, k, decTmp, lgTmp;
    int seq_lg, seq1_lg, seq2_lg;
    char* seq;
 
    // Oninitialise la nouvelle séquence
    seq1_lg = seqlen(seq1);
    seq2_lg = seqlen(seq2);
 
    seq_lg = seq1_lg + seq2_lg;
 
    if (seq_lg%3 == 0) lgTmp = seq_lg/3;
    else lgTmp = (seq_lg/3)+1;
 
    // Calcul de la longueur du tableau de la séquence 1
    if (seq1_lg%3 == 0) lgTab1 = seq1_lg/3;
    else lgTab1 = (seq1_lg/3)+1;
 
    // Calcul de la longueur du tableau de la séquence 2
    if (seq2_lg%3 == 0) lgTab2 = seq2_lg/3;
    else lgTab2 = (seq2_lg/3)+1;
 
    seq = calloc(lgTmp+1, sizeof(unsigned char));
 
    // Recopie du tableau de la séquence 1 dans la nouvelle séquence
    for (i=0; i<lgTab1; i++){
        seq[i] = seq1[i];
    }
 
    decTmp = (seq1[i-1] & MASK_0) * 2;
    seq[i-1] = seq[i-1] & MASK_1_2_3 | MASK_0;
 
    // Si aucun décalage dans la séquence 1, je recopie le tableau de la séquence 2 à la suite du 1 dans la nouvelle séquence
    if (decTmp == 6){
        for (k=0; k<lgTab2; k++){
            seq[i] = seq2[k];
            i++;
        }
    }
    else {
        // Gestion du décalage entre la dernière ligne du premier tableau et la première ligne du dernier tableau
 
        seq[i-1] = seq[i-1] | (seq2[0] >> decTmp) | MASK_0;
        if (i < lgTmp) seq[i] = (seq2[0] & MASK_1_2_3) << (6-decTmp);
 
        // Recopie du deuxième tableau avec gestion du décalage
        for (k=0; k<lgTab2-1; k++){
            seq[i] = seq[i] | (seq2[k+1] >> decTmp) | MASK_0;
            seq[i+1] = (seq2[k+1] & MASK_1_2_3) << (6-decTmp);
            i++;
        }
 
        if (seq_lg%3 == 0) seq[lgTmp-1] = seq[lgTmp-1] | MASK_0;
        else seq[lgTmp-1] = seq[lgTmp-1] | (seq_lg%3);
    }
 
    seq[lgTmp]= '\0';
 
    return seq;
}
 
char *substr(const char *src,int pos,int len) {
  char *dest=NULL;
  if (len>0) {
    dest = calloc(len+1, sizeof(char));
    if(NULL != dest) {
        strncat(dest,src+pos,len);
    }
  }
  return dest;
}
 
unsigned char reverseCompChar(unsigned char c){
    int k;
    unsigned char tmp = 0;
 
    for (k=0; k<3; k++){
        switch(k){
            case 0: tmp = ((~(c >> 2) & 3) | tmp) << 2; break;
            case 1: tmp = ((~(c >> 4) & 3) | tmp) << 2; break;
            case 2: tmp = ((~(c >> 6) & 3) | tmp) << 2; break;
        }
    }
 
    tmp = tmp | MASK_0;
 
    return tmp;
}
Puis le header (sequence.h) :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
#ifndef DEF_SEQUENCE
#define DEF_SEQUENCE
 
unsigned char* createSequence(char *str);
int seqlen(unsigned char* seq);
int seqcmp(unsigned char* seq1, int position1, unsigned char* seq2, int position2, int costMismatch);
unsigned char* reverseSequence(unsigned char* seq, int complement);
unsigned char* subSequence(unsigned char* seq, int posDeb, int posFin);
unsigned char* concatSequence(unsigned char* seq1, unsigned char* seq2);
char *substr(const char *src,int pos,int len);
unsigned char reverseCompChar(unsigned char c);
 
#endif
J'ai mesuré la mémoire à différents points de mon programme et rien que le début, n'utilisant que createSequence() utilise déjà beaucoup trop de mémoire. Voici un exemple d'appel a createSequence():

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
void debut_element(void *user_data, const xmlChar *name, const xmlChar **attrs) {
    DataParser* dp = (DataParser*)user_data;
     if (xmlStrEqual(name, BAD_CAST "node")) {
         Node* n = NULL;
         char* id = NULL;
         char* att = NULL;
         if (NULL != attrs) {
            int i;
            for (i = 0; attrs[i] != NULL; i+=2) {
                if (xmlStrEqual(attrs[i], BAD_CAST dp->nodeAttribute)) {
                    att = calloc(strlen((char *) attrs[i+1]) + 1, sizeof(char));
                    strcpy(att, (char *) attrs[i+1]);
                }
                else if (xmlStrEqual(attrs[i], BAD_CAST "id")) {
                    id = calloc(strlen((char *) attrs[i+1]) + 1, sizeof(char));
                    strcpy(id, (char *) attrs[i+1]);
                }
            }
 
            if (id != NULL){
                if (att != NULL){
                    dp->nb_nucl += (long) strlen((char *) att);
 
                    n = createNode(id, att);
                    int ret;
                    khiter_t k;
 
                    k = kh_put(32, dp->net, id, &ret);
                    kh_value(dp->net, k) = n;
 
                    free(att);
                }
            }
            else {
                fprintf (stderr, "Missing element(s) on one node while parsing graph\n");
                exit (EXIT_FAILURE);
            }
         }
     }
     else if (xmlStrEqual(name, BAD_CAST "edge")) {
        if (NULL != attrs) {
            int i;
            char* reading = NULL;
            khiter_t s, t;
            for (i = 0; attrs[i] != NULL; i+=2) {
                if (xmlStrEqual(attrs[i], BAD_CAST dp->edgeAttribute)) {
                    int l = strlen((char *) attrs[i+1]) + 1;
                    reading = calloc(l, sizeof(char));
                    strcpy(reading, (char *) attrs[i+1]);
                }
                else if (xmlStrEqual(attrs[i], BAD_CAST "source")) {
                   s = kh_get(32, dp->net, attrs[i+1]);
                }
                else if (xmlStrEqual(attrs[i], BAD_CAST "target")) {
                   t = kh_get(32, dp->net, attrs[i+1]);
                }
            }
 
            if (reading != NULL && s && t){
                addNeigh((Node*)kh_value(dp->net,s), (Node*)kh_value(dp->net,t), reading);
            }
            free(reading);
         }
     }
}
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
Node* createNode(char* id, char* attribute){
    Node* n = malloc(sizeof(Node));
    if ( n!= NULL ){
        n->id = id;
        n->attribute = createSequence(attribute);
        n->children = list_create();
        n->relative_position = list_create();
        return n;
    }
    else {
        fprintf (stderr, "insufficient memory to create a node\n");
        exit (EXIT_FAILURE);
    }
}
Voilà si quelqu'un à ne serait-ce qu'une idée, une piste, quelque chose, je lui en serait super reconnaissant ! Merci