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:
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...
Dans news:Xns94A122871E1C9zoubidamanhotmailcom@212.27.42.67, 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 mm@gdzid.com
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/
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" wrote in news:VUb1c.13844$qA2.646611 @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!!
"Michel Michaud" <mm@gdzid.com> wrote in news:VUb1c.13844$qA2.646611
@news20.bellglobal.com:
Dans news:Xns94A122871E1C9zoubidamanhotmailcom@212.27.42.67, 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...
"Michel Michaud" wrote in news:VUb1c.13844$qA2.646611 @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
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.
-- ;-)
On 03 Mar 2004 12:28:32 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
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.
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
Fabien LE LEZ wrote in 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 <gramster@gramster.com> wrote in
news:m1gc4014plisvqu397mqskilceu2d4k09d@4ax.com:
On 03 Mar 2004 12:28:32 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
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?
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
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.
-- ;-)
On 03 Mar 2004 21:19:04 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
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.
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
Fabien LE LEZ wrote in 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
Fabien LE LEZ <gramster@gramster.com> wrote in
news:c8kc40dfpll0ltvpkvb0qd4i2bh1ags96f@4ax.com:
On 03 Mar 2004 21:19:04 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
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.
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
Michaël Delva wrote:
Fabien LE LEZ wrote in 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
Michaël Delva wrote:
Fabien LE LEZ <gramster@gramster.com> wrote in
news:m1gc4014plisvqu397mqskilceu2d4k09d@4ax.com:
On 03 Mar 2004 12:28:32 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
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).
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
Loïc Joly écrivait:
L'insertion dans un set est en O(N) Faire N insetions est donc en O(N log N)
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
Loïc Joly wrote in 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 <loic.actarus.joly@wanadoo.fr> wrote in
news:c25nkg$v9o$1@news-reader1.wanadoo.fr:
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).
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
Franck Branjonneau wrote:
Loïc Joly é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.