Bonjour,
si je vous dit comme ça : "tableau de 240 000 entiers", que me répondez vous
?
a) Quoi ?! Mais vous êtes completement fou ! Votre processeur va fondre,
votre mémoire exploser, ça va tout crasher !
b) Ca peut marcher mais ce n'est pas trés élégant, surtout si c'est un
majorant et qu'il est trés probable que vous ne le remplissiez même pas au
quart...
c) Meuh non, c'est rien du tout ça ! C++ encaisse tout ça sans broncher, y'a
pas de problème ! Hier je suis monté jusqu'à 100 000 000 entiers sur mon 386
avec 2mo de Ram !
Bon, j'imagine que votre réponse se situera quelquepart entre (a) et (b).
Mon problème est de stocker des entiers dans une liste.
Je sais que je ne peux pas avoir plus de 240 000 mais je ais aussi que j'en
aurai beaucoup moins dans la majorité des cas.
Alors : que faire ?
La taille des éléments ajoutés ne sera connue qu'à la fin de l'exécution de
mon algorithme.
Il me semble qu'il est impossible de faire varier la taille du tableau en
cours de route ?
A moins de creer à chaque itération un nouveau tableau de taille n+1 et de
recopier l'ancien tableaude taille n pusi de le supprimer ?
Qu'en pensez vous ?
Ou alors faire tourner une première fois l'algorithme pour connaître la
taille du tableau puis le relancer en ayant entre temps crée un tableau avec
pile la bonne taille ? Mais ca me semble pas trés élégant...
Bonjour, si je vous dit comme ça : "tableau de 240 000 entiers", que me répo ndez vous ?
a) Quoi ?! Mais vous êtes completement fou ! Votre processeur va fond re, votre mémoire exploser, ça va tout crasher !
Pas du tout, surtout des entiers, c'est 4 octets l'entier, et donc ton tableau te prend 960 Ko, c'est pas ça qui va faire craquer ton proc ! Tout dépend de la mémoire que tu as, 512 Mo semble un minimum quand o n veut faire des choses sérieuses
b) Ca peut marcher mais ce n'est pas trés élégant, surtout si c'e st un majorant et qu'il est trés probable que vous ne le remplissiez même pas au quart...
La technique j'alloue un tableau de 2 Go n'est pas élégante, c'est certain, mais il valait mieux parler de 240 millions de flottants dans ce cas :-p
c) Meuh non, c'est rien du tout ça ! C++ encaisse tout ça sans bron cher, y'a pas de problème ! Hier je suis monté jusqu'à 100 000 000 entiers sur mon 386 avec 2mo de Ram !
100 millions, c'est utopiste avec si peu de ram a moins que tu n'aies une partition swap de 500 Mo. Laisse ton 386 a la poubelle, ça ira mieu x pour tout le monde !
Il me semble qu'il est impossible de faire varier la taille du tableau en cours de route ?
Vi, si tu prends une structure c++ du style une liste chainee (list par exemple), en revanche les algos que tu veux faire tourner dessus seront plus lents car les blocs de mémoire ne seront plus contigus.
A moins de creer à chaque itération un nouveau tableau de taille n+ 1 et de recopier l'ancien tableaude taille n pusi de le supprimer ? Qu'en pensez vous ?
Non, a proscrire
Ou alors faire tourner une première fois l'algorithme pour connaîtr e la taille du tableau puis le relancer en ayant entre temps crée un table au avec pile la bonne taille ? Mais ca me semble pas trés élégant...
Vi c'est bien ça, ou faire une estimation a priori de la taille de ton
tableau, un majorant tu vois. Et c'est bien plus élégant que tout ce que tu as dit auparavant !
Rincevent wrote:
Bonjour,
si je vous dit comme ça : "tableau de 240 000 entiers", que me répo ndez vous
?
a) Quoi ?! Mais vous êtes completement fou ! Votre processeur va fond re,
votre mémoire exploser, ça va tout crasher !
Pas du tout, surtout des entiers, c'est 4 octets l'entier, et donc ton
tableau te prend 960 Ko, c'est pas ça qui va faire craquer ton proc !
Tout dépend de la mémoire que tu as, 512 Mo semble un minimum quand o n
veut faire des choses sérieuses
b) Ca peut marcher mais ce n'est pas trés élégant, surtout si c'e st un
majorant et qu'il est trés probable que vous ne le remplissiez même pas au
quart...
La technique j'alloue un tableau de 2 Go n'est pas élégante, c'est
certain, mais il valait mieux parler de 240 millions de flottants dans
ce cas :-p
c) Meuh non, c'est rien du tout ça ! C++ encaisse tout ça sans bron cher, y'a
pas de problème ! Hier je suis monté jusqu'à 100 000 000 entiers sur mon 386
avec 2mo de Ram !
100 millions, c'est utopiste avec si peu de ram a moins que tu n'aies
une partition swap de 500 Mo. Laisse ton 386 a la poubelle, ça ira mieu x
pour tout le monde !
Il me semble qu'il est impossible de faire varier la taille du tableau en
cours de route ?
Vi, si tu prends une structure c++ du style une liste chainee (list par
exemple), en revanche les algos que tu veux faire tourner dessus seront
plus lents car les blocs de mémoire ne seront plus contigus.
A moins de creer à chaque itération un nouveau tableau de taille n+ 1 et de
recopier l'ancien tableaude taille n pusi de le supprimer ?
Qu'en pensez vous ?
Non, a proscrire
Ou alors faire tourner une première fois l'algorithme pour connaîtr e la
taille du tableau puis le relancer en ayant entre temps crée un table au avec
pile la bonne taille ? Mais ca me semble pas trés élégant...
Vi c'est bien ça, ou faire une estimation a priori de la taille de ton
tableau, un majorant tu vois. Et c'est bien plus élégant que tout ce que
tu as dit auparavant !
Bonjour, si je vous dit comme ça : "tableau de 240 000 entiers", que me répo ndez vous ?
a) Quoi ?! Mais vous êtes completement fou ! Votre processeur va fond re, votre mémoire exploser, ça va tout crasher !
Pas du tout, surtout des entiers, c'est 4 octets l'entier, et donc ton tableau te prend 960 Ko, c'est pas ça qui va faire craquer ton proc ! Tout dépend de la mémoire que tu as, 512 Mo semble un minimum quand o n veut faire des choses sérieuses
b) Ca peut marcher mais ce n'est pas trés élégant, surtout si c'e st un majorant et qu'il est trés probable que vous ne le remplissiez même pas au quart...
La technique j'alloue un tableau de 2 Go n'est pas élégante, c'est certain, mais il valait mieux parler de 240 millions de flottants dans ce cas :-p
c) Meuh non, c'est rien du tout ça ! C++ encaisse tout ça sans bron cher, y'a pas de problème ! Hier je suis monté jusqu'à 100 000 000 entiers sur mon 386 avec 2mo de Ram !
100 millions, c'est utopiste avec si peu de ram a moins que tu n'aies une partition swap de 500 Mo. Laisse ton 386 a la poubelle, ça ira mieu x pour tout le monde !
Il me semble qu'il est impossible de faire varier la taille du tableau en cours de route ?
Vi, si tu prends une structure c++ du style une liste chainee (list par exemple), en revanche les algos que tu veux faire tourner dessus seront plus lents car les blocs de mémoire ne seront plus contigus.
A moins de creer à chaque itération un nouveau tableau de taille n+ 1 et de recopier l'ancien tableaude taille n pusi de le supprimer ? Qu'en pensez vous ?
Non, a proscrire
Ou alors faire tourner une première fois l'algorithme pour connaîtr e la taille du tableau puis le relancer en ayant entre temps crée un table au avec pile la bonne taille ? Mais ca me semble pas trés élégant...
Vi c'est bien ça, ou faire une estimation a priori de la taille de ton
tableau, un majorant tu vois. Et c'est bien plus élégant que tout ce que tu as dit auparavant !
Anthony Fleury
Rincevent wrote:
Bonjour,
Bonjour,
si je vous dit comme ça : "tableau de 240 000 entiers", que me répondez vous ?
b) Ca peut marcher mais ce n'est pas trés élégant, surtout si c'est un majorant et qu'il est trés probable que vous ne le remplissiez même pas au quart...
Je dirai b. Peut être que sur certains OS avec certaines architectures ca passera en variable automatique, mais ce n'est pas assuré. À ma connaissance le C définit une taille maximale pour les objets automatiques (64 kB en C99 et 32 en C90) au dessus le comportement est indéfini ; donc ca _peut_ marcher. Pour ce qui est de 240 000 entiers, soit 937 kB (avec sizeof (int) == 4) d'après bc, c'est beaucoup trop. Et pour le C++ je ne sais pas si cette taille est définie mais le contraire m'étonnerait.
Je sais que je ne peux pas avoir plus de 240 000 mais je ais aussi que j'en aurai beaucoup moins dans la majorité des cas. Alors : que faire ? La taille des éléments ajoutés ne sera connue qu'à la fin de l'exécution de mon algorithme. [...]
A moins de creer à chaque itération un nouveau tableau de taille n+1 et de recopier l'ancien tableaude taille n pusi de le supprimer ? Qu'en pensez vous ?
C'est la méthode qui serait utilisée je pense. Une petite question, pourquoi ne pas utiliser un std::vector<> avec ses méthodes reserve(), push_back()... ? Si il est impossible de l'utiliser car c'est pour un exercice ou autre, refaire à peu près la même chose que ce que peut faire vector peut etre interessant. En effet, std::vector<> offre une fonction membre reserve qui augmente la taille de son tableau de n élements en réallouant et recopiant. C'est je pense la méthode normale, augmenter au fur et à mesure la taille, mais pas de 1 car ca serait une perte de temps totale, plutot l'augmenter de 100 à la fois par exemple parce que la copie augmente fortement le temps d'execution. Enfin le n dépend de l'algorithme. Donc ce que je ferai si je ne pouvais pas utiliser vector (et sans plus de détail sur l'algo), encapsuler le tableau dans une taille, ce tableau étant alloué dynamiquement, et réallouer si besoin, ou sur demande avec une fonction reservant n Bytes en mémoire.
Ou alors faire tourner une première fois l'algorithme pour connaître la taille du tableau puis le relancer en ayant entre temps crée un tableau avec pile la bonne taille ? Mais ca me semble pas trés élégant...
En effet, surtout si l'algorithme s'execute en 1 mois et demi ca peut ne pas être élégant.
Anthony -- "I should have seen it would be this way I should have known from the start what she's up to When you have loved and you've lost someone You know what it feels like to lose" -- The Rasmus
Rincevent wrote:
Bonjour,
Bonjour,
si je vous dit comme ça : "tableau de 240 000 entiers", que me répondez
vous ?
b) Ca peut marcher mais ce n'est pas trés élégant, surtout si c'est un
majorant et qu'il est trés probable que vous ne le remplissiez même pas au
quart...
Je dirai b. Peut être que sur certains OS avec certaines architectures ca
passera en variable automatique, mais ce n'est pas assuré. À ma
connaissance le C définit une taille maximale pour les objets automatiques
(64 kB en C99 et 32 en C90) au dessus le comportement est indéfini ; donc
ca _peut_ marcher. Pour ce qui est de 240 000 entiers, soit 937 kB (avec
sizeof (int) == 4) d'après bc, c'est beaucoup trop. Et pour le C++ je ne
sais pas si cette taille est définie mais le contraire m'étonnerait.
Je sais que je ne peux pas avoir plus de 240 000 mais je ais aussi que
j'en aurai beaucoup moins dans la majorité des cas.
Alors : que faire ?
La taille des éléments ajoutés ne sera connue qu'à la fin de l'exécution
de mon algorithme.
[...]
A moins de creer à chaque itération un nouveau tableau de taille n+1 et de
recopier l'ancien tableaude taille n pusi de le supprimer ?
Qu'en pensez vous ?
C'est la méthode qui serait utilisée je pense. Une petite question, pourquoi
ne pas utiliser un std::vector<> avec ses méthodes reserve(),
push_back()... ?
Si il est impossible de l'utiliser car c'est pour un exercice ou autre,
refaire à peu près la même chose que ce que peut faire vector peut etre
interessant. En effet, std::vector<> offre une fonction membre reserve qui
augmente la taille de son tableau de n élements en réallouant et recopiant.
C'est je pense la méthode normale, augmenter au fur et à mesure la taille,
mais pas de 1 car ca serait une perte de temps totale, plutot l'augmenter
de 100 à la fois par exemple parce que la copie augmente fortement le temps
d'execution. Enfin le n dépend de l'algorithme.
Donc ce que je ferai si je ne pouvais pas utiliser vector (et sans plus de
détail sur l'algo), encapsuler le tableau dans une taille, ce tableau étant
alloué dynamiquement, et réallouer si besoin, ou sur demande avec une
fonction reservant n Bytes en mémoire.
Ou alors faire tourner une première fois l'algorithme pour connaître la
taille du tableau puis le relancer en ayant entre temps crée un tableau
avec pile la bonne taille ? Mais ca me semble pas trés élégant...
En effet, surtout si l'algorithme s'execute en 1 mois et demi ca peut ne pas
être élégant.
Anthony
--
"I should have seen it would be this way
I should have known from the start what she's up to
When you have loved and you've lost someone
You know what it feels like to lose" -- The Rasmus
si je vous dit comme ça : "tableau de 240 000 entiers", que me répondez vous ?
b) Ca peut marcher mais ce n'est pas trés élégant, surtout si c'est un majorant et qu'il est trés probable que vous ne le remplissiez même pas au quart...
Je dirai b. Peut être que sur certains OS avec certaines architectures ca passera en variable automatique, mais ce n'est pas assuré. À ma connaissance le C définit une taille maximale pour les objets automatiques (64 kB en C99 et 32 en C90) au dessus le comportement est indéfini ; donc ca _peut_ marcher. Pour ce qui est de 240 000 entiers, soit 937 kB (avec sizeof (int) == 4) d'après bc, c'est beaucoup trop. Et pour le C++ je ne sais pas si cette taille est définie mais le contraire m'étonnerait.
Je sais que je ne peux pas avoir plus de 240 000 mais je ais aussi que j'en aurai beaucoup moins dans la majorité des cas. Alors : que faire ? La taille des éléments ajoutés ne sera connue qu'à la fin de l'exécution de mon algorithme. [...]
A moins de creer à chaque itération un nouveau tableau de taille n+1 et de recopier l'ancien tableaude taille n pusi de le supprimer ? Qu'en pensez vous ?
C'est la méthode qui serait utilisée je pense. Une petite question, pourquoi ne pas utiliser un std::vector<> avec ses méthodes reserve(), push_back()... ? Si il est impossible de l'utiliser car c'est pour un exercice ou autre, refaire à peu près la même chose que ce que peut faire vector peut etre interessant. En effet, std::vector<> offre une fonction membre reserve qui augmente la taille de son tableau de n élements en réallouant et recopiant. C'est je pense la méthode normale, augmenter au fur et à mesure la taille, mais pas de 1 car ca serait une perte de temps totale, plutot l'augmenter de 100 à la fois par exemple parce que la copie augmente fortement le temps d'execution. Enfin le n dépend de l'algorithme. Donc ce que je ferai si je ne pouvais pas utiliser vector (et sans plus de détail sur l'algo), encapsuler le tableau dans une taille, ce tableau étant alloué dynamiquement, et réallouer si besoin, ou sur demande avec une fonction reservant n Bytes en mémoire.
Ou alors faire tourner une première fois l'algorithme pour connaître la taille du tableau puis le relancer en ayant entre temps crée un tableau avec pile la bonne taille ? Mais ca me semble pas trés élégant...
En effet, surtout si l'algorithme s'execute en 1 mois et demi ca peut ne pas être élégant.
Anthony -- "I should have seen it would be this way I should have known from the start what she's up to When you have loved and you've lost someone You know what it feels like to lose" -- The Rasmus
Fabien LE LEZ
On Sun, 7 Mar 2004 15:58:00 +0100, "Rincevent" wrote:
Je sais que je ne peux pas avoir plus de 240 000 mais je ais aussi que j'en aurai beaucoup moins dans la majorité des cas. Alors : que faire ?
Typiquement, on laisse le std::vector<> vide au départ (avec éventuellement un reserve() sur une valeur "raisonnable"), et on le remplit au fur et à mesure. Eventuellement, on peut utiliser deque<> si on a peur des réallocations trop fréquentes.
-- ;-)
On Sun, 7 Mar 2004 15:58:00 +0100, "Rincevent" <pierre@nospam.net>
wrote:
Je sais que je ne peux pas avoir plus de 240 000 mais je ais aussi que j'en
aurai beaucoup moins dans la majorité des cas.
Alors : que faire ?
Typiquement, on laisse le std::vector<> vide au départ (avec
éventuellement un reserve() sur une valeur "raisonnable"), et on le
remplit au fur et à mesure.
Eventuellement, on peut utiliser deque<> si on a peur des
réallocations trop fréquentes.
On Sun, 7 Mar 2004 15:58:00 +0100, "Rincevent" wrote:
Je sais que je ne peux pas avoir plus de 240 000 mais je ais aussi que j'en aurai beaucoup moins dans la majorité des cas. Alors : que faire ?
Typiquement, on laisse le std::vector<> vide au départ (avec éventuellement un reserve() sur une valeur "raisonnable"), et on le remplit au fur et à mesure. Eventuellement, on peut utiliser deque<> si on a peur des réallocations trop fréquentes.
-- ;-)
Rincevent
"Rincevent" a écrit dans le message de news: c2fd9u$de1$
Bonjour, si je vous dit comme ça : "tableau de 240 000 entiers", que me répondez vous
?
Merci à tous pour vos réponses. Débutant en C++, on ne nous a jamais aprlé de l'objet "vector" en cours mais ça parait correspondre à mes besoins d'utilisation ! Je vais aller farfouiller ça sur le net. @++
Pierre
P.S : pour info, mon porgramme doit être capable de trouver des particules noires sur une image en N&B. Pour une matrice 800*600, un majorant de ces particules est 800*600/2 = 240 000 d'où l'origine de ma question ;-)
"Rincevent" <pierre@nospam.net> a écrit dans le message de news:
c2fd9u$de1$1@news-reader5.wanadoo.fr...
Bonjour,
si je vous dit comme ça : "tableau de 240 000 entiers", que me répondez
vous
?
Merci à tous pour vos réponses.
Débutant en C++, on ne nous a jamais aprlé de l'objet "vector" en cours mais
ça parait correspondre à mes besoins d'utilisation !
Je vais aller farfouiller ça sur le net.
@++
Pierre
P.S : pour info, mon porgramme doit être capable de trouver des particules
noires sur une image en N&B.
Pour une matrice 800*600, un majorant de ces particules est 800*600/2 = 240
000 d'où l'origine de ma question ;-)
"Rincevent" a écrit dans le message de news: c2fd9u$de1$
Bonjour, si je vous dit comme ça : "tableau de 240 000 entiers", que me répondez vous
?
Merci à tous pour vos réponses. Débutant en C++, on ne nous a jamais aprlé de l'objet "vector" en cours mais ça parait correspondre à mes besoins d'utilisation ! Je vais aller farfouiller ça sur le net. @++
Pierre
P.S : pour info, mon porgramme doit être capable de trouver des particules noires sur une image en N&B. Pour une matrice 800*600, un majorant de ces particules est 800*600/2 = 240 000 d'où l'origine de ma question ;-)
Fabien LE LEZ
On Sun, 7 Mar 2004 17:05:28 +0100, "Rincevent" wrote:
Débutant en C++, on ne nous a jamais aprlé de l'objet "vector" en cours
:-/ C'est pourtant bien plus souvent utile que les tableaux "à la C"... Si jamais tu n'as pas non plus entendu parler de std::string, jette un oeil sur un bon bouquin, ça aussi c'est relativement indispensable.
-- ;-)
On Sun, 7 Mar 2004 17:05:28 +0100, "Rincevent" <pierre@nospam.net>
wrote:
Débutant en C++, on ne nous a jamais aprlé de l'objet "vector" en cours
:-/
C'est pourtant bien plus souvent utile que les tableaux "à la C"...
Si jamais tu n'as pas non plus entendu parler de std::string, jette un
oeil sur un bon bouquin, ça aussi c'est relativement indispensable.
On Sun, 7 Mar 2004 17:05:28 +0100, "Rincevent" wrote:
Débutant en C++, on ne nous a jamais aprlé de l'objet "vector" en cours
:-/ C'est pourtant bien plus souvent utile que les tableaux "à la C"... Si jamais tu n'as pas non plus entendu parler de std::string, jette un oeil sur un bon bouquin, ça aussi c'est relativement indispensable.
-- ;-)
Samuel Krempp
le Sunday 07 March 2004 16:28, écrivit :
C'est la méthode qui serait utilisée je pense. Une petite question, pourquoi ne pas utiliser un std::vector<> avec ses méthodes reserve(), push_back()... ?
c'est aussi ce que je me demande, pourquoi ne pas utiliser un des containers STL ? selon comment ces éléments seront ensuite utilisé, et le rapport entre temps passé à remplir le container et temps passé à le parcourir, on peut envisager std::deque ou std::vector (à priori vaut mieux deque, qui aura presque pas d'overhead au remplissage un-par-un, et un très léger overhead au parcours)
la taille, mais pas de 1 car ca serait une perte de temps totale, plutot l'augmenter de 100 à la fois par exemple parce que la copie augmente
100 aussi finira par être une perte de temps. les algos des stdlib font grandir le container exponentiellement (genre x2 à chaque agrandissement, ou x1.5 ..) comme ça N appels à push_back sur un tableau vide avec multiplication de la taille par k à chaque fois occasionnera simplement log(N)/log(k) allocations et kN/(k-1) recopiages de valeurs par rapport à si le vecteur était alloué dès le début. (et aussi le vecteur final occupera plus de place que nécessaire, au pire k fois la place nécessaire) (1 + k + k^2 + k^3 + ... + k^p = (k * k^p - 1)/(k-1) recopiages avec pÎil(log(N)/log(k))-1 au pire N=1+k^p et ça fait (k(N-1)-1)/(k-1) recopiages)
pour k=2, ça fait au pire 2N recopiages de valeurs, et une taille finale au pire 2 fois trop grande. c'est pas cher payé pour le confort d'utilisation obtenu.
pour k=1.5 ça fait 3N recopiages, mais au final le vecteur prend au pire seulement 50% de place de plus que nécessaire.
Ou alors faire tourner une première fois l'algorithme pour connaître la taille du tableau puis le relancer en ayant entre temps crée un tableau avec pile la bonne taille ? Mais ca me semble pas trés élégant...
et puis probablement inutile pour si peu d'éléments. comme d'hab il faudrait mesurer (profiler) mais je pense pas que y ait de grande différence de temps d'éxécution entre deque et vector, ou encore un tableau à taille déterminée pour qques centaines de milliers d'entiers. selon les calculs nécessaires pour précalculer le nbre d'éléments, ça pourrait très bien ne même pas être rentable par rapport à utiliser push_back directement.
-- Sam
le Sunday 07 March 2004 16:28, fleury_anthony@hotmail_.com écrivit :
C'est la méthode qui serait utilisée je pense. Une petite question,
pourquoi ne pas utiliser un std::vector<> avec ses méthodes reserve(),
push_back()... ?
c'est aussi ce que je me demande, pourquoi ne pas utiliser un des containers
STL ? selon comment ces éléments seront ensuite utilisé, et le rapport
entre temps passé à remplir le container et temps passé à le parcourir, on
peut envisager std::deque ou std::vector (à priori vaut mieux deque, qui
aura presque pas d'overhead au remplissage un-par-un, et un très léger
overhead au parcours)
la taille, mais pas de 1 car ca serait une perte de temps totale, plutot
l'augmenter de 100 à la fois par exemple parce que la copie augmente
100 aussi finira par être une perte de temps. les algos des stdlib font
grandir le container exponentiellement (genre x2 à chaque agrandissement,
ou x1.5 ..)
comme ça N appels à push_back sur un tableau vide avec multiplication de la
taille par k à chaque fois occasionnera simplement log(N)/log(k)
allocations et kN/(k-1) recopiages de valeurs par rapport à si le vecteur
était alloué dès le début. (et aussi le vecteur final occupera plus de
place que nécessaire, au pire k fois la place nécessaire)
(1 + k + k^2 + k^3 + ... + k^p = (k * k^p - 1)/(k-1) recopiages avec
pÎil(log(N)/log(k))-1
au pire N=1+k^p et ça fait (k(N-1)-1)/(k-1) recopiages)
pour k=2, ça fait au pire 2N recopiages de valeurs, et une taille finale au
pire 2 fois trop grande. c'est pas cher payé pour le confort d'utilisation
obtenu.
pour k=1.5 ça fait 3N recopiages, mais au final le vecteur prend au pire
seulement 50% de place de plus que nécessaire.
Ou alors faire tourner une première fois l'algorithme pour connaître la
taille du tableau puis le relancer en ayant entre temps crée un tableau
avec pile la bonne taille ? Mais ca me semble pas trés élégant...
et puis probablement inutile pour si peu d'éléments.
comme d'hab il faudrait mesurer (profiler) mais je pense pas que y ait de
grande différence de temps d'éxécution entre deque et vector, ou encore un
tableau à taille déterminée pour qques centaines de milliers d'entiers.
selon les calculs nécessaires pour précalculer le nbre d'éléments, ça
pourrait très bien ne même pas être rentable par rapport à utiliser
push_back directement.
C'est la méthode qui serait utilisée je pense. Une petite question, pourquoi ne pas utiliser un std::vector<> avec ses méthodes reserve(), push_back()... ?
c'est aussi ce que je me demande, pourquoi ne pas utiliser un des containers STL ? selon comment ces éléments seront ensuite utilisé, et le rapport entre temps passé à remplir le container et temps passé à le parcourir, on peut envisager std::deque ou std::vector (à priori vaut mieux deque, qui aura presque pas d'overhead au remplissage un-par-un, et un très léger overhead au parcours)
la taille, mais pas de 1 car ca serait une perte de temps totale, plutot l'augmenter de 100 à la fois par exemple parce que la copie augmente
100 aussi finira par être une perte de temps. les algos des stdlib font grandir le container exponentiellement (genre x2 à chaque agrandissement, ou x1.5 ..) comme ça N appels à push_back sur un tableau vide avec multiplication de la taille par k à chaque fois occasionnera simplement log(N)/log(k) allocations et kN/(k-1) recopiages de valeurs par rapport à si le vecteur était alloué dès le début. (et aussi le vecteur final occupera plus de place que nécessaire, au pire k fois la place nécessaire) (1 + k + k^2 + k^3 + ... + k^p = (k * k^p - 1)/(k-1) recopiages avec pÎil(log(N)/log(k))-1 au pire N=1+k^p et ça fait (k(N-1)-1)/(k-1) recopiages)
pour k=2, ça fait au pire 2N recopiages de valeurs, et une taille finale au pire 2 fois trop grande. c'est pas cher payé pour le confort d'utilisation obtenu.
pour k=1.5 ça fait 3N recopiages, mais au final le vecteur prend au pire seulement 50% de place de plus que nécessaire.
Ou alors faire tourner une première fois l'algorithme pour connaître la taille du tableau puis le relancer en ayant entre temps crée un tableau avec pile la bonne taille ? Mais ca me semble pas trés élégant...
et puis probablement inutile pour si peu d'éléments. comme d'hab il faudrait mesurer (profiler) mais je pense pas que y ait de grande différence de temps d'éxécution entre deque et vector, ou encore un tableau à taille déterminée pour qques centaines de milliers d'entiers. selon les calculs nécessaires pour précalculer le nbre d'éléments, ça pourrait très bien ne même pas être rentable par rapport à utiliser push_back directement.
-- Sam
Samuel Krempp
le Sunday 07 March 2004 16:50, écrivit :
éventuellement un reserve() sur une valeur "raisonnable"), et on le
plus précisément, une valeur qui *majore* le nombre final d'éléments, et qui sera pas trop souvent plus que 2 fois trop grande.
sinon ya pas vraiment d'interêt de reserver au préalable cette approximation là, vu qu'on obtiendrait quasiment autant de recopiages et une taille pas plus petite qu'en laissant les push_back redimensionner au fur et à mesure.
Eventuellement, on peut utiliser deque<> si on a peur des réallocations trop fréquentes.
tout à fait. ça dépend dc du nbre de fois qu'on prévoit parcourir le container, et comment. si c'est juste qques fois, il y a fort à parier que le gain de temps de std::deque pour l'allocation soit plus conséquent que l'overhead lors des parcours.
-- Sam
le Sunday 07 March 2004 16:50, gramster@gramster.com écrivit :
éventuellement un reserve() sur une valeur "raisonnable"), et on le
plus précisément, une valeur qui *majore* le nombre final d'éléments, et qui
sera pas trop souvent plus que 2 fois trop grande.
sinon ya pas vraiment d'interêt de reserver au préalable cette approximation
là, vu qu'on obtiendrait quasiment autant de recopiages et une taille pas
plus petite qu'en laissant les push_back redimensionner au fur et à mesure.
Eventuellement, on peut utiliser deque<> si on a peur des
réallocations trop fréquentes.
tout à fait. ça dépend dc du nbre de fois qu'on prévoit parcourir le
container, et comment. si c'est juste qques fois, il y a fort à parier que
le gain de temps de std::deque pour l'allocation soit plus conséquent que
l'overhead lors des parcours.
éventuellement un reserve() sur une valeur "raisonnable"), et on le
plus précisément, une valeur qui *majore* le nombre final d'éléments, et qui sera pas trop souvent plus que 2 fois trop grande.
sinon ya pas vraiment d'interêt de reserver au préalable cette approximation là, vu qu'on obtiendrait quasiment autant de recopiages et une taille pas plus petite qu'en laissant les push_back redimensionner au fur et à mesure.
Eventuellement, on peut utiliser deque<> si on a peur des réallocations trop fréquentes.
tout à fait. ça dépend dc du nbre de fois qu'on prévoit parcourir le container, et comment. si c'est juste qques fois, il y a fort à parier que le gain de temps de std::deque pour l'allocation soit plus conséquent que l'overhead lors des parcours.
-- Sam
Fabien LE LEZ
On Sun, 07 Mar 2004 17:24:18 +0100, Samuel Krempp wrote:
selon les calculs nécessaires pour précalculer le nbre d'éléments, ça pourrait très bien ne même pas être rentable par rapport à utiliser push_back directement.
Souvent, on a une vague idée d'un ordre de grandeur du nombre d'éléments. Si on sait qu'il y a 90 % de chances pour que le nombre d'éléments soit compris entre cent mille et un million, un reserve(100000) fera sans doute plus de bien que de mal. Mais bon, on arrive dans des problèmes d'optimisation, donc, si un tel reserve() n'est pas évident, inutile de s'occuper de ça tant que le profiler ne nous l'a pas demandé :-)
-- ;-)
On Sun, 07 Mar 2004 17:24:18 +0100, Samuel Krempp
<krempp@crans.truc.en.trop.ens-cachan.fr> wrote:
selon les calculs nécessaires pour précalculer le nbre d'éléments, ça
pourrait très bien ne même pas être rentable par rapport à utiliser
push_back directement.
Souvent, on a une vague idée d'un ordre de grandeur du nombre
d'éléments. Si on sait qu'il y a 90 % de chances pour que le nombre
d'éléments soit compris entre cent mille et un million, un
reserve(100000) fera sans doute plus de bien que de mal.
Mais bon, on arrive dans des problèmes d'optimisation, donc, si un tel
reserve() n'est pas évident, inutile de s'occuper de ça tant que le
profiler ne nous l'a pas demandé :-)
On Sun, 07 Mar 2004 17:24:18 +0100, Samuel Krempp wrote:
selon les calculs nécessaires pour précalculer le nbre d'éléments, ça pourrait très bien ne même pas être rentable par rapport à utiliser push_back directement.
Souvent, on a une vague idée d'un ordre de grandeur du nombre d'éléments. Si on sait qu'il y a 90 % de chances pour que le nombre d'éléments soit compris entre cent mille et un million, un reserve(100000) fera sans doute plus de bien que de mal. Mais bon, on arrive dans des problèmes d'optimisation, donc, si un tel reserve() n'est pas évident, inutile de s'occuper de ça tant que le profiler ne nous l'a pas demandé :-)
-- ;-)
Samuel Krempp
le Sunday 07 March 2004 17:35, écrivit :
Souvent, on a une vague idée d'un ordre de grandeur du nombre d'éléments. Si on sait qu'il y a 90 % de chances pour que le nombre d'éléments soit compris entre cent mille et un million, un reserve(100000) fera sans doute plus de bien que de mal.
c'est vrai qu'un bon minorant est aussi utilisable. dans cet exemple, si les 90% sont répartis équiprobablement dans [100K, 1000K], en général le reserve(100K) économise 100K recopiages (pour une croissance de vector par doublement), ce qui représente une économie de recopiages moyenne d'environ 20%.
20% c'est déja ça, mais ça ajoute une dépendance à l'ordre de grandeur attendu qui sera catastrophique si le prog est ensuite utilisé dans un autre contexte où le nbre d'éléments sera rarement plus que qques milliers.
c'est en réfléchissant à ça que je me suis fixé comme devise de faire un reserve seulement dans les cas où j'ai une bonne évaluation d'un majorant précis du nbre d'éléments attendus (soit par pré-traitement soit grâce à la connaissance absolue de la situation) précis au sens de qques dizaines de %, pas un majorant qui peut être 100% plus grand.
comme ça je prends ma décision rapidement, et je ne prends pas de risque pour des économies de 20% de recopiages. Du coup si j'ai seulement un ordre de grandeur, je ne fais pas de reserve.
Mais bon, on arrive dans des problèmes d'optimisation, donc, si un tel reserve() n'est pas évident, inutile de s'occuper de ça tant que le profiler ne nous l'a pas demandé :-)
ouaip. sauf si on s'occuppe d'une bibli destinée à traiter des données très variables, ou un petit prog utilitaire en ligne de commande (comme la commande unix sort) qui peut aussi bien être utilisé une fois pour cent million d'éléments, qu'un million de fois pour 100 éléments.. Dans les cas de données très variables, il faut de toute façon réfléchir et quantifier les complexités.
-- Sam
le Sunday 07 March 2004 17:35, gramster@gramster.com écrivit :
Souvent, on a une vague idée d'un ordre de grandeur du nombre
d'éléments. Si on sait qu'il y a 90 % de chances pour que le nombre
d'éléments soit compris entre cent mille et un million, un
reserve(100000) fera sans doute plus de bien que de mal.
c'est vrai qu'un bon minorant est aussi utilisable.
dans cet exemple, si les 90% sont répartis équiprobablement dans
[100K, 1000K], en général le reserve(100K) économise 100K recopiages (pour
une croissance de vector par doublement), ce qui représente une économie de
recopiages moyenne d'environ 20%.
20% c'est déja ça, mais ça ajoute une dépendance à l'ordre de grandeur
attendu qui sera catastrophique si le prog est ensuite utilisé dans un
autre contexte où le nbre d'éléments sera rarement plus que qques milliers.
c'est en réfléchissant à ça que je me suis fixé comme devise de faire un
reserve seulement dans les cas où j'ai une bonne évaluation d'un majorant
précis du nbre d'éléments attendus (soit par pré-traitement soit grâce à la
connaissance absolue de la situation)
précis au sens de qques dizaines de %, pas un majorant qui peut être 100%
plus grand.
comme ça je prends ma décision rapidement, et je ne prends pas de risque
pour des économies de 20% de recopiages.
Du coup si j'ai seulement un ordre de grandeur, je ne fais pas de reserve.
Mais bon, on arrive dans des problèmes d'optimisation, donc, si un tel
reserve() n'est pas évident, inutile de s'occuper de ça tant que le
profiler ne nous l'a pas demandé :-)
ouaip. sauf si on s'occuppe d'une bibli destinée à traiter des données très
variables, ou un petit prog utilitaire en ligne de commande (comme la
commande unix sort) qui peut aussi bien être utilisé une fois pour cent
million d'éléments, qu'un million de fois pour 100 éléments..
Dans les cas de données très variables, il faut de toute façon réfléchir et
quantifier les complexités.
Souvent, on a une vague idée d'un ordre de grandeur du nombre d'éléments. Si on sait qu'il y a 90 % de chances pour que le nombre d'éléments soit compris entre cent mille et un million, un reserve(100000) fera sans doute plus de bien que de mal.
c'est vrai qu'un bon minorant est aussi utilisable. dans cet exemple, si les 90% sont répartis équiprobablement dans [100K, 1000K], en général le reserve(100K) économise 100K recopiages (pour une croissance de vector par doublement), ce qui représente une économie de recopiages moyenne d'environ 20%.
20% c'est déja ça, mais ça ajoute une dépendance à l'ordre de grandeur attendu qui sera catastrophique si le prog est ensuite utilisé dans un autre contexte où le nbre d'éléments sera rarement plus que qques milliers.
c'est en réfléchissant à ça que je me suis fixé comme devise de faire un reserve seulement dans les cas où j'ai une bonne évaluation d'un majorant précis du nbre d'éléments attendus (soit par pré-traitement soit grâce à la connaissance absolue de la situation) précis au sens de qques dizaines de %, pas un majorant qui peut être 100% plus grand.
comme ça je prends ma décision rapidement, et je ne prends pas de risque pour des économies de 20% de recopiages. Du coup si j'ai seulement un ordre de grandeur, je ne fais pas de reserve.
Mais bon, on arrive dans des problèmes d'optimisation, donc, si un tel reserve() n'est pas évident, inutile de s'occuper de ça tant que le profiler ne nous l'a pas demandé :-)
ouaip. sauf si on s'occuppe d'une bibli destinée à traiter des données très variables, ou un petit prog utilitaire en ligne de commande (comme la commande unix sort) qui peut aussi bien être utilisé une fois pour cent million d'éléments, qu'un million de fois pour 100 éléments.. Dans les cas de données très variables, il faut de toute façon réfléchir et quantifier les complexités.
-- Sam
Samuel Krempp
le Sunday 07 March 2004 18:28, écrivit :
20% c'est déja ça, mais ça ajoute une dépendance à l'ordre de grandeur attendu qui sera catastrophique si le prog est ensuite utilisé dans un autre contexte où le nbre d'éléments sera rarement plus que qques milliers.
oui enfin, "catastrophique" en terme d'occupation mémoire, c'est vrai qu'en général ça n'est pas un problème, à moins d'appeler la méthode de nbreuses fois en stockant chque vector..
-- Sam
le Sunday 07 March 2004 18:28, krempp@crans.truc.en.trop.ens-cachan.fr
écrivit :
20% c'est déja ça, mais ça ajoute une dépendance à l'ordre de grandeur
attendu qui sera catastrophique si le prog est ensuite utilisé dans un
autre contexte où le nbre d'éléments sera rarement plus que qques
milliers.
oui enfin, "catastrophique" en terme d'occupation mémoire, c'est vrai qu'en
général ça n'est pas un problème, à moins d'appeler la méthode de nbreuses
fois en stockant chque vector..
20% c'est déja ça, mais ça ajoute une dépendance à l'ordre de grandeur attendu qui sera catastrophique si le prog est ensuite utilisé dans un autre contexte où le nbre d'éléments sera rarement plus que qques milliers.
oui enfin, "catastrophique" en terme d'occupation mémoire, c'est vrai qu'en général ça n'est pas un problème, à moins d'appeler la méthode de nbreuses fois en stockant chque vector..
