C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Version la plus rapide Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ (French) View previous topic :: View next topic   Author Message Michaël Delva Guest Posted: Wed Mar 03, 2004 2:23 am    Post subject: Version la plus rapide 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 Back to top Michel Michaud Guest Posted: Wed Mar 03, 2004 3:02 am    Post subject: Re: Version la plus rapide Dans news:Xns94A122871E1C9zoubidamanhotmailcom (AT) 212 (DOT) 27.42.67, Michaël Delva <zoubidaman (AT) hotmail (DOT) com> a écrit : Quote: 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 [email]mm (AT) gdzid (DOT) com[/email] http://www.gdzid.com FAQ de fr.comp.lang.c++ : http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/ Back to top Michaël Delva Guest Posted: Wed Mar 03, 2004 12:28 pm    Post subject: Re: Version la plus rapide "Michel Michaud" <mm (AT) gdzid (DOT) com> wrote in news:VUb1c.13844$qA2.646611 @news20.bellglobal.com: Quote: Dans news:Xns94A122871E1C9zoubidamanhotmailcom (AT) 212 (DOT) 27.42.67, Michaël Delva <zoubidaman (AT) hotmail (DOT) com> a écrit : 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... Quote: 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!! Back to top Fabien LE LEZ Guest Posted: Wed Mar 03, 2004 8:30 pm    Post subject: Re: Version la plus rapide On 03 Mar 2004 12:28:32 GMT, "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> wrote: Quote: 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. -- ;-) Back to top Michaël Delva Guest Posted: Wed Mar 03, 2004 9:19 pm    Post subject: Re: Version la plus rapide Fabien LE LEZ <gramster (AT) gramster (DOT) com> wrote in news:m1gc4014plisvqu397mqskilceu2d4k09d (AT) 4ax (DOT) com: Quote: 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? Back to top Fabien LE LEZ Guest Posted: Wed Mar 03, 2004 9:42 pm    Post subject: Re: Version la plus rapide On 03 Mar 2004 21:19:04 GMT, "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> wrote: Quote: 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 : Quote: 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. -- ;-) Back to top Michaël Delva Guest Posted: Wed Mar 03, 2004 9:51 pm    Post subject: Re: Version la plus rapide Fabien LE LEZ <gramster (AT) gramster (DOT) com> wrote in news:c8kc40dfpll0ltvpkvb0qd4i2bh1ags96f (AT) 4ax (DOT) com: Quote: 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 Back to top Loïc Joly Guest Posted: Wed Mar 03, 2004 10:56 pm    Post subject: Re: Version la plus rapide Michaël Delva wrote: Quote: Fabien LE LEZ <gramster (AT) gramster (DOT) com> wrote in news:m1gc4014plisvqu397mqskilceu2d4k09d (AT) 4ax (DOT) com: 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. Quote: 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. Quote: 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 Back to top Franck Branjonneau Guest Posted: Wed Mar 03, 2004 10:56 pm    Post subject: Re: Version la plus rapide Loïc Joly <loic.actarus.joly (AT) wanadoo (DOT) fr> écrivait: Quote: L'insertion dans un set est en O(N) Faire N insetions est donc en O(N log N) Vraiment ? -- Franck Branjonneau <fasbjx (AT) free (DOT) fr> Back to top Michaël Delva Guest Posted: Wed Mar 03, 2004 11:22 pm    Post subject: Re: Version la plus rapide Loïc Joly <loic.actarus.joly (AT) wanadoo (DOT) fr> wrote in news:c25nkg$v9o$1 (AT) news-reader1 (DOT) wanadoo.fr: Quote: 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... Quote: 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! Back to top Loïc Joly Guest Posted: Wed Mar 03, 2004 11:43 pm    Post subject: Re: Version la plus rapide Franck Branjonneau wrote: Quote: Loïc Joly <loic.actarus.joly (AT) wanadoo (DOT) fr> écrivait: 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 Back to top Fabien LE LEZ Guest Posted: Wed Mar 03, 2004 11:58 pm    Post subject: Re: Version la plus rapide On 03 Mar 2004 21:51:52 GMT, "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> wrote: Quote: Bon ben merci De rien, Mich ;-) -- ;-) Back to top Michel Michaud Guest Posted: Thu Mar 04, 2004 1:09 am    Post subject: Re: Version la plus rapide Dans news:Xns94A189195464Azoubidamanhotmailcom (AT) 212 (DOT) 27.42.67, Michaël Delva <zoubidaman (AT) hotmail (DOT) com> a écrit : Quote: Mais je pensais vraiment qu'insérer directement dans un set était quand même plus rapide que 3 opérations: sort,unique,erase... Quicksort est vraiment étonnamment rapide (toute proportion gardée). Si l'insertion dans un arbre balancé (ce qu'est normalement un std::set) était si rapide, on s'en servirait plutôt que les algorithmes de tri courants : on s'en sert parfois, mais pas pour trier des données ordinaires en mémoire. Il ne faut pas oublier tout ce qu'il faut faire pour maintenir un arbre. Et un arbre balancé, c'est pire. D'autres ont continué la discussion sur cet aspect. Je voulais simplement ajouter dire que la méthode la plus rapide, s'il s'agit simplement d'enlever les doublons, est probablement l'emploi d'une table de hachage. Je me demande d'ailleurs si, dans peu de temps, tu ne serais pas revenu avec une question sur la recherche dans ton vecteur. Ne pas oublier que dans un vecteur trié la recherche (binaire) est O(log N), alors que dans une table de hachage, on peut avoir O(1) ! Le seul défaut avec la table de hachage, c'est que les données ne sont pas en ordre. Mais c'est bien moins souvent nécessaire qu'on peut le croire. -- Michel Michaud [email]mm (AT) gdzid (DOT) com[/email] http://www.gdzid.com FAQ de fr.comp.lang.c++ : http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/ Back to top kanze@gabi-soft.fr Guest Posted: Thu Mar 04, 2004 8:17 am    Post subject: Re: Version la plus rapide "Michaël Delva" <zoubidaman (AT) hotmail (DOT) com> wrote Quote: "Michel Michaud" <mm (AT) gdzid (DOT) com> wrote in news:VUb1c.13844$qA2.646611 @news20.bellglobal.com: Dans news:Xns94A122871E1C9zoubidamanhotmailcom (AT) 212 (DOT) 27.42.67, Michaël Delva <zoubidaman (AT) hotmail (DOT) com> a écrit : 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... Ce n'est pas une opération comparée à trois opérations. Dans les deux cas, tu as N insertions. Or, une insertion dans un set est bien plus chère qu'une insertion dans un vector. D'une part, l'insertion dans le vector est O(1), l'insertion dans un set O(ln N). Mais j'imagine que la plupart du temps, c'est plutôt la différence dans les constantes qui va faire la différence -- dans le cas de vector, la plupart du temps, une insertion n'est que l'incrémentation d'un pointeur et la copie de l'objet, tandis que dans le cas de set, il y a une allocation dynamique de la mémoire à chaque coup. Sur une machine moderne, la localité joue aussi un rôle -- le fait que les éléments dans un set sont éparpillés partout dans la mémoire risque d'augmenter les cache misses, voir les page faults. Alors, toutes ces différences fait que dans les faits, on risque de gagner assez sur les insertions pour pouvoir se payer un coup de sort, unique et erase. Au moins que la copie et l'échange (swap) des éléments soit très, très cher. Quote: Comme quoi... Comme quoi, il n'y a que les mésures qui diront la vérité. Mais à mon avis, ce n'est pas la peine de faire tant de travail (pour faire les mésures, etc.) avant de savoir si tu as un problème. J'utiliserai probablement set, simplement parce que ça me donne le résultat voulu « automatiquement », sans que je me soucis des opérations supplémentaires à la fin. -- James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16 Back to top Michaël Delva Guest Posted: Thu Mar 04, 2004 9:27 am    Post subject: Re: Version la plus rapide "Michel Michaud" <mm (AT) gdzid (DOT) com> wrote in news:Pkv1c.16646$qA2.873990 @news20.bellglobal.com: Quote: Quicksort est vraiment étonnamment rapide (toute proportion gardée). Si l'insertion dans un arbre balancé (ce qu'est normalement un std::set) était si rapide, on s'en servirait plutôt que les algorithmes de tri courants : on s'en sert parfois, mais pas pour trier des données ordinaires en mémoire. Il ne faut pas oublier tout ce qu'il faut faire pour maintenir un arbre. Et un arbre balancé, c'est pire. D'autres ont continué la discussion sur cet aspect. Je voulais simplement ajouter dire que la méthode la plus rapide, s'il s'agit simplement d'enlever les doublons, est probablement l'emploi d'une table de hachage. Je me demande d'ailleurs si, dans peu de temps, tu ne serais pas revenu avec une question sur la recherche dans ton vecteur. Ne pas oublier que dans un vecteur trié la recherche (binaire) est O(log N), alors que dans une table de hachage, on peut avoir O(1) ! Le seul défaut avec la table de hachage, c'est que les données ne sont pas en ordre. Mais c'est bien moins souvent nécessaire qu'on peut le croire. Problème: je ne sais pas ce qu'est une table de hachage ;-) Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ (French) All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.