Allouer un très gros espace mémoire

Le
kathan
Bonjour,

En TP de complexit je dois effectuer des programmes ayant diffrents
cots O(n), O(log n), O(n!) et voir pour quelle taille n il
tourneront pendant 3min. Pour le prog en log n, j'ai fait la recherche
d'un nombre dans un tableau tri. Le problme c'est que j'arrive pas =

le faire tourner pendant 3min, en effet la taille n du tableau qu'il
faudrait est tellement grande que j'arrive pas l'allouer.
J'ai pas fait le calcul mais je suppose que c'est impossible d'allouer
la taille ncessaire.
Cependant, en testant un peu, j'ai vu que sur mon pc, intel 32-bit,
sous linux, j'arrive allouer qu'environ 400Mo de mmoire (avec
malloc) avant que a pte. Or il parait que normalement on peut
allouer jusqu' 3Go de mem sous linux 32-bit.
Donc j'aimerai savoir si vous avez un bout de code qui permettrait
d'allouer jusqu' 3Go de mmoire - ou au moins un peu plus que 400Mo.

Merci.
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Marc Boyer
Le #983746
Le 20-02-2007, kathan
En TP de complexité je dois effectuer des programmes ayant différents
coûts O(n), O(log n), O(n!)... et voir pour quelle taille n il
tourneront pendant 3min. Pour le prog en log n, j'ai fait la recherche
d'un nombre dans un tableau trié. Le problème c'est que j'arrive pas à
le faire tourner pendant 3min, en effet la taille n du tableau qu'il
faudrait est tellement grande que j'arrive pas à l'allouer.
J'ai pas fait le calcul


Et si c'était justement ce qu'attend le chargé de TP ?

mais je suppose que c'est impossible d'allouer
la taille nécessaire.
Cependant, en testant un peu, j'ai vu que sur mon pc, intel 32-bit,
sous linux, j'arrive à allouer qu'environ 400Mo de mémoire (avec
malloc) avant que ça pète. Or il parait que normalement on peut
allouer jusqu'à 3Go de mem sous linux 32-bit.
Donc j'aimerai savoir si vous avez un bout de code qui permettrait
d'allouer jusqu'à 3Go de mémoire - ou au moins un peu plus que 400Mo.


AMHA, ça n'a strictement rien à voir avec le C, mais bien
plus avec la configuration de ton OS. fr.comp.os.linux

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)

kathan
Le #983608
On Feb 20, 2:41 pm, Marc Boyer wrote:

En TP de complexité je dois effectuer des programmes ayant différen ts
coûts O(n), O(log n), O(n!)... et voir pour quelle taille n il
tourneront pendant 3min. Pour le prog en log n, j'ai fait la recherche
d'un nombre dans un tableau trié. Le problème c'est que j'arrive pa s à
le faire tourner pendant 3min, en effet la taille n du tableau qu'il
faudrait est tellement grande que j'arrive pas à l'allouer.
J'ai pas fait le calcul


Et si c'était justement ce qu'attend le chargé de TP ?

mais je suppose que c'est impossible d'allouer
la taille nécessaire.
Cependant, en testant un peu, j'ai vu que sur mon pc, intel 32-bit,
sous linux, j'arrive à allouer qu'environ 400Mo de mémoire (avec
malloc) avant que ça pète. Or il parait que normalement on peut
allouer jusqu'à 3Go de mem sous linux 32-bit.
Donc j'aimerai savoir si vous avez un bout de code qui permettrait
d'allouer jusqu'à 3Go de mémoire - ou au moins un peu plus que 400M o.


AMHA, ça n'a strictement rien à voir avec le C, mais bien
plus avec la configuration de ton OS. fr.comp.os.linux

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)



C'est vrai, désolé.


Pascal Bourguignon
Le #983604
"kathan"
Bonjour,

En TP de complexité je dois effectuer des programmes ayant différents
coûts O(n), O(log n), O(n!)... et voir pour quelle taille n il
tourneront pendant 3min. Pour le prog en log n, j'ai fait la recherche
d'un nombre dans un tableau trié. Le problème c'est que j'arrive pas à
le faire tourner pendant 3min, en effet la taille n du tableau qu'il
faudrait est tellement grande que j'arrive pas à l'allouer.
J'ai pas fait le calcul mais je suppose que c'est impossible d'allouer
la taille nécessaire.


LOL!

Bon, alors une recherche dichotomique dans un tableau d'entier 32-bit
par exemple (on pourrait prendre des double-float ce serait pareil).

Disons, sans gérer les cas où la cible n'est pas dans le tableau:

int dichotomy(int target,int min,int max,int* vector){
for(;;){
int cur=(min+max)>>1;
if(vector[cur]<target){ max=cur; }
else if(vector[cur]>target){ min=cur; }
else{ return(cur); }
}
}

On a 1 accès à la mémoire par boucle. Tout le reste se fait dans les
régistres du processeur ou dans la cache L1, alors ça ne compte pas.
Si on a de la RAM DDR2 3200 400 MHz (de la mémoire un peu vieille, on
fait mieux de nos jours...) on va pouvoir faire dans les 800 millions
de boucles par seconde (en lisant dans les 3.2 milliard d'octets par
seconde).

Donc, en 3 minutes, soit 180 secondes, on va pouvoir faire 144
milliard de boucles. C'est à dire que log2(n)4e9
donc il faut que n au départ (n=max-min) soit au moins:


144000000000
2

C'est un nombre avec plus de 43 millions de chiffres en base dix!


Pour comparer, le nombre de particules dans l'univers en supposant que
la masse cachée soit dix fois plus importante que la masse visible
n'est que de 1E83, soit un petit nombre de seulement 83 chiffres en
base dix!



Et oui, c'est ça le problème. C'est justement ça que ce TP voulait te
montrer, mais tu n'as pas fait le calcul toi même... L'univers n'est
pas assez grand pour faire tourner une telle dichotomie pendant 3
minute!



Cependant, en testant un peu, j'ai vu que sur mon pc, intel 32-bit,
sous linux, j'arrive à allouer qu'environ 400Mo de mémoire (avec
malloc) avant que ça pète. Or il parait que normalement on peut
allouer jusqu'à 3Go de mem sous linux 32-bit.
Donc j'aimerai savoir si vous avez un bout de code qui permettrait
d'allouer jusqu'à 3Go de mémoire - ou au moins un peu plus que 400Mo.


Essaye plutôt de prier Dieu et de lui demander s'il ne pourrait pas te preter


144000000000
2
------------------ univers, pour voir comment tu peux faire tourner
83
10

une dichotomie pendant trois minutes...



--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.

Laurent Deniau
Le #983601
Pascal Bourguignon wrote:
"kathan"
Bonjour,

En TP de complexité je dois effectuer des programmes ayant différents
coûts O(n), O(log n), O(n!)... et voir pour quelle taille n il
tourneront pendant 3min. Pour le prog en log n, j'ai fait la recherche
d'un nombre dans un tableau trié. Le problème c'est que j'arrive pas à
le faire tourner pendant 3min, en effet la taille n du tableau qu'il
faudrait est tellement grande que j'arrive pas à l'allouer.
J'ai pas fait le calcul mais je suppose que c'est impossible d'allouer
la taille nécessaire.


LOL!

Bon, alors une recherche dichotomique dans un tableau d'entier 32-bit
par exemple (on pourrait prendre des double-float ce serait pareil).

Disons, sans gérer les cas où la cible n'est pas dans le tableau:

int dichotomy(int target,int min,int max,int* vector){
for(;;){
int cur=(min+max)>>1;
if(vector[cur]<target){ max=cur; }
else if(vector[cur]>target){ min=cur; }
else{ return(cur); }
}
}

On a 1 accès à la mémoire par boucle. Tout le reste se fait dans les
régistres du processeur ou dans la cache L1, alors ça ne compte pas.
Si on a de la RAM DDR2 3200 400 MHz (de la mémoire un peu vieille, on
fait mieux de nos jours...) on va pouvoir faire dans les 800 millions
de boucles par seconde (en lisant dans les 3.2 milliard d'octets par
seconde).

Donc, en 3 minutes, soit 180 secondes, on va pouvoir faire 144
milliard de boucles. C'est à dire que log2(n)4e9
donc il faut que n au départ (n=max-min) soit au moins:


144000000000
2

C'est un nombre avec plus de 43 millions de chiffres en base dix!


Pour comparer, le nombre de particules dans l'univers en supposant que
la masse cachée soit dix fois plus importante que la masse visible
n'est que de 1E83, soit un petit nombre de seulement 83 chiffres en
base dix!


Sans aller chercher la masse cachee de l'univers, ton index de tableau
cur ne tient sur aucun PC (48GB) et juste pour stoker les arguments de
ta fonction, il faut 192GB, alors le tableau lui-meme...

a+, ld.


Publicité
Poster une réponse
Anonyme