Est-on toujours obligé de trier un container pour pouvoir enlever les doublons??
Obligé, non... mais t'as intérêt à prévoir un film pour attendre la fin du processus.
--
Français *==> "Musique renaissance" <==* English midi - facsimiles - ligatures - mensuration http://anaigeon.free.fr | http://www.medieval.org/emfaq/anaigeon/ Alain Naigeon - - Strasbourg, France
James Kanze
"Michaël Delva" writes:
|> Est-on toujours obligé de trier un container pour pouvoir enlever |> les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)).
-- James Kanze mailto: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
"Michaël Delva" <zoubidaman@hotmail.com> writes:
|> Est-on toujours obligé de trier un container pour pouvoir enlever
|> les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2)
à la place de O(n ln n)).
--
James Kanze mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
|> Est-on toujours obligé de trier un container pour pouvoir enlever |> les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)).
-- James Kanze mailto: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
Michaël Delva
James Kanze wrote in news::
"Michaël Delva" writes:
|> Est-on toujours obligé de trier un container pour pouvoir enlever |> les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de rapidité :-(
Comment calcules-tu ça? Quel serait l'ordre de rapidité décroissant?
James Kanze <kanze@alex.gabi-soft.fr> wrote in
news:86n09c6j0y.fsf@alex.gabi-soft.fr:
"Michaël Delva" <zoubidaman@hotmail.com> writes:
|> Est-on toujours obligé de trier un container pour pouvoir enlever
|> les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2)
à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de
rapidité :-(
Comment calcules-tu ça?
Quel serait l'ordre de rapidité décroissant?
|> Est-on toujours obligé de trier un container pour pouvoir enlever |> les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de rapidité :-(
Comment calcules-tu ça? Quel serait l'ordre de rapidité décroissant?
Fabien LE LEZ
On 29 Dec 2003 10:19:26 GMT, "Michaël Delva" wrote:
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de rapidité :-(
O(n^2) est très proche de k*n^2 (k étant une constante) quand n est très grand (Plus précisément, O(n^2)/n^2 tend vers une constante k quand n tend vers l'infini). En gros, la durée de calcul pour un algorithme en O(n^2) augmentera très rapidement quand n (le nombre d'éléments) grandit, tandis qu'un algorithme en O(n*ln(n)) augmentera moins vite :
n n^2 n*ln(n) 10 100 23 100 10000 460 1000 1 million 6907 10000 100 millions 92103
Le problème, c'est que la constante n'est pas partout la même. Le temps de calcul d'un algorithme en O(n^2) peut très bien être 2*n^2, tandis que le temps de calcul d'un algo en O(n*ln(n)) peut être 40*n*ln(n). Du coup, pour des petites valeurs de n le premier se révèle plus rapide :
b 2*n^2 40*n*ln(n) 10 200 920 100 20000 18400 1000 2 millions 276280
... Mais dès que n prend des valeurs plus importantes, le deuxième devient meilleur.
En gros, ln(n) est proportionnel au nombre de chiffres de n. C'est donc vite beaucoup plus petit que n.
Comment calcules-tu ça?
Pour trouver les doublons sans tri préalable, il faut comparer chacun des n éléments avec chacun des n-1 autres éléments. Il faut donc effectuer n*(n-1) comparaisons. Le "-1" étant négligeable devant le n, on peut dire qu'on fait à peu près n^2 comparaisons, i.e. que le temps de calcul est à peu près proportionnel à n^2 : O(n^2).
-- ;-)
On 29 Dec 2003 10:19:26 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
wrote:
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2)
à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de
rapidité :-(
O(n^2) est très proche de k*n^2 (k étant une constante) quand n est
très grand (Plus précisément, O(n^2)/n^2 tend vers une constante k
quand n tend vers l'infini).
En gros, la durée de calcul pour un algorithme en O(n^2) augmentera
très rapidement quand n (le nombre d'éléments) grandit, tandis qu'un
algorithme en O(n*ln(n)) augmentera moins vite :
n n^2 n*ln(n)
10 100 23
100 10000 460
1000 1 million 6907
10000 100 millions 92103
Le problème, c'est que la constante n'est pas partout la même. Le
temps de calcul d'un algorithme en O(n^2) peut très bien être 2*n^2,
tandis que le temps de calcul d'un algo en O(n*ln(n)) peut être
40*n*ln(n). Du coup, pour des petites valeurs de n le premier se
révèle plus rapide :
b 2*n^2 40*n*ln(n)
10 200 920
100 20000 18400
1000 2 millions 276280
... Mais dès que n prend des valeurs plus importantes, le deuxième
devient meilleur.
En gros, ln(n) est proportionnel au nombre de chiffres de n. C'est
donc vite beaucoup plus petit que n.
Comment calcules-tu ça?
Pour trouver les doublons sans tri préalable, il faut comparer chacun
des n éléments avec chacun des n-1 autres éléments. Il faut donc
effectuer n*(n-1) comparaisons. Le "-1" étant négligeable devant le n,
on peut dire qu'on fait à peu près n^2 comparaisons, i.e. que le temps
de calcul est à peu près proportionnel à n^2 : O(n^2).
On 29 Dec 2003 10:19:26 GMT, "Michaël Delva" wrote:
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de rapidité :-(
O(n^2) est très proche de k*n^2 (k étant une constante) quand n est très grand (Plus précisément, O(n^2)/n^2 tend vers une constante k quand n tend vers l'infini). En gros, la durée de calcul pour un algorithme en O(n^2) augmentera très rapidement quand n (le nombre d'éléments) grandit, tandis qu'un algorithme en O(n*ln(n)) augmentera moins vite :
n n^2 n*ln(n) 10 100 23 100 10000 460 1000 1 million 6907 10000 100 millions 92103
Le problème, c'est que la constante n'est pas partout la même. Le temps de calcul d'un algorithme en O(n^2) peut très bien être 2*n^2, tandis que le temps de calcul d'un algo en O(n*ln(n)) peut être 40*n*ln(n). Du coup, pour des petites valeurs de n le premier se révèle plus rapide :
b 2*n^2 40*n*ln(n) 10 200 920 100 20000 18400 1000 2 millions 276280
... Mais dès que n prend des valeurs plus importantes, le deuxième devient meilleur.
En gros, ln(n) est proportionnel au nombre de chiffres de n. C'est donc vite beaucoup plus petit que n.
Comment calcules-tu ça?
Pour trouver les doublons sans tri préalable, il faut comparer chacun des n éléments avec chacun des n-1 autres éléments. Il faut donc effectuer n*(n-1) comparaisons. Le "-1" étant négligeable devant le n, on peut dire qu'on fait à peu près n^2 comparaisons, i.e. que le temps de calcul est à peu près proportionnel à n^2 : O(n^2).
-- ;-)
Michaël Delva
Fabien LE LEZ wrote in news::
On 29 Dec 2003 10:19:26 GMT, "Michaël Delva" wrote:
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de rapidité :-(
O(n^2) est très proche de k*n^2 (k étant une constante) quand n est très grand (Plus précisément, O(n^2)/n^2 tend vers une constante k quand n tend vers l'infini). En gros, la durée de calcul pour un algorithme en O(n^2) augmentera très rapidement quand n (le nombre d'éléments) grandit, tandis qu'un algorithme en O(n*ln(n)) augmentera moins vite :
n n^2 n*ln(n) 10 100 23 100 10000 460 1000 1 million 6907 10000 100 millions 92103
Le problème, c'est que la constante n'est pas partout la même. Le temps de calcul d'un algorithme en O(n^2) peut très bien être 2*n^2, tandis que le temps de calcul d'un algo en O(n*ln(n)) peut être 40*n*ln(n). Du coup, pour des petites valeurs de n le premier se révèle plus rapide :
b 2*n^2 40*n*ln(n) 10 200 920 100 20000 18400 1000 2 millions 276280
... Mais dès que n prend des valeurs plus importantes, le deuxième devient meilleur.
En gros, ln(n) est proportionnel au nombre de chiffres de n. C'est donc vite beaucoup plus petit que n.
Comment calcules-tu ça?
Pour trouver les doublons sans tri préalable, il faut comparer chacun des n éléments avec chacun des n-1 autres éléments. Il faut donc effectuer n*(n-1) comparaisons. Le "-1" étant négligeable devant le n, on peut dire qu'on fait à peu près n^2 comparaisons, i.e. que le temps de calcul est à peu près proportionnel à n^2 : O(n^2).
Très constructif...
J'ai tout compris, merci!!
Fabien LE LEZ <gramster@gramster.com> wrote in
news:bi50vvc6vtr1hhhb8813vsfe0v6lnscgnn@4ax.com:
On 29 Dec 2003 10:19:26 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
wrote:
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2)
à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de
rapidité :-(
O(n^2) est très proche de k*n^2 (k étant une constante) quand n est
très grand (Plus précisément, O(n^2)/n^2 tend vers une constante k
quand n tend vers l'infini).
En gros, la durée de calcul pour un algorithme en O(n^2) augmentera
très rapidement quand n (le nombre d'éléments) grandit, tandis qu'un
algorithme en O(n*ln(n)) augmentera moins vite :
n n^2 n*ln(n)
10 100 23
100 10000 460
1000 1 million 6907
10000 100 millions 92103
Le problème, c'est que la constante n'est pas partout la même. Le
temps de calcul d'un algorithme en O(n^2) peut très bien être 2*n^2,
tandis que le temps de calcul d'un algo en O(n*ln(n)) peut être
40*n*ln(n). Du coup, pour des petites valeurs de n le premier se
révèle plus rapide :
b 2*n^2 40*n*ln(n)
10 200 920
100 20000 18400
1000 2 millions 276280
... Mais dès que n prend des valeurs plus importantes, le deuxième
devient meilleur.
En gros, ln(n) est proportionnel au nombre de chiffres de n. C'est
donc vite beaucoup plus petit que n.
Comment calcules-tu ça?
Pour trouver les doublons sans tri préalable, il faut comparer chacun
des n éléments avec chacun des n-1 autres éléments. Il faut donc
effectuer n*(n-1) comparaisons. Le "-1" étant négligeable devant le n,
on peut dire qu'on fait à peu près n^2 comparaisons, i.e. que le temps
de calcul est à peu près proportionnel à n^2 : O(n^2).
On 29 Dec 2003 10:19:26 GMT, "Michaël Delva" wrote:
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)).
Tiens, puisque tu en parles, je n'ai jamais compris ces formules de rapidité :-(
O(n^2) est très proche de k*n^2 (k étant une constante) quand n est très grand (Plus précisément, O(n^2)/n^2 tend vers une constante k quand n tend vers l'infini). En gros, la durée de calcul pour un algorithme en O(n^2) augmentera très rapidement quand n (le nombre d'éléments) grandit, tandis qu'un algorithme en O(n*ln(n)) augmentera moins vite :
n n^2 n*ln(n) 10 100 23 100 10000 460 1000 1 million 6907 10000 100 millions 92103
Le problème, c'est que la constante n'est pas partout la même. Le temps de calcul d'un algorithme en O(n^2) peut très bien être 2*n^2, tandis que le temps de calcul d'un algo en O(n*ln(n)) peut être 40*n*ln(n). Du coup, pour des petites valeurs de n le premier se révèle plus rapide :
b 2*n^2 40*n*ln(n) 10 200 920 100 20000 18400 1000 2 millions 276280
... Mais dès que n prend des valeurs plus importantes, le deuxième devient meilleur.
En gros, ln(n) est proportionnel au nombre de chiffres de n. C'est donc vite beaucoup plus petit que n.
Comment calcules-tu ça?
Pour trouver les doublons sans tri préalable, il faut comparer chacun des n éléments avec chacun des n-1 autres éléments. Il faut donc effectuer n*(n-1) comparaisons. Le "-1" étant négligeable devant le n, on peut dire qu'on fait à peu près n^2 comparaisons, i.e. que le temps de calcul est à peu près proportionnel à n^2 : O(n^2).
Très constructif...
J'ai tout compris, merci!!
Fabien LE LEZ
On 29 Dec 2003 13:27:19 GMT, "Michaël Delva" wrote:
J'ai tout compris, merci!!
Mais c'est pas la peine de recopier l'intégralité de mon message pour rajouter une ligne ou deux... :-(
-- ;-)
On 29 Dec 2003 13:27:19 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
wrote:
J'ai tout compris, merci!!
Mais c'est pas la peine de recopier l'intégralité de mon message pour
rajouter une ligne ou deux... :-(
On 29 Dec 2003 13:27:19 GMT, "Michaël Delva" wrote:
J'ai tout compris, merci!!
Mais c'est pas la peine de recopier l'intégralité de mon message pour rajouter une ligne ou deux... :-(
-- ;-)
Christophe Lephay
Michaël Delva wrote:
James Kanze wrote in news::
"Michaël Delva" writes:
Est-on toujours obligé de trier un container pour pouvoir enlever les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)). Quel serait l'ordre de rapidité décroissant?
Croissant ou décroissant, la vitesse est la même. Ce qui compte, c'est que les doublons soient consécutifs dans ton container pour limiter le nombre de recherches...
Chris
Michaël Delva wrote:
James Kanze <kanze@alex.gabi-soft.fr> wrote in
news:86n09c6j0y.fsf@alex.gabi-soft.fr:
"Michaël Delva" <zoubidaman@hotmail.com> writes:
Est-on toujours obligé de trier un container pour pouvoir enlever
les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2)
à la place de O(n ln n)).
Quel serait l'ordre de rapidité décroissant?
Croissant ou décroissant, la vitesse est la même. Ce qui compte, c'est que
les doublons soient consécutifs dans ton container pour limiter le nombre de
recherches...
Est-on toujours obligé de trier un container pour pouvoir enlever les doublons??
Non, mais les alternatifs ne sont pas forcement très rapide (O(n^2) à la place de O(n ln n)). Quel serait l'ordre de rapidité décroissant?
Croissant ou décroissant, la vitesse est la même. Ce qui compte, c'est que les doublons soient consécutifs dans ton container pour limiter le nombre de recherches...
Chris
Fabien LE LEZ
On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" wrote:
Est-on toujours obligé de trier un container pour pouvoir enlever les doublons?
Ch'tite remarque en passant : tu peux copier tous les éléments, un par un, dans un std::set<>. A chaque fois, avant insertion tu vérifies si l'élément est déjà dans le set<> ou pas, ce qui t'indique si c'est un doublon. Cette technique me semble plus lente que la technique habituelle (par tri), mais sans doute plus rapide que de faire n^2 comparaisons.
-- ;-)
On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
wrote:
Est-on toujours obligé de trier un container pour pouvoir enlever les
doublons?
Ch'tite remarque en passant : tu peux copier tous les éléments, un par
un, dans un std::set<>. A chaque fois, avant insertion tu vérifies si
l'élément est déjà dans le set<> ou pas, ce qui t'indique si c'est un
doublon. Cette technique me semble plus lente que la technique
habituelle (par tri), mais sans doute plus rapide que de faire n^2
comparaisons.
On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" wrote:
Est-on toujours obligé de trier un container pour pouvoir enlever les doublons?
Ch'tite remarque en passant : tu peux copier tous les éléments, un par un, dans un std::set<>. A chaque fois, avant insertion tu vérifies si l'élément est déjà dans le set<> ou pas, ce qui t'indique si c'est un doublon. Cette technique me semble plus lente que la technique habituelle (par tri), mais sans doute plus rapide que de faire n^2 comparaisons.
-- ;-)
Fabien LE LEZ
On Mon, 29 Dec 2003 13:08:06 +0100, Fabien LE LEZ wrote:
Pour trouver les doublons sans tri préalable, il faut comparer chacun des n éléments avec chacun des n-1 autres éléments.
En fait, non : on comparerait deux fois chaque couple. On fait en fait deux fois moins de comparaisons, mais le résultat reste le même : O(n^2).
-- ;-)
On Mon, 29 Dec 2003 13:08:06 +0100, Fabien LE LEZ
<gramster@gramster.com> wrote:
Pour trouver les doublons sans tri préalable, il faut comparer chacun
des n éléments avec chacun des n-1 autres éléments.
En fait, non : on comparerait deux fois chaque couple. On fait en fait
deux fois moins de comparaisons, mais le résultat reste le même :
O(n^2).
On Mon, 29 Dec 2003 13:08:06 +0100, Fabien LE LEZ wrote:
Pour trouver les doublons sans tri préalable, il faut comparer chacun des n éléments avec chacun des n-1 autres éléments.
En fait, non : on comparerait deux fois chaque couple. On fait en fait deux fois moins de comparaisons, mais le résultat reste le même : O(n^2).
-- ;-)
James Kanze
Fabien LE LEZ writes:
|> On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" |> wrote:
|> >Est-on toujours obligé de trier un container pour pouvoir |> >enlever les doublons?
|> Ch'tite remarque en passant : tu peux copier tous les |> éléments, un par un, dans un std::set<>. A chaque fois, avant |> insertion tu vérifies si l'élément est déjà dans le |> set<> ou pas, ce qui t'indique si c'est un doublon.
Même pas nécessaire. Un set n'accepte pas de doublons, et set<>::insert fait ce qu'il faut pour qu'il n'y en ait pas.
|> Cette technique me semble plus lente que la technique habituelle |> (par tri), mais sans doute plus rapide que de faire n^2 |> comparaisons.
J'imagine aussi que c'est moins rapide, mais à une constante près. C'est toujours O(n ln n).
Avec un bon hachage, utiliser hash_set pourrait être O(n).
-- James Kanze mailto: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
Fabien LE LEZ <gramster@gramster.com> writes:
|> On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" <zoubidaman@hotmail.com>
|> wrote:
|> >Est-on toujours obligé de trier un container pour pouvoir
|> >enlever les doublons?
|> Ch'tite remarque en passant : tu peux copier tous les
|> éléments, un par un, dans un std::set<>. A chaque fois, avant
|> insertion tu vérifies si l'élément est déjà dans le
|> set<> ou pas, ce qui t'indique si c'est un doublon.
Même pas nécessaire. Un set n'accepte pas de doublons, et
set<>::insert fait ce qu'il faut pour qu'il n'y en ait pas.
|> Cette technique me semble plus lente que la technique habituelle
|> (par tri), mais sans doute plus rapide que de faire n^2
|> comparaisons.
J'imagine aussi que c'est moins rapide, mais à une constante près.
C'est toujours O(n ln n).
Avec un bon hachage, utiliser hash_set pourrait être O(n).
--
James Kanze mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
|> On 28 Dec 2003 15:24:17 GMT, "Michaël Delva" |> wrote:
|> >Est-on toujours obligé de trier un container pour pouvoir |> >enlever les doublons?
|> Ch'tite remarque en passant : tu peux copier tous les |> éléments, un par un, dans un std::set<>. A chaque fois, avant |> insertion tu vérifies si l'élément est déjà dans le |> set<> ou pas, ce qui t'indique si c'est un doublon.
Même pas nécessaire. Un set n'accepte pas de doublons, et set<>::insert fait ce qu'il faut pour qu'il n'y en ait pas.
|> Cette technique me semble plus lente que la technique habituelle |> (par tri), mais sans doute plus rapide que de faire n^2 |> comparaisons.
J'imagine aussi que c'est moins rapide, mais à une constante près. C'est toujours O(n ln n).
Avec un bon hachage, utiliser hash_set pourrait être O(n).
-- James Kanze mailto: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France +33 1 41 89 80 93
