C++

De la lenteur de string avec BC++ 5 et d'un algo de m*** en general ..

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : De la lenteur de string avec BC++ 5 et d'un algo de m*** en general ..

Joel F

Real men use unique_ptr

Des remarques ???

je traitent des fichiers de 400Ko contenant 5000 entrées de types chaines de caractéres que je stocke dans des string ...

puis je fait un truc du style :

Code :

for( int i = 0; i < nbChaine; i++ )
{
allstring += chaine_cle[i] + "\0" + chaine_valeur[i] + "\0";
...
// autres trucs pas lents du tout.
}

et je sauve allstring sur disque.

Moralité : 1mn 35s pour sauver 5000 chaines de moins de 128 octets chacunes ... sur un AMD 800 ... ou est al blague ???
je suis plus en mode debug, j'optimise tout pour la vitesse et j'inline a mort mes traitements annexes.

Ouin :cry: :cry:

Message édité par Joel F le 12-09-2002 à 09:47:55

Publicité

farib

Ansistring borland ou string de la stl a la sauce borland ?

Joel F

Real men use unique_ptr

STL std::string de borland.
AnsiString c encore pire :pt1cable:

LetoII

Le dormeur doit se réveiller

La question étant que fait le += des string, est ce qu'il réalloue de la mémoir tout le temps ou bien est ce optimisé?

---------------
Le Tyran

Joel F

Real men use unique_ptr

grave question en effet ....
j'ai beau regarder ca avec la fenetre CPU, si pipe kedal

LeGreg

le probleme que tu rencontres c'est sur l'operateur +
il cree un objet temporaire qu'il te renvoie.

si tu veux les performances utilise plutot +=
qui travaille sur ta chaine courante
et remplace tes "\0" par des '\0'.

A+
LeGreg

Joel F

Real men use unique_ptr

eh eh déjà fait

Code :

allstring += chaine_cle[i];
allstring += '\0';
allstring += chaine_valeur[i];
allstring += '\0';

c pas mieux ...

LeGreg

autre truc,
si tu connais la taille globale
tu fais un reserve sur ta chaine principale
comme ca pas besoin de redimensionner en route.

LeGreg

Joel F

Real men use unique_ptr

ben cruel dilemne.
Je pourrais effectivement faire ca

Code :

taille = 0;
for( int j = 0; j < nbChaine; j++ )
{
taille += 2 + chaine_cle[i].length() + chaine_valeur[i].length();
}
string allstring(taille);

avant la boucle principale mais ca m'oblige a parcourir 2x les 2 tableaux

LetoII

Le dormeur doit se réveiller

J'ai vérifié, sur l'implémentation que j'ai voilà le code du += :

Code :

_Self& operator+=(const _Self& __s) { return append(__s); }

Donc à priori c bon, par contre effectivement si tu dépasse la taille du buffer va y avoir allocation de mémoir, donc perte de temps. Tente un reserve comme ça t'as été sugéré.

---------------
Le Tyran

Publicité

LeGreg

Joel F a écrit a écrit :

ben cruel dilemne.
Je pourrais effectivement faire ca

Code :

taille = 0;
for( int j = 0; j < nbChaine; j++ )
{
taille += 2 + chaine_cle[i].length() + chaine_valeur[i].length();
}
string allstring(taille);

avant la boucle principale mais ca m'oblige a parcourir 2x les 2 tableaux

Tu n'as pas une valeur max de tes chaines?
Dans ce cas basta taille = nbChaine * valeur max

LeGreg

LeGreg

de toute facon parcourir ton tableau
pour faire la somme des longueurs
c'est beaucoup moins couteux que de faire une seule reallocation
au milieu de traitement. (il est obligé d'allouer puis de recopier intégralement ce qui a déjà été écrit..)

LeGreg

Joel F

Real men use unique_ptr

non g pas de taille max malheureseument.

Je v tenter le calcul pre-operatoire (aouch gaffe a l'ansthesie )
on verra bien.

En tout cas je suis sure que ca vient de la car si je commente ces 4 operations et que je laisse tout le reste, ca speede a fond.

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

non g pas de taille max malheureseument.

Je v tenter le calcul pre-operatoire (aouch gaffe a l'ansthesie )
on verra bien.

[:grinking]

Joel F a écrit a écrit :

En tout cas je suis sure que ca vient de la car si je commente ces 4 operations et que je laisse tout le reste, ca speede a fond.

Je t'ai déjà dit que ct normal que le programme aille vachement plus vite quand tu enlève tous les traitements :pt1cable:

Message édité par LetoII le 11-09-2002 à 15:47:38

---------------
Le Tyran

verdoux

And I'm still waiting

Faudrait essayer avec allstring en ostringstream

Joel F

Real men use unique_ptr

Resumé de l'épisode précédent :

Citation :

aprés avoir baiser la geule au espion russo-chinois ..

oups désolé , non bon, c bien les chaines ki font ramer j'en ai la certitude.

std::string avec allocation a taille max : gain de 20% (40s au lieu de 1mn et qqs)
AnsiString simple : nada
AnsiString + pre-alloc : gain de 15 % ...
char* + memcpy : gain de 20 % itou ...

j'commence a me posser des questions ...
Le + starnge c que ce que je fais, y a deja un truc qui le fait et ce prog sauve le tout en 5s ...

:cry: :cry:

Message édité par Joel F le 12-09-2002 à 09:48:40

LetoII

Le dormeur doit se réveiller

Ensuite tu peux essayer de mapper le fichier en mémoir pour aller écrire directement dedans mais bon je sais pas si ça peux te faire gagner du temps.

---------------
Le Tyran

Joel F

Real men use unique_ptr

ben de tte maniere je peux pas...
Je charge l'originale, je rajoute/enleve des entrees puis je el sauve. Sacahnt que je ne peux pas conserver les donnes de l'original car chaque +/- de chaines modifie une grosse partie du fichier (bicose sauvegarde d'une table de hachage )

Je tiens aussi a preciser que le format c pas moi ki l'est inventé donc tte remark sur "Mais il put ton format" seront redirigé ici

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

ben de tte maniere je peux pas...
Je charge l'originale, je rajoute/enleve des entrees puis je el sauve. Sacahnt que je ne peux pas conserver les donnes de l'original car chaque +/- de chaines modifie une grosse partie du fichier (bicose sauvegarde d'une table de hachage )

Je tiens aussi a preciser que le format c pas moi ki l'est inventé donc tte remark sur "Mais il put ton format" seront redirigé ici

C pas un pb ça

---------------
Le Tyran

Joel F

Real men use unique_ptr

alors on va expliker l'algo.

Code :

Soit CK, le tableau des chaines clés, CV le tab des chaines de valeurs.
La sauvegarde se passe ainsi.
Soit T le tableau de stockage d'une structure indicant en outre les tailles des chaines te leurs offsets dans le fichier.
Pour toutes les entrées de CK faire :
{
hashvalue = Hachage( Ck[i], taille );
hoffset = hashvalue;
erreur = 0;
Tant que T[hoffset] n'est pas libre
{
hoffset++;
hoffset %= taille;
erreur++;
}
remplir la structure de T[hoffset].
allstring += CK[i];
allstring += '\0';
allstring += CV[i];
allstring += '\0';
}
Header.CRC = CalculCheckSum(allstring);
ecrire Header sur file
ecrire T sur file
ecrire allstring sur file

Toute bonne ame optimisatrice ets la bien venue.

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

alors on va expliker l'algo.

Code :

Soit CK, le tableau des chaines clés, CV le tab des chaines de valeurs.
La sauvegarde se passe ainsi.
Soit T le tableau de stockage d'une structure indicant en outre les tailles des chaines te leurs offsets dans le fichier.
Pour toutes les entrées de CK faire :
{
hashvalue = Hachage( Ck[i], taille );
hoffset = hashvalue;
erreur = 0;
Tant que T[hoffset] n'est pas libre
{
hoffset++;
hoffset %= taille;
erreur++;
}
remplir la structure de T[hoffset].
allstring += CK[i];
allstring += '\0';
allstring += CV[i];
allstring += '\0';
}
Header.CRC = CalculCheckSum(allstring);
ecrire Header sur file
ecrire T sur file
ecrire allstring sur file

Toute bonne ame optimisatrice ets la bien venue.

T'as le code tel qu'il est à l'heure actuelle?

---------------
Le Tyran

Joel F

Real men use unique_ptr

ouais a la maison )

si je vois j'irais le chercher a 12h

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

ouais a la maison

)

si je vois j'irais le chercher a 12h

Laisse faire, je passerai demain, ou on jettra un coup d'oeuil samedi

Message édité par LetoII le 12-09-2002 à 09:59:29

---------------
Le Tyran

Joel F

Real men use unique_ptr

LetoII a écrit a écrit :

Laisse faire, je passerai de main, ou on jettra un coup d'oeuil samedi

Eh moi 2 pieds merci

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

Eh moi 2 pieds merci

Spas bien de rajouter des fautes dans une citation pour faire une blague pourie :ange:

---------------
Le Tyran

Joel F

Real men use unique_ptr

oh le menteur-editeur-de par derriere
bou !!

vilain !!

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

oh le menteur-editeur-de par derriere
bou !!

vilain !!

:lol:

---------------
Le Tyran

Joel F

Real men use unique_ptr

paske sinon tout le reste du prog marche, sniff y en a marre !!

BENB

100% Lux.

A quoi te sert allstring ?

c'est juste une concatenation avant ecriture ?

pourquoi ne pas ecrire directement dans le fichier ?

La concatenation viendra naturellement, et tu n'aurra plus d'allocation mémoire parasite...

verdoux

And I'm still waiting

BENB a écrit a écrit :

A quoi te sert allstring ?

c'est juste une concatenation avant ecriture ?

pourquoi ne pas ecrire directement dans le fichier ?

La concatenation viendra naturellement, et tu n'aurra plus d'allocation mémoire parasite...

Ou bien les strstream ou stringstream comme dit plus haut.

Joel F

Real men use unique_ptr

allstring sert a calculer la valeur de checksum (CRC) placé en tête du fichier ...

Je v voir si je peux pas transformer ce calcul en truc itératif

CRC(i) =f( CRC(i-1))

BENB

100% Lux.

Joel F a écrit a écrit :

allstring sert a calculer la valeur de checksum (CRC) placé en tête du fichier ...

Je v voir si je peux pas transformer ce calcul en truc itératif

CRC(i) =f( CRC(i-1))

un CRC donc une taille constante, tu laisse la place au debut du fichier et tu reviens l'ecrire à la fin...
De toute maniere tu le calcule bien de maniere iterative, ca ca ne changes pas...

Joel F

Real men use unique_ptr

hmm la formule du crc tiens compte des caractéres de toute sles chaine du style

pour i de 0 à taille-2 :

CRC += (char[i]+char[i+1]+char[i+3]) ^??? etc ...

je dois avoir toutes les chaines concaténées d'abord.

En outre le crc fait partie d'un structure que je prépare à l'avance.

Je l'ai peut etre mal dit mais je sauve riend ans la boucle (pas fou) mais bien un gros dump sur disk apres la boucle qui m'embetent

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

hmm la formule du crc tiens compte des caractéres de toute sles chaine du style

pour i de 0 à taille-2 :

CRC += (char[i]+char[i+1]+char[i+3]) ^??? etc ...

je dois avoir toutes les chaines concaténées d'abord.

En outre le crc fait partie d'un structure que je prépare à l'avance.

Je l'ai peut etre mal dit mais je sauve riend ans la boucle (pas fou) mais bien un gros dump sur disk apres la boucle qui m'embetent

Rappel la structure du fichier stp.

---------------
Le Tyran

BENB

100% Lux.

Puisque tu fais CRC += c'est bien que c'est iteratif !

de plus au lieu de faire de 0 à taille -2 tu peut bien faire de 2à la fin du traitement

CRC += ( a+b+c)...

ou a b et c sont les trois derniers caracteres traités...

Joel F

Real men use unique_ptr

Structure du fichier pour Leto II

Partie 1 : Header

short : CRC
short : nb d'éléments
long : nb d'éléments (fo pas chercher)
long : offset de début des chaines
long : nb d'erreur (cf plus loin) maximale
long : offset de fin des chaines

Partie 2 : Index de hashage

nb d'elements *
short : valeur de hashage de la clé correspondante.

PArtie 3 : Headers des chaines

nb d'éléments *

bool : indicateur d'utilisation
long : indice actuel dans le tableau (de 0 à nb éléments )
long : offset fichier de la clé correspondante
long : offset fichier de la valeur ""
long : taille de la chaine

Partie 4 :

Ensemble des clés et des chaines, par paires, séparées par des '\0'
ex:
"Clé 1\0Chaine 1\0Clé 2\0Chaine 2"

lorsque j'insére un élément dans ce tableau, je calcule sa valeur de hash de la clé. Je regarde à cet indice dans la partie 3. Si cet emplacement est libre, j'y colle la structure bien remplie, sinon j'ajoute un a la valeur de hash et je recommence jusk'a trouver une place libre. Si je sors du tableau, je retourne au début.

Ex :
Clé 1 --> Hash = 3
Clé 2 --> Hash = 5
Clé 3 --> Hash = 3
Clé 4 --> Hash = 4
Clé 5 --> Hash = 9
Clé 6 --> Hash = 1

J'insére Clé 1 -> OK
J'insére Clé 2 -> OK
J'insére Clé 3 -> KO, place prise par 1, je me déplace en 4 ,OK
J'insére Clé 4 -> KO, pris par 3, je vais en 5, KO, je vais en 6 OK
J'insére Clé 5 -> OK
J'insére Clé 6 -> OK

Résulat

Tableau[1]= 6
Tableau[2]=
Tableau[3]= 1
Tableau[4]= 3
Tableau[5]= 2
Tableau[6]= 4
Tableau[7]=
Tableau[8]=
Tableau[9]= 1

Ok c clair ??

Le nombre d'erreur du header c le + grand décalage entre un valeur de hash et la position de la clé correspondante . Ici la Clé 4 devait aller en 3 et se retrouve en 6.

nbErreur = 3.

Ca va ?

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

Structure du fichier pour Leto II

Partie 1 : Header

short : CRC
short : nb d'éléments
long : nb d'éléments (fo pas chercher)
long : offset de début des chaines
long : nb d'erreur (cf plus loin) maximale
long : offset de fin des chaines

Partie 2 : Index de hashage

nb d'elements *
short : valeur de hashage de la clé correspondante.

PArtie 3 : Headers des chaines

nb d'éléments *

bool : indicateur d'utilisation
long : indice actuel dans le tableau (de 0 à nb éléments )
long : offset fichier de la clé correspondante
long : offset fichier de la valeur ""
long : taille de la chaine

Partie 4 :

Ensemble des clés et des chaines, par paires, séparées par des '\0'
ex:
"Clé 1\0Chaine 1\0Clé 2\0Chaine 2"

lorsque j'insére un élément dans ce tableau, je calcule sa valeur de hash de la clé. Je regarde à cet indice dans la partie 3. Si cet emplacement est libre, j'y colle la structure bien remplie, sinon j'ajoute un a la valeur de hash et je recommence jusk'a trouver une place libre. Si je sors du tableau, je retourne au début.

Ex :
Clé 1 --> Hash = 3
Clé 2 --> Hash = 5
Clé 3 --> Hash = 3
Clé 4 --> Hash = 4
Clé 5 --> Hash = 9
Clé 6 --> Hash = 1

J'insére Clé 1 -> OK
J'insére Clé 2 -> OK
J'insére Clé 3 -> KO, place prise par 1, je me déplace en 4 ,OK
J'insére Clé 4 -> KO, pris par 3, je vais en 5, KO, je vais en 6 OK
J'insére Clé 5 -> OK
J'insére Clé 6 -> OK

Résulat

Tableau[1]= 6
Tableau[2]=
Tableau[3]= 1
Tableau[4]= 3
Tableau[5]= 2
Tableau[6]= 4
Tableau[7]=
Tableau[8]=
Tableau[9]= 1

Ok c clair ??

Le nombre d'erreur du header c le + grand décalage entre un valeur de hash et la position de la clé correspondante . Ici la Clé 4 devait aller en 3 et se retrouve en 6.

nbErreur = 3.

Ca va ?

Alors tu peux essayer de le faire en une seule passe (c à dire que tu écrit dans ton fichier dans ta boucle au lieu d'écrire après) Tu écrit un gros bloc au début u fichier de la taille nécessaire ensuite à chaque itération tu met à jour le header de la chaine et tu l'écrit (en te déplacent dans le fichier) Tu calcul ton CRC et à la fin tu modifie ça valeur en début de fichier.

---------------
Le Tyran

Joel F

Real men use unique_ptr

LetoII a écrit a écrit :

Alors tu peux essayer de le faire en une seule passe (c à dire que tu écrit dans ton fichier dans ta boucle au lieu d'écrire après) Tu écrit un gros bloc au début u fichier de la taille nécessaire ensuite à chaque itération tu met à jour le header de la chaine et tu l'écrit (en te déplacent dans le fichier) Tu calcul ton CRC et à la fin tu modifie ça valeur en début de fichier.

.... le meme en + clair ?

LetoII

Le dormeur doit se réveiller

Joel F a écrit a écrit :

.... le meme en + clair ?

Toi y en a calculer la place de tout tes header
Toi y en a allouer un bloc de cette taille
Toi y en a l'écrir dans fichier
Toi y en a faire ta boucle sur tes chaines
Toi y en a écrire info au fur et à mesure de leur disponibilité dans fichier

Je vais avoir du mal à faire mieu là

C pas sûr que t'y gagne à cause de la navigation dans le fichier mais bon faut tanter.

---------------
Le Tyran

Joel F

Real men use unique_ptr

Moi y en a compris mais moi y en apenser ca pas rapidos paske
disque bien lent itou

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

C++

De la lenteur de string avec BC++ 5 et d'un algo de m*** en general ..

Sujets relatifs
eingénierie et programmation en général !	[ALGO] les grand mondes .....
algo deplacements	[PHP] aide avec une fonction de rajout de dates / string
[Java] Remplacer un string par un string (Résolu)	convertir un prog java en algo ?
[Algo] Faire un fondu entre 2 images...	[vb] utiliser un string pour un nom de fichier
Un algo de tri, oui mais avec Iterator	[Algo] un site sur la syntaxe algorithmique ?
Plus de sujets relatifs à : De la lenteur de string avec BC++ 5 et d'un algo de m*** en general ..

Page générée en 0.077 secondes