Optimisation

Fabien LE LEZ wrote:

On Thu, 25 Nov 2004 00:31:20 +0100, "nico" <spam@spam.spam>:

J'obtiens donc une version optimisée ressemblant à ceci :

string xor_crypte(string *str_in,string *clef) {

Uh ? Où as-tu vu ce genre de choses ?


string xor_crypte (string const& str_in, string const& clef)
{...

Pourquoi pas string xor_crypte(string const* str_in,string const* clef) ?
On veut des pointeurs !

"Richard Delorme" <abulmo@nospam.fr> a écrit dans le message de news:
41a5142d$0$10781$7a628cd7@news.club-internet.fr...

Bonjour,

A titre d'entrainement j'ai ecrit la fonction suivante :

string xor_crypte(string str_in,string clef) {
int str_len=str_in.length();
int clef_len=clef.length();
string str_out;
for(int i=0;i<str_len;i+=clef_len) {
for(int j=0;j<clef_len;j++) {
char c[1]={ static_cast<char>(*str_in.substr(i+j,1).c_str()) ^
static_cast<char>(*clef.substr(j,1).c_str()) };
str_out+=string(c,1);
}
}

static_cast<char>(*str_in.substr(i+j,1).c_str() est une façon compliqué
d'écrire : str_in.at(i + j) ou str_in[i + j], si la vérification de
l'index était inutile.

En plus ce programme est erroné, car i + j peut être "out of range",
c'est-à-dire plus grand que str_len.
Une écriture un peu plus optimale et correcte de la boucle pourrait être:

for (int i = 0; i < str_len; ++i) {
const int j = i % clef_len;
str_out.append(1, str_in[i] ^ clef[j]);
}

Il me semble que l'utilisation de l'operateur += est plus idiomatique (enfin
moi je la trouve plus lisible)... str_out += str_in[i] ^ clef[j];

ou str_out.push_back(str_in[i] ^ clef[j]);

mais je fais trop de Java en ce moment...

--
Richard

On Thu, 25 Nov 2004 00:57:46 +0100, "nico" <spam@spam.spam>:

Pourquoi pas string xor_crypte(string const* str_in,string const* clef) ?

Lis donc le thread "difference entre reference et pointeur ?" du
22/11...

On veut des pointeurs !

Pourquoi ?

Un pointeur est à la fois un objet à part entière (qui prend 32 bits
sur ma machine) et une "référence" à une variable, ou NULL.

On utilisera donc un pointeur :

- si on a effectivement besoin d'un objet (par exemple, on peut créer
un vector<> de pointeurs, mais pas de références)

- si on a besoin de la possibilité de pointer sur rien (NULL)

- s'il est "naturel" d'utiliser un pointeur. Par exemple, new renvoie
un pointeur, donc
Machin* m= new Machin;
me paraît plus naturel que
Machin& m= *new Machin;

Dans le cas qui nous occupe, passer les arguments par pointeurs
n'apporte aucun avantage, et que des inconvénients :
- l'indirection alourdit l'écriture
- tu dois préciser dans la doc que les pointeurs ne doivent pas
être NULL, et éventuellement le tester dans ta fonction.


--
;-)

"nico" <spam@spam.spam> writes:

Bonjour,

A titre d'entrainement j'ai ecrit la fonction suivante :

string xor_crypte(string str_in,string clef) {
int str_len=str_in.length();
int clef_len=clef.length();
string str_out;
for(int i=0;i<str_len;i+=clef_len) {
for(int j=0;j<clef_len;j++) {
char c[1]={ static_cast<char>(*str_in.substr(i+j,1).c_str()) ^
static_cast<char>(*clef.substr(j,1).c_str()) };
str_out+=string(c,1);
}
}
return str_out;
}

Que faudrait-il faire pour éventuellement l'optimiser ?

D'abord la rendre lisible,

string xor_crypte(string str_in, string clef) {
int str_len = str_in.length();
int clef_len = clef.length();
string str_out;

for(int i = 0; i < str_len; i += clef_len) {
for(int j = 0; j < clef_len; j++) {
char c[1]= { static_cast<char>(*str_in.substr(i+j,1).c_str())
^ static_cast<char>(*clef.substr(j,1).c_str()) };
str_out+=string(c,1);
}
}
return str_out;
}

la rendre correcte (substr jette une exception si son premier argument
est plus grand que la taille de la chaine, on utilise des unsigned
pour appliquer des operateurs binaires),

string xor_crypte(string str_in, string clef) {
int str_len = str_in.length();
int clef_len = clef.length();
string str_out;

for(int i = 0; i < str_len; i += clef_len) {
for(int j = 0; j < clef_len && i + j < str_len; j++) {
char c[1]= { static_cast<unsigned char>(*str_in.substr(i+j,1).c_str())
^ static_cast<unsigned char>(*clef.substr(j,1).c_str()) };
str_out+=string(c,1);
}
}
return str_out;
}

la rendre idiomatique (les string sont generalement passees par
reference, on n'utilise pas substr pour acceder a un seul element, on
utilise const, on ne melange pas les langues dans les identificateurs),

string simple_crypt(string const& message, string const& key) {
int const message_length = message.length();
int const key_length = key.length();
string result;

for(int i = 0; i < message_length; i += key_length) {
for(int j = 0; j < key_length && i + j < message_length; ++j) {
result += static_cast<unsigned char>(message[i+j])
^ static_cast<unsigned char>(key[j]);
}
}
return result;
}

Ceci fait, on a deja fait des choses qui doivent ameliorer les
performances:
- utilisation des references plutot que de la copie pour les
parametres
- non construction de resultats temporaires inutiles (substr,
c_str qui peut devoir ajouter un '' final et entrainer des
allocations, string(c,1))

Avant de faire plus, mesurer que la fonction est bien dans le chemin
critique de l'application sur des cas reels.

Ceci fait, la premiere optimisation est d'utiliser reserve sur result
puisqu'on connait sa longueur finale.

Apres il y a des choses a mesurer pour voir comment ca se passe, parce
que je ne suis pas sur que ce soit meilleur. Et ca peut etre meilleur
a partir de seuils (une certaine taille de message_length, une
certaine taille de key_length, un certain rapport entre les deux, ...)
uniquement sur certaines plateformes, uniquement en combinaison avec
d'autre chose. Attention aussi a faire les mesures en contexte, les
effets de caches peuvent parfois etre surprenant.

* utiliser j = i % key_length
* utiliser des iterateurs
* faire parcourir des pointeurs sur data() plutot que d'utiliser
l'indexation ou des pointeurs
* voir si utiliser resize et result[i+j] = est un gain par rapport a
utiliser reserve et result + * Decouper la premiere boucle pour eviter que la seconde ait une
condition compliquee:
int const bi = (message_length / key_length) * key_length;
int const bj = message_length * key_length;
for (int i = 0; i < bi; i+= key_length)...
for (int j = 0; j < bj; ++j)...
* agrandir la cle en la recopiant (used_key = key+key+key_key)
* faire les xor en utilisant des unsigned long plutot que des chars,
pour en faire plusieurs en // (en particulier l'utilisation de
resize peut devenir interessante uniquement ici). Attention aux
alignements, meme si les acces non alignes sont autorises, ils peuvent
etre moins efficaces.
* changer l'interface pour passer le resultat dans un parametre et
eviter la copie

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Matthieu Moy wrote:

i := ma_string.end();

réminiscence du Pascal ? ;-)

--
Arnaud (qui ne veut pas entendre parler de proximité de : et | ;-))
(Supprimez les geneurs pour me répondre)

Fabien LE LEZ wrote:

On Thu, 25 Nov 2004 00:57:46 +0100, "nico" <spam@spam.spam>:

Pourquoi pas string xor_crypte(string const* str_in,string const*
clef) ?

Lis donc le thread "difference entre reference et pointeur ?" du
22/11...

On veut des pointeurs !

Pourquoi ?

Un pointeur est à la fois un objet à part entière (qui prend 32 bits
sur ma machine) et une "référence" à une variable, ou NULL.

On utilisera donc un pointeur :

- si on a effectivement besoin d'un objet (par exemple, on peut créer
un vector<> de pointeurs, mais pas de références)

- si on a besoin de la possibilité de pointer sur rien (NULL)

- s'il est "naturel" d'utiliser un pointeur. Par exemple, new renvoie
un pointeur, donc
Machin* m= new Machin;
me paraît plus naturel que
Machin& m= *new Machin;

Dans le cas qui nous occupe, passer les arguments par pointeurs
n'apporte aucun avantage, et que des inconvénients :
- l'indirection alourdit l'écriture
- tu dois préciser dans la doc que les pointeurs ne doivent pas
être NULL, et éventuellement le tester dans ta fonction.

ok merci je croyais que passage par pointer et reference revenait au mm !

--
nico

Jean-Marc Bourguet wrote:

"nico" <spam@spam.spam> writes:

Bonjour,

A titre d'entrainement j'ai ecrit la fonction suivante :

string xor_crypte(string str_in,string clef) {
int str_len=str_in.length();
int clef_len=clef.length();
string str_out;
for(int i=0;i<str_len;i+=clef_len) {
for(int j=0;j<clef_len;j++) {
char c[1]={ static_cast<char>(*str_in.substr(i+j,1).c_str()) ^
static_cast<char>(*clef.substr(j,1).c_str()) };
str_out+=string(c,1);
}
}
return str_out;
}

Que faudrait-il faire pour éventuellement l'optimiser ?

D'abord la rendre lisible,

string xor_crypte(string str_in, string clef) {
int str_len = str_in.length();
int clef_len = clef.length();
string str_out;

for(int i = 0; i < str_len; i += clef_len) {
for(int j = 0; j < clef_len; j++) {
char c[1]= { static_cast<char>(*str_in.substr(i+j,1).c_str())
^ static_cast<char>(*clef.substr(j,1).c_str()) };
str_out+=string(c,1);
}
}
return str_out;
}

la rendre correcte (substr jette une exception si son premier argument
est plus grand que la taille de la chaine, on utilise des unsigned
pour appliquer des operateurs binaires),

string xor_crypte(string str_in, string clef) {
int str_len = str_in.length();
int clef_len = clef.length();
string str_out;

for(int i = 0; i < str_len; i += clef_len) {
for(int j = 0; j < clef_len && i + j < str_len; j++) {
char c[1]= { static_cast<unsigned
char>(*str_in.substr(i+j,1).c_str()) ^
static_cast<unsigned char>(*clef.substr(j,1).c_str()) };
str_out+=string(c,1); }
}
return str_out;
}

la rendre idiomatique (les string sont generalement passees par
reference, on n'utilise pas substr pour acceder a un seul element, on
utilise const, on ne melange pas les langues dans les
identificateurs),

string simple_crypt(string const& message, string const& key) {
int const message_length = message.length();
int const key_length = key.length();
string result;

for(int i = 0; i < message_length; i += key_length) {
for(int j = 0; j < key_length && i + j < message_length; ++j) {
result += static_cast<unsigned char>(message[i+j])
^ static_cast<unsigned char>(key[j]);
}
}
return result;
}

Ceci fait, on a deja fait des choses qui doivent ameliorer les
performances:
- utilisation des references plutot que de la copie pour les
parametres
- non construction de resultats temporaires inutiles (substr,
c_str qui peut devoir ajouter un '' final et entrainer des
allocations, string(c,1))

Avant de faire plus, mesurer que la fonction est bien dans le chemin
critique de l'application sur des cas reels.

Ceci fait, la premiere optimisation est d'utiliser reserve sur result
puisqu'on connait sa longueur finale.

Apres il y a des choses a mesurer pour voir comment ca se passe, parce
que je ne suis pas sur que ce soit meilleur. Et ca peut etre meilleur
a partir de seuils (une certaine taille de message_length, une
certaine taille de key_length, un certain rapport entre les deux, ...)
uniquement sur certaines plateformes, uniquement en combinaison avec
d'autre chose. Attention aussi a faire les mesures en contexte, les
effets de caches peuvent parfois etre surprenant.

* utiliser j = i % key_length
* utiliser des iterateurs
* faire parcourir des pointeurs sur data() plutot que d'utiliser
l'indexation ou des pointeurs
* voir si utiliser resize et result[i+j] = est un gain par rapport a
utiliser reserve et result + > * Decouper la premiere boucle pour eviter que la seconde ait une
condition compliquee:
int const bi = (message_length / key_length) * key_length;
int const bj = message_length * key_length;
for (int i = 0; i < bi; i+= key_length)...
for (int j = 0; j < bj; ++j)...
* agrandir la cle en la recopiant (used_key = key+key+key_key)
* faire les xor en utilisant des unsigned long plutot que des chars,
pour en faire plusieurs en // (en particulier l'utilisation de
resize peut devenir interessante uniquement ici). Attention aux
alignements, meme si les acces non alignes sont autorises, ils
peuvent etre moins efficaces.
* changer l'interface pour passer le resultat dans un parametre et
eviter la copie

A+

Bonjour,


Ok Merci Beaucoup !!!

--
nico

"nico" <spam@spam.spam> wrote in message
news:<41a5071b$0$32298$626a14ce@news.free.fr>...

A titre d'entrainement j'ai ecrit la fonction suivante :

string xor_crypte(string str_in,string clef) {
int str_len=str_in.length();
int clef_len=clef.length();
string str_out;
for(int i=0;i<str_len;i+=clef_len) {
for(int j=0;j<clef_len;j++) {
char c[1]={ static_cast<char>(*str_in.substr(i+j,1).c_str()) ^
static_cast<char>(*clef.substr(j,1).c_str()) };
str_out+=string(c,1);
}
}
return str_out;
}

Que faudrait-il faire pour éventuellement l'optimiser ?

D'abord, le rendre correct. Actuellement, il a un comportement indéfini
chaque fois que la longueur de la chaîne à encrypter n'est pas une
multiple exacte de la longueur de la clé.

Ensuite, j'utiliserais les fonctions de la bibliothèque standard --
elles sont là pour ça. Ce qui donnerait quelque chose du genre :

class Encrypteur
{
public:
explicit Encrypteur( std::string const& cle )
: maCle( cle )
, maPosition( 0 )
{
assert( maCle.size() > 0 ) ;
}
char operator()( char ch )
{
char result = ch ^ maCle[ maPosition ] ;
++ maPosition ;
if ( maPosition >= maCle.size() ) {
maPosition = 0 ;
}
return result ;
}

private:
std::string maCle ;
size_t maPosition ;
} ;

std::string
xorCrypt(
std::string const& source,
std::string const& cle )
{
std::string result ;
std::transform(
source.begin(),
source.end(),
std::back_inserter( result ),
Encrypteur( cle ) ) ;
return result ;
}

Ensuite, et seulement ensuite, je considèrerais les problèmes de
l'optimisation. Ici, je vois deux possibilités intéressantes : que
Encrypteur n'ait qu'un pointeur à la clé, plutôt qu'une copie (mais
selon la longueur de la clé et l'implémentation de std::string, c'est
possible aussi que ce soit une pessimisation). Et peut-être plus
important, de faire l'encryption « en place », c-à-d qu'on passe une
référence non-const à la chaîne à encrypter, et qu'après l'appel du
programme, c'est cette chaîne même qui contient la chaîne encryptée.

Mais dans beaucoup de cas, l'optimisation la plus importante serait
aussi la plus simple : ajouter simplement la ligne :
result.reserve( source.size() ) ;
après la declaration de result.

Une autre possibilité (plus générique) serait d'utiliser un itérateur
et un opérateur spécial avec la version à deux sources de transform.

--
James Kanze GABI Software http://www.gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Matthieu Moy <MatthieuNOSPAM.Moy@imag.fr.invalid> writes:

Si tu veux le 42ème caractère (en partant de 0) de la chaine
ma_string, un ma_string[42] me parait simple et adapté ;-)

Bof.

--drkm

"nico" <spam@spam.spam> writes:

[ 126 lines skipped. ]

Ok Merci Beaucoup !!!

Ne cite que la partie pertinente du message auquel tu réponds, stp.

Merci.

--drkm