Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

[newbee] taille d'un tableau

15 réponses
Avatar
Rincevent
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...

Merci d'avance pour votre réponse


Pierre

5 réponses

1 2
Avatar
James Kanze
"Rincevent" writes:

|> si je vous dit comme ça : "tableau de 240 000 entiers", que me
|> répondez vous ?

Que dans les applications qui utilise les tableaux de cette
taille-là, c'est plus souvent des tableaux de double. Bien que dans
ma dernière application, on arrivait facilement à une million
d'éléments d'un type de classe.

|> 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 !

Tel que tu l'as formulé, c est manifestement faux, mais sur des
machines réalistes, des tableaux d'une million d'éléments,
voire plus, ne sont pas rares. Dans certaines applications, bien
entendues.

|> Bon, j'imagine que votre réponse se situera quelquepart entre (a)
|> et (b).

Plus proche de (c), en fait, j'imagine, pour la plupart des gens.
Aujourd'hui, 240000 éléments, ce n'est vraiment pas beaucoup.
D'ailleurs, la mémoire d'un écran graphique dépasse en
général un million d'éléments. Je connais peu de gens qui
n'ont jamais vu un écran graphique, quand même.

|> 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 ?

Tu viens de dire que tu voulais les stocker dans une liste. Où en est
le problème ?

|> La taille des éléments ajoutés ne sera connue qu'à la
|> fin de l'exécution de mon algorithme.

Pas un problème non plus avec une liste.

|> Il me semble qu'il est impossible de faire varier la taille du
|> tableau en cours de route ?

Je ne sais pas où tu as ça. Ça sert à quoi, push_back(),
sinon que pour augmenter la taille du tableau.

Mais il faut savoir, est-ce que tu les stockes dans une liste, ou dans
un tableau ?

|> 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 ?

Que pour une quantité de données rélativement faible (disons
moins qu'une million), sur une machine moderne, vector, deque ou list
doivent tous faire l'affaire. Tout dépend de ce que tu comptes en
faire après.

|> 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...

Comme tu dis.

--
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
Avatar
James Kanze
Anthony Fleury writes:

|> Rincevent wrote:

|> > 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.

La taille maximum d'un objet varie effectivement d'une implémentation
à un autre, mais sur des machines courantes aujourd'hui, c'est rare
qu'elle se situe en dessous d'un gigaoctet -- largement assez pour son
tableau. Et en C++, au moins, la zone de données d'un tableau ne se
situe pas sur la pile proprement dite ; il n'y a donc pas de
problèmes de cette côté-là non plus.

|> > 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()... ?

Parce qu'il voulait une liste (std::list) ? Quand on parle de tableau en
C++, c'est bien de std::vector dont on parle, non ? (Si on se trouve sur
un ancien compilateur, qui ne supporte pas la bibliothèque standard,
on a normalement déjà sa bibliothèque à soi, avec le même
fonctionnement.)

|> 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.

Que tu l'augementes d'un, ou de mille, si tu commences à lire des
millions d'éléments, le temps des copies va te tuer. Normalement,
on l'augmente d'une multiple de l'ancienne taille : 1.5 et 2 semblent
être des valeurs « populaires ».

--
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
Avatar
James Kanze
"Rincevent" writes:

|> "Rincevent" a écrit dans le message de news:
|> c2fd9u$de1$

|> > 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 !

Curieux. Débuttant en C++, c'est probablement le seul type de tableau
que tu dois connaître. Ce sont les vieux, qui font du C++ depuis
quinze ans, qui pourrait éventuellement ne pas le connaître.

|> Je vais aller farfouiller ça sur le net.

|> 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 ;-)

C'est un peu pourquoi je me démande comment on pourrait trouver ça
grande. La plupart des écrans ont bien plus de résolution que
ça, et sont on couleur -- ça fait tout de suite quelque chose du
genre 1000x1200 int. Et les applis plein écran, ça existe. Alors,
il doit bien avoir des gens qui utilisent des tableaux aussi grands.

--
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
Avatar
Fabien LE LEZ
On 07 Mar 2004 23:20:15 +0100, James Kanze wrote:

Débuttant en C++, c'est probablement le seul type de tableau
que tu dois connaître. Ce sont les vieux, qui font du C++ depuis
quinze ans, qui pourrait éventuellement ne pas le connaître.


Et si le prof est un "vieux qui fait du C++ depuis 15 ans" ?

--
;-)

Avatar
Fabien LE LEZ
On 07 Mar 2004 23:12:50 +0100, James Kanze wrote:

Parce qu'il voulait une liste (std::list) ?


Si on prend le mot "liste" en-dehors de son acception "C++" (ce qui
pourraît très bien être le cas ici puisqu'il s'agit d'un débutant),
j'aurais tendance à plutôt le rapprocher de std::set<> (style, une
liste de courses).

--
;-)

1 2