Allouer un très gros espace mémoire
Le
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.
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.
Merci.
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.
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.
Merci.
Et si c'était justement ce qu'attend le chargé de TP ?
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é.
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!
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.
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.