Version la plus rapide

Le
Michaël Delva
Bonsoir à tous,

une petite question sur la version de ce code qui vous paraît être la
plus rapide, ou du moins celle que vous utiliseriez. Ce code permet
d'éviter les doublons dans une liste:

//--

int nbre_noeuds = XML->GetCount();

if (nbre_noeuds > 0)
{
std::vector<AnsiString> liste_strategies(nbre_noeuds);
XML->Push(0);
for (int i=0; i < nbre_noeuds; i++)
{
XML->Modify(i);
liste_strategies[i] = XML->GetAttr("Nom");
}

std::sort(liste_strategies.begin(),liste_strategies.end());
std::vector<AnsiString>::iterator p = std::unique
(liste_strategies.begin(),liste_strategies.end());
liste_strategies.erase(p,liste_strategies.end());
}

//--

Ou bien

//--

int nbre_noeuds = XML->GetCount();

if (nbre_noeuds > 0)
{
std::set<AnsiString> liste_strategies;
XML->Push(0);
for (int i=0; i < nbre_noeuds; i++)
{
XML->Modify(i);
liste_strategies.insert(XML->GetAttr("Nom"));
}
}

//--

Je me posais la question car cet article ne conseille vraiment pas
d'utiliser les std::set

http://www.lafstern.org/matt/col1.pdf

Merci d'avance!!

Et bonne nuit pour ceux qui dorment pas ;-)
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Michel Michaud
Le #168510
Dans news:, Michaël
une petite question sur la version de ce code qui vous paraît être
la plus rapide, ou du moins celle que vous utiliseriez. Ce code
permet d'éviter les doublons dans une liste:


[Comparaison d'utilisation de sort+unique vs un set]

En principe, utiliser un set pour mettre des données en ordre est
plus lent que trier un vecteur (par un bon algo évidemment). Donc
si tu as peu de doublons, la méthode du tri suivi de unique sera
certainement plus rapide. Par contre, si tu as très peu de données
et beaucoup de doublons ça pourrait être plus rapide de passer par
set car il y aura moins de manipulations (copie) de données, mais
ça dépendra aussi de la taille de tes données....

Où se situe le point où une méthode sera meilleure que l'autre ?
Ça dépend de trop de facteurs pour qu'on puisse le dire. Mon
impression (comme tu parles de XML et que tu manipules des
strings que je suppose pas trop longue), c'est que tu auras assez
de données pour que sort/unique soit toujours mieux.

La seule réponse formelle possible est donc toujours la même dans
ce genre de cas : écrire le code le plus clair et correct. Si la
vitesse pose problème, et seulement si elle pose problème à cause
de ce code, essayer diverses méthodes pour voir en pratique ce qui
est mieux, tout en notant que ça pourra probalement changer avec
un nouveau compilateur, une nouvelle bibliothèque, un changement dans
la quantité de mémoire disponible dans l'ordinateur, une modification
des données à conserver, etc. ! De plus, je vois mal comment choisir
un jeu de données typique pour faire les comparaisons...

--
Michel Michaud
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/

Michaël Delva
Le #168505
"Michel Michaud" @news20.bellglobal.com:

Dans news:, Michaël
une petite question sur la version de ce code qui vous paraît être
la plus rapide, ou du moins celle que vous utiliseriez. Ce code
permet d'éviter les doublons dans une liste:


[Comparaison d'utilisation de sort+unique vs un set]

En principe, utiliser un set pour mettre des données en ordre est
plus lent que trier un vecteur (par un bon algo évidemment). Donc
si tu as peu de doublons, la méthode du tri suivi de unique sera
certainement plus rapide. Par contre, si tu as très peu de données
et beaucoup de doublons ça pourrait être plus rapide de passer par
set car il y aura moins de manipulations (copie) de données, mais
ça dépendra aussi de la taille de tes données....

Où se situe le point où une méthode sera meilleure que l'autre ?
Ça dépend de trop de facteurs pour qu'on puisse le dire. Mon
impression (comme tu parles de XML et que tu manipules des
strings que je suppose pas trop longue), c'est que tu auras assez
de données pour que sort/unique soit toujours mieux.


Effectivement c'est le cas... Je vais donc garder cette méthode. Mais je
pensais vraiment qu'insérer directement dans un set était quand même plus
rapide que 3 opérations: sort,unique,erase...

Comme quoi...

La seule réponse formelle possible est donc toujours la même dans
ce genre de cas : écrire le code le plus clair et correct. Si la
vitesse pose problème, et seulement si elle pose problème à cause
de ce code, essayer diverses méthodes pour voir en pratique ce qui
est mieux, tout en notant que ça pourra probalement changer avec
un nouveau compilateur, une nouvelle bibliothèque, un changement dans
la quantité de mémoire disponible dans l'ordinateur, une modification
des données à conserver, etc. ! De plus, je vois mal comment choisir
un jeu de données typique pour faire les comparaisons...



Il est vrai qu'avec autant de paramètres qui entrent en jeu, c'est
difficile de se prononcer pour le choix d'une méhode...

Merci!!


Fabien LE LEZ
Le #168402
On 03 Mar 2004 12:28:32 GMT, "Michaël Delva" wrote:

Effectivement c'est le cas... Je vais donc garder cette méthode. Mais je
pensais vraiment qu'insérer directement dans un set était quand même plus
rapide que 3 opérations: sort,unique,erase...


Mais tu fais l'opération d'insertion un grand nombre de fois.

--
;-)

Michaël Delva
Le #168400
Fabien LE LEZ news::

On 03 Mar 2004 12:28:32 GMT, "Michaël Delva" wrote:

Effectivement c'est le cas... Je vais donc garder cette méthode. Mais
je pensais vraiment qu'insérer directement dans un set était quand
même plus rapide que 3 opérations: sort,unique,erase...


Mais tu fais l'opération d'insertion un grand nombre de fois.



Et l'insertion dans un set est si couteuse que ça, par rapport aux 3
opérations?

Parce que si je ne m'abuse, le sort et le unique parcourent quand même
l'intégralité du vecteur.

Si c'est vraiment plus rapide, faudra que je revoie certaines parties de
mon code.

Et côté mémoire, je suppose que c'est moins couteux également d'utiliser le
vector?


Fabien LE LEZ
Le #168399
On 03 Mar 2004 21:19:04 GMT, "Michaël Delva" wrote:

Et l'insertion dans un set est si couteuse que ça, par rapport aux 3
opérations?


Honnêtement, je n'en sais rien. Je voulais juste dire que départager
les deux solutions n'est pas si évident que ça.

Pour le reste, je ne peux que copier-coller la réponse de Michel, ça
m'évitera de le paraphraser :

La seule réponse formelle possible est donc toujours la même dans
ce genre de cas : écrire le code le plus clair et correct. Si la
vitesse pose problème, et seulement si elle pose problème à cause
de ce code, essayer diverses méthodes pour voir en pratique ce qui
est mieux, tout en notant que ça pourra probalement changer avec
un nouveau compilateur, une nouvelle bibliothèque, un changement dans
la quantité de mémoire disponible dans l'ordinateur, une modification
des données à conserver, etc.


--
;-)

Michaël Delva
Le #168398
Fabien LE LEZ news::

On 03 Mar 2004 21:19:04 GMT, "Michaël Delva" wrote:

Et l'insertion dans un set est si couteuse que ça, par rapport aux 3
opérations?


Honnêtement, je n'en sais rien. Je voulais juste dire que départager
les deux solutions n'est pas si évident que ça.

Pour le reste, je ne peux que copier-coller la réponse de Michel, ça
m'évitera de le paraphraser :

La seule réponse formelle possible est donc toujours la même dans
ce genre de cas : écrire le code le plus clair et correct. Si la
vitesse pose problème, et seulement si elle pose problème à cause
de ce code, essayer diverses méthodes pour voir en pratique ce qui
est mieux, tout en notant que ça pourra probalement changer avec
un nouveau compilateur, une nouvelle bibliothèque, un changement dans
la quantité de mémoire disponible dans l'ordinateur, une modification
des données à conserver, etc.




Bon ben merci Michel, je fais comme tu dis ;-D


Loïc Joly
Le #170069
Michaël Delva wrote:
Fabien LE LEZ news::


On 03 Mar 2004 12:28:32 GMT, "Michaël Delva" wrote:


Effectivement c'est le cas... Je vais donc garder cette méthode. Mais
je pensais vraiment qu'insérer directement dans un set était quand
même plus rapide que 3 opérations: sort,unique,erase...


Mais tu fais l'opération d'insertion un grand nombre de fois.




Et l'insertion dans un set est si couteuse que ça, par rapport aux 3
opérations?


L'insertion dans un set est en O(N)
Faire N insetions est donc en O(N log N)

L'insertion dans un vecteur est en amortie en O(1), l'insertion de tous
les éléments est donc en O(N)
Le tri est lui en O(N log N)
Le unique est en O(N)
Le tout est donc en O(N log N)

On ne peut donc pas déterminer a priori quel sera le plus rapide pour
des grands nombres.


Parce que si je ne m'abuse, le sort et le unique parcourent quand même
l'intégralité du vecteur.


Et chaque insertion parcourt partiellement le set.

Si c'est vraiment plus rapide, faudra que je revoie certaines parties de
mon code.

Et côté mémoire, je suppose que c'est moins couteux également d'utiliser le
vector?


Ce n'est pas spécifié dans le standard. Maintenant, étant donné que le
vecteur est une structure très simple, il y a effectivement de fortes
chances que ce soit le cas (une implémentation où ce ne serait pas au
moins l'égalité aurait probablement du le faire exprès).

--
Loïc



Franck Branjonneau
Le #170068
Loïc Joly

L'insertion dans un set est en O(N)
Faire N insetions est donc en O(N log N)


Vraiment ?
--
Franck Branjonneau
Michaël Delva
Le #170067
Loïc Joly news:c25nkg$v9o$:

L'insertion dans un set est en O(N)
Faire N insetions est donc en O(N log N)

L'insertion dans un vecteur est en amortie en O(1), l'insertion de
tous les éléments est donc en O(N)
Le tri est lui en O(N log N)
Le unique est en O(N)
Le tout est donc en O(N log N)

On ne peut donc pas déterminer a priori quel sera le plus rapide pour
des grands nombres.



Voilà qui est intéressant...

Et côté mémoire, je suppose que c'est moins couteux également
d'utiliser le vector?


Ce n'est pas spécifié dans le standard. Maintenant, étant donné que le
vecteur est une structure très simple, il y a effectivement de fortes
chances que ce soit le cas (une implémentation où ce ne serait pas au
moins l'égalité aurait probablement du le faire exprès).



C'est ce que je pensais...

Merci pour tes éclaircissements!


Loïc Joly
Le #170066
Franck Branjonneau wrote:

Loïc Joly
L'insertion dans un set est en O(N)



Qui a écrit une telle {e|ho}rreur !? On a du mettre un virus de
l'internet sur mon ordinateur... ;)

Il fallait bien entendu lire que cette insertion est en O(log N).
Le reste du raisonnement lui doit être correct.

--
Loïc


Publicité
Poster une réponse
Anonyme