Re-bonjour,
Pour ceux qui sont en forme, une seconde question: malgré des recherches
et des essais, je ne comprends pas la différence entre partial_sort et
nth_element. Quelle est-elle ?
J'ai simplement constaté (sous VC++) que partial_sort était plus lente
que std::sort (???), contrairement à nth_element qui est un peu plus rapide.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
alexandre
"Aurelien Regat-Barrel" a écrit dans le message de news: 4433baa6$0$1877$
Re-bonjour, Pour ceux qui sont en forme, une seconde question: malgré des recherches et des essais, je ne comprends pas la différence entre partial_sort et nth_element. Quelle est-elle ?
J'ai simplement constaté (sous VC++) que partial_sort était plus lente que std::sort (???), contrairement à nth_element qui est un peu plus rapide.
partial_sort et sort peuvent chacune être plus rapide suivant les cas. Normalement partial_sort devrait être plus rapide que sort dans la plupart des cas nth_element est de complexité N, donc systématiquement plus rapide que sort (NlogN) nth_element ne trie pas la collection, mais garantit simplement que tous les élements précédant le nième lui soient inférieurs, et que tous ceux le suivant lui soient supérieurs... donc les éléments avant et après ne sont pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être produit par nth_element (avec n =3 par exemple)
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis jamais servi de nth_element. D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo, je suis preneur ;-)
Alexandre
"Aurelien Regat-Barrel" <nospam.aregatba@yahoo.fr> a écrit dans le message
de news: 4433baa6$0$1877$636a55ce@news.free.fr...
Re-bonjour,
Pour ceux qui sont en forme, une seconde question: malgré des recherches
et des essais, je ne comprends pas la différence entre partial_sort et
nth_element. Quelle est-elle ?
J'ai simplement constaté (sous VC++) que partial_sort était plus lente que
std::sort (???), contrairement à nth_element qui est un peu plus rapide.
partial_sort et sort peuvent chacune être plus rapide suivant les cas.
Normalement partial_sort devrait être plus rapide que sort dans la plupart
des cas
nth_element est de complexité N, donc systématiquement plus rapide que sort
(NlogN)
nth_element ne trie pas la collection, mais garantit simplement que tous les
élements précédant le nième lui soient inférieurs, et que tous ceux le
suivant lui soient supérieurs... donc les éléments avant et après ne sont
pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être produit par
nth_element (avec n =3 par exemple)
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis
jamais servi de nth_element.
D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo, je
suis preneur ;-)
"Aurelien Regat-Barrel" a écrit dans le message de news: 4433baa6$0$1877$
Re-bonjour, Pour ceux qui sont en forme, une seconde question: malgré des recherches et des essais, je ne comprends pas la différence entre partial_sort et nth_element. Quelle est-elle ?
J'ai simplement constaté (sous VC++) que partial_sort était plus lente que std::sort (???), contrairement à nth_element qui est un peu plus rapide.
partial_sort et sort peuvent chacune être plus rapide suivant les cas. Normalement partial_sort devrait être plus rapide que sort dans la plupart des cas nth_element est de complexité N, donc systématiquement plus rapide que sort (NlogN) nth_element ne trie pas la collection, mais garantit simplement que tous les élements précédant le nième lui soient inférieurs, et que tous ceux le suivant lui soient supérieurs... donc les éléments avant et après ne sont pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être produit par nth_element (avec n =3 par exemple)
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis jamais servi de nth_element. D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo, je suis preneur ;-)
Alexandre
Aurelien Regat-Barrel
nth_element ne trie pas la collection, mais garantit simplement que tous les élements précédant le nième lui soient inférieurs, et que tous ceux le suivant lui soient supérieurs... donc les éléments avant et après ne sont pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être produit par nth_element (avec n =3 par exemple)
Ah d'accord. En testant j'ai constaté que les éléments précédents étaient triés, mais c'est juste un coup de chance si j'ai bien compris.
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis jamais servi de nth_element. D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo, je suis preneur ;-)
Je m'en sert pour calculer la valeur médiane d'un échantillon
Merci.
-- Aurélien Regat-Barrel
nth_element ne trie pas la collection, mais garantit simplement que tous les
élements précédant le nième lui soient inférieurs, et que tous ceux le
suivant lui soient supérieurs... donc les éléments avant et après ne sont
pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être produit par
nth_element (avec n =3 par exemple)
Ah d'accord. En testant j'ai constaté que les éléments précédents
étaient triés, mais c'est juste un coup de chance si j'ai bien compris.
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis
jamais servi de nth_element.
D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo, je
suis preneur ;-)
Je m'en sert pour calculer la valeur médiane d'un échantillon
nth_element ne trie pas la collection, mais garantit simplement que tous les élements précédant le nième lui soient inférieurs, et que tous ceux le suivant lui soient supérieurs... donc les éléments avant et après ne sont pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être produit par nth_element (avec n =3 par exemple)
Ah d'accord. En testant j'ai constaté que les éléments précédents étaient triés, mais c'est juste un coup de chance si j'ai bien compris.
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis jamais servi de nth_element. D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo, je suis preneur ;-)
Je m'en sert pour calculer la valeur médiane d'un échantillon
Merci.
-- Aurélien Regat-Barrel
alexandre
"Aurelien Regat-Barrel" a écrit dans le message de news: 4433c59b$0$2632$
nth_element ne trie pas la collection, mais garantit simplement que tous les élements précédant le nième lui soient inférieurs, et que tous ceux le suivant lui soient supérieurs... donc les éléments avant et après ne sont pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être produit par nth_element (avec n =3 par exemple)
Ah d'accord. En testant j'ai constaté que les éléments précédents étaient triés, mais c'est juste un coup de chance si j'ai bien compris.
il me semble, oui. Toujours uniquement d'après la lecture de la doc que j'ai (celle qui est livrée avec C++ Builder)
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis jamais servi de nth_element. D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo, je suis preneur ;-)
Je m'en sert pour calculer la valeur médiane d'un échantillon
ok, je vois. Je ne fais jamais de stats alors ça ne m'était pas venu à l'esprit ;-)
Merci.
-- Aurélien Regat-Barrel
"Aurelien Regat-Barrel" <nospam.aregatba@yahoo.fr> a écrit dans le message
de news: 4433c59b$0$2632$636a55ce@news.free.fr...
nth_element ne trie pas la collection, mais garantit simplement que tous
les élements précédant le nième lui soient inférieurs, et que tous ceux
le suivant lui soient supérieurs... donc les éléments avant et après ne
sont pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être
produit par nth_element (avec n =3 par exemple)
Ah d'accord. En testant j'ai constaté que les éléments précédents étaient
triés, mais c'est juste un coup de chance si j'ai bien compris.
il me semble, oui. Toujours uniquement d'après la lecture de la doc que j'ai
(celle qui est livrée avec C++ Builder)
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis
jamais servi de nth_element.
D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo,
je suis preneur ;-)
Je m'en sert pour calculer la valeur médiane d'un échantillon
ok, je vois. Je ne fais jamais de stats alors ça ne m'était pas venu à
l'esprit ;-)
"Aurelien Regat-Barrel" a écrit dans le message de news: 4433c59b$0$2632$
nth_element ne trie pas la collection, mais garantit simplement que tous les élements précédant le nième lui soient inférieurs, et que tous ceux le suivant lui soient supérieurs... donc les éléments avant et après ne sont pas forcément triés... 4 12 1 20 30 23 50 par exemple peut être produit par nth_element (avec n =3 par exemple)
Ah d'accord. En testant j'ai constaté que les éléments précédents étaient triés, mais c'est juste un coup de chance si j'ai bien compris.
il me semble, oui. Toujours uniquement d'après la lecture de la doc que j'ai (celle qui est livrée avec C++ Builder)
enfin si j'ai bien compris la lecture de la doc, parce que je ne me suis jamais servi de nth_element. D'ailleurs si quelqu'un a un exemple d'utilisation pratique de cet algo, je suis preneur ;-)
Je m'en sert pour calculer la valeur médiane d'un échantillon
ok, je vois. Je ne fais jamais de stats alors ça ne m'était pas venu à l'esprit ;-)
