Out of memory a parita' di memoria

Ciao a tutti,
Stavo risolvendo il problema pickup quando mi sono ritrovato a dover inizializzare un vettore tridimensionale O(b*b*a), con a = b = 300, che dovevo inizializzare a -1
Inizialmente avevo provato con il costruttore dei vector tradizionale, ovvero con:

typedef vector<long long> vi;
vector<vector<vi>> memo;
memo.resize(b, vector<vi>(b, vi(b, -1)));

Questa soluzione funzionava perfettamente in locale con entrambi i parametri impostati a 300, pero’ dava il solito codice di ritorno 9

Allora ho provato a definire un array per poi successivamente riempirlo con -1

long long memo[301][301][301];
for (int i = 0; i < 301; i++)
   for (int j = 0; j < 301; j++)
       for (int h = 0; h < 301; h++)
           memo[i][j][h] = -1;

Non ha funzionato neanche questo

Inizializzare a -1 era necessario perche’ 0 non distingueva un valore calcolato risultante 0 da un valore non ancora calcolato

Alla fine me la sono cavata utilizzando l’array statico non inizializzato, inserendo poi tutti i valori nel vettore shiftati di un numero positivo arbitrario ed effettivamente mi ha dato 100/100, ma mi rimane il dubbio: per quale motivo potrebbe essere cosi’?

Tempo fa avevo chiesto qualcosa di simile e la risposta che avevo avuto era all’incirca questa:
Per il calcolo dello sforamento di memoria non conta tanto quella che dichiari

long long memo[301][301][301];

ma quella che poi effettivamente utilizzi:
ora, se la inizializzi, la usi tutta 300x301x301x8 e vai ben al di sopra dei 128Mib a disposizione, se no utilizzi solo quella che effettivamente serve e che probabilmente è sotto il limite.
Non metterei la mano sul fuoco relativamente a quanto ho scritto.

Questa cosa mi pare un po’ strana ma anche ragionevole
Con strana indico non la risposta ma la scelta di design del linguaggio
Credo che rinuncero’ a capire il C++ perche’ se effettivamente gli indirizzi inutilizzati rimangono “sporchi” allora significa che vengono inizializzati a 0 nel momento in cui vado a fare il primo accesso. Operazione che, tra l’altro, viene fatta solo se l’array e’ globale…

Non so se sia un qualcosa di dovuto al linguaggio, penso che potrebbe essere il cms che calcola così la quantità di memoria utilizzata.

Non è una funzionalità del C++ ma bensì del sistema operativo. Quello che CMS misura è la “memoria reale”, ovvero la memoria che è fisicamente allocata in RAM. Tuttavia c’è un altro tipo di memoria, la “memoria virtuale” che comprende, oltre alla memoria reale, altre aree di memoria che non si trovano fisicamente in RAM.

Tra queste c’è il segmento bss che è quella parte del programma che contiene le variabili globali non inizializzate. Inizialmente questo segmento non è caricato in RAM, quando però il programma tenta di leggere o scrivere una variabile di questo segmento, il sistema operativo controlla se la variabile è in RAM e se non lo è, alloca un’area di memoria e la inizializza a zero.

Nel tuo caso, inizializzando tutta la matrice a -1, hai caricato l’intera variabile in RAM sforando il limite di memoria, tuttavia lasciandola non inizializzata vengono caricate in RAM solo quelle parti di memoria che effettivamente usi.

4 Mi Piace

Grazie mille del chiarimento