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:
On 03 Mar 2004 21:51:52 GMT, "Michaël Delva" wrote:
Bon ben merci
De rien, Mich ;-)
-- ;-)
Michel Michaud
Dans news:, Michaël
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 http://www.gdzid.com FAQ de fr.comp.lang.c++ : http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/
Dans news:Xns94A189195464Azoubidamanhotmailcom@212.27.42.67, Michaël
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 mm@gdzid.com
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/
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 http://www.gdzid.com FAQ de fr.comp.lang.c++ : http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/
kanze
"Michaël Delva" wrote in message news:...
"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...
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.
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: 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
"Michaël Delva" <zoubidaman@hotmail.com> wrote in message
news:<Xns94A189195464Azoubidamanhotmailcom@212.27.42.67>...
"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...
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.
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@gabi-soft.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
"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...
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.
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: 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
Michaël Delva
"Michel Michaud" wrote in news:Pkv1c.16646$qA2.873990 @news20.bellglobal.com:
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 ;-)
"Michel Michaud" <mm@gdzid.com> wrote in news:Pkv1c.16646$qA2.873990
@news20.bellglobal.com:
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 ;-)
"Michel Michaud" wrote in news:Pkv1c.16646$qA2.873990 @news20.bellglobal.com:
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 ;-)
Michel Michaud
Dans news:, Michaël
Problème: je ne sais pas ce qu'est une table de hachage ;-)
Si tu ne sais pas ce qu'est une table de hachage alors je dirais sérieusement (sans t'insulter) que tu n'es pas assez compétent en général pour être à l'étape de te poser des questions de performance entre X et Y. Il y a très certainement des endroits de ton code où les différences entre ce que tu sais faire et ce que tu devrais faire seront bien plus importantes que les différences de vitesse en deux méthodes de même ordre...
-- Michel Michaud http://www.gdzid.com FAQ de fr.comp.lang.c++ : http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/
Dans news:Xns94A26A7ECDDF5zoubidamanhotmailcom@212.27.42.67, Michaël
Problème: je ne sais pas ce qu'est une table de hachage ;-)
Si tu ne sais pas ce qu'est une table de hachage alors je dirais
sérieusement (sans t'insulter) que tu n'es pas assez compétent
en général pour être à l'étape de te poser des questions de
performance entre X et Y. Il y a très certainement des endroits
de ton code où les différences entre ce que tu sais faire et ce
que tu devrais faire seront bien plus importantes que les
différences de vitesse en deux méthodes de même ordre...
--
Michel Michaud mm@gdzid.com
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/
Problème: je ne sais pas ce qu'est une table de hachage ;-)
Si tu ne sais pas ce qu'est une table de hachage alors je dirais sérieusement (sans t'insulter) que tu n'es pas assez compétent en général pour être à l'étape de te poser des questions de performance entre X et Y. Il y a très certainement des endroits de ton code où les différences entre ce que tu sais faire et ce que tu devrais faire seront bien plus importantes que les différences de vitesse en deux méthodes de même ordre...
-- Michel Michaud http://www.gdzid.com FAQ de fr.comp.lang.c++ : http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/
Michaël Delva
"Michel Michaud" wrote in news:nVD1c.16994$qA2.970139 @news20.bellglobal.com:
Dans news:, Michaël
Problème: je ne sais pas ce qu'est une table de hachage ;-)
Si tu ne sais pas ce qu'est une table de hachage alors je dirais sérieusement (sans t'insulter) que tu n'es pas assez compétent en général pour être à l'étape de te poser des questions de performance entre X et Y. Il y a très certainement des endroits de ton code où les différences entre ce que tu sais faire et ce que tu devrais faire seront bien plus importantes que les différences de vitesse en deux méthodes de même ordre...
Curieusement, c'est l'idée que je me suis faite tout au long de cette discussion... ;-) Et heureusement pour toi, sinon je l'aurai pris comme une insulte!! ;-)
"Michel Michaud" <mm@gdzid.com> wrote in news:nVD1c.16994$qA2.970139
@news20.bellglobal.com:
Dans news:Xns94A26A7ECDDF5zoubidamanhotmailcom@212.27.42.67, Michaël
Problème: je ne sais pas ce qu'est une table de hachage ;-)
Si tu ne sais pas ce qu'est une table de hachage alors je dirais
sérieusement (sans t'insulter) que tu n'es pas assez compétent
en général pour être à l'étape de te poser des questions de
performance entre X et Y. Il y a très certainement des endroits
de ton code où les différences entre ce que tu sais faire et ce
que tu devrais faire seront bien plus importantes que les
différences de vitesse en deux méthodes de même ordre...
Curieusement, c'est l'idée que je me suis faite tout au long de cette
discussion... ;-)
Et heureusement pour toi, sinon je l'aurai pris comme une insulte!! ;-)
"Michel Michaud" wrote in news:nVD1c.16994$qA2.970139 @news20.bellglobal.com:
Dans news:, Michaël
Problème: je ne sais pas ce qu'est une table de hachage ;-)
Si tu ne sais pas ce qu'est une table de hachage alors je dirais sérieusement (sans t'insulter) que tu n'es pas assez compétent en général pour être à l'étape de te poser des questions de performance entre X et Y. Il y a très certainement des endroits de ton code où les différences entre ce que tu sais faire et ce que tu devrais faire seront bien plus importantes que les différences de vitesse en deux méthodes de même ordre...
Curieusement, c'est l'idée que je me suis faite tout au long de cette discussion... ;-) Et heureusement pour toi, sinon je l'aurai pris comme une insulte!! ;-)
