Problema con allocazione memoria in Super Mario 2

ciao

sto confrontando varie soluzioni per Super Mario 2, in quanto è un problema utile per provare tecniche di base. Ho una soluzione ricorsiva, in cui provo diverse tecniche per implementare le strutture dati del grafo. Una delle tecniche (ammetto che è strana) è usare liste di adiacenza allocate staticamente, ovvero dichiaro staticamente una matrice N x N e uso ogni riga per contenere la lista di adiacenza. La tecnica in se funziona bene con altre soluzioni. Invece nel codice seguente accadono le seguenti cose:

1)Se dichiaro la matrice con elementi di tipo unsigned il programma fallisce con Signal 11, secondo me perché supero il limite di memoria
2) Se uso una matrice di unsigned short il programma va in timeout. Questo è strano, dal punto di vista teorico la complessità dovrebbe essere la stessa del caso in cui uso delle normali liste di adiacenza dinamiche. Cosa può esserci che rallenta il codice? Forse l’uso di unsigned short rallenta?

Ecco il codice. mediante la define DATA_STRUCTURE, si può selezionare la struttura dati usata per memorizzare il grafo (spero non sia troppo incasinata da leggere per via della parametrizzazione)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* #define DEBUG */
#define MAX_N 10000
#define MAX_M 100000

/* Le macro seguenti definiscono nomi per le strutture dati per memorizzare archi */
#define LISTA_ARCHI 0
#define MATRICE_ADIACENZA_STATICA 1
#define MATRICE_ADIACENZA_SEMI_DINAMICA 2
#define MATRICE_ADIACENZA_DINAMICA 3
#define LISTE_ADIACENZA_STATICHE 4
#define LISTE_ADIACENZA_DINAMICHE 5

/* La macro seguente seleziona la struttura dati per memorizzare gli archi: deve essere
posta uguale ad una delle macro che definiscono i nomi delle strutture dati */
#define DATA_STRUCTURE LISTE_ADIACENZA_STATICHE

/* tipo coppia */
struct pair {
unsigned	first, second;
};

/* file handlers */
FILE *in, *out;

/* variabili globali:
 S è il numero di monete raccolte, le altre hanno gli stessi significati del testo
*/
unsigned N, M, S;

/* insieme dei nodi raggiungibili da 0, implicitamente inizializzato a insieme vuoto */
bool raggiungibili[ MAX_N ];

/* insieme delle monete presenti nei nodi */
unsigned monete[ MAX_N ];
 
/*
Struttura dati usata dalla funzione calcola_cammini_minimi per memorizzare gli archi, 
selezionabile mediante la macro DATA_STRUCTURE

	Se DATA_STRUCTURE vale LISTA_ARCHI si usa la lista di archi globale, realizzata
		mediante un array statico
	Se DATA_STRUCTURE vale MATRICE_ADIACENZA_STATICA si usa una matrice di adiacenza
		allocata staticamente
	Se DATA_STRUCTURE vale MATRICE_ADIACENZA_SEMI_DINAMICA si usa una matrice di
		adiacenza allocata in modo semi-dinamico: un array statico che contiene 
		puntatori alle righe e ciascuna riga e' allocata dinamicamente
	Se DATA_STRUCTURE vale MATRICE_ADIACENZA_DINAMICA si usa una matrice di adiacenza
		allocata in modo dinamico: un array dinamico che contiene puntatori alle righe
		e ciascuna riga e' allocata dinamicamente
	Se DATA_STRUCTURE vale LISTE_ADIACENZA_STATICHE si usano liste di adiacenza
		allocate staticamente
	Se DATA_STRUCTURE vale LISTE_ADIACENZA_DINAMICHE si usano liste di adiacenza
		allocate dinamicamente

	Altrimenti, il caso di default e' LISTA_ARCHI
	
*/
#if DATA_STRUCTURE == MATRICE_ADIACENZA_STATICA

bool archi[ MAX_N ][ MAX_N ];

#elif DATA_STRUCTURE == MATRICE_ADIACENZA_SEMI_DINAMICA

bool *archi[ MAX_N ];

#elif DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA

bool **archi;

#elif DATA_STRUCTURE == LISTE_ADIACENZA_STATICHE

/* array che contiene le lunghezze delle liste di adiacenza */
unsigned numero_archi[ MAX_N ];

/* memoria allocata per le liste di adiacenza:
in questa versione devo usare unsigned short per non violare il limite di memoria */
unsigned short archi[ MAX_N ][ MAX_N ];

#elif DATA_STRUCTURE == LISTE_ADIACENZA_DINAMICHE

struct list_node {
unsigned node;
struct list_node *next;
};

/* array di puntatori a liste di adiacenza, ogni puntatore e' implicitamente inizializzato
a NULL */
struct list_node *archi[ MAX_N ];

#else

struct pair lista_archi[ MAX_M ];

#endif

/*
Questa funzione legge la lista degli archi da input e costruisce la rappresentazione
in memoria centrale dell'insieme degli archi
*/
#if DATA_STRUCTURE == MATRICE_ADIACENZA_STATICA ||\
 DATA_STRUCTURE == MATRICE_ADIACENZA_SEMI_DINAMICA ||\
 DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA 

void leggi_archi( void ) {

/*	se si usa MATRICE_ADIACENZA_SEMI_DINAMICA o MATRICE_ADIACENZA_DINAMICA alloca 
	dinamicamente le righe inizializzando gli elementi a false
	inoltre se si usa MATRICE_ADIACENZA_DINAMICA alloca anche l'array che contiene
	i puntatori alle righe */
#if	DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA
archi = malloc( N * sizeof( bool * ) );
#endif
#if	DATA_STRUCTURE == MATRICE_ADIACENZA_SEMI_DINAMICA ||\
 DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA
for ( unsigned i = 0 ; i < N ; i++ )
	archi[ i ] = calloc( N, sizeof( bool ) );
#endif

/* memorizza archi */
for ( unsigned i = 0, u, w ; i < M ; i++ ) {
	fscanf( in, "%u%u", &u, &w );
	archi[ u ][ w ] = archi[ w ][ u ] = true;
}

}

#elif DATA_STRUCTURE == LISTE_ADIACENZA_STATICHE

void leggi_archi( void ) {

/* memorizza archi */
for ( unsigned short i = 0, u, w ; i < M ; i++ ) {
	fscanf( in, "%hu%hu", &u, &w );

	archi[ u ][ numero_archi[ u ]++ ] = w;
	archi[ w ][ numero_archi[ w ]++ ] = u;
}

}

#elif DATA_STRUCTURE == LISTE_ADIACENZA_DINAMICHE

void leggi_archi( void ) {

/* memorizza archi */
for ( unsigned i = 0, u, w ; i < M ; i++ ) {

	fscanf( in, "%u%u", &u, &w );
	struct list_node *p = malloc( sizeof( struct list_node ) );
	p -> node = w;
	p -> next = archi[ u ];
	archi[ u ] = p;
	p = malloc( sizeof( struct list_node ) );
	p -> node = u;
	p -> next = archi[ w ];
	archi[ w ] = p;
}

}

#else

void leggi_archi( void ) {

/* memorizza archi */
for ( unsigned i = 0, u, w ; i < M ; i++ ) {
	fscanf( in, "%u%u", &u, &w );
	lista_archi[ i ].first = u;
	lista_archi[ i ].second = w;
}

}

#endif

/*
Questa funzione visita in profondità il grafo, in modo ricorsivo

Inoltre memorizza in S il numero di monete raggiungibili a partire dal nodo iniziale
*/
#if DATA_STRUCTURE == MATRICE_ADIACENZA_STATICA ||\
 DATA_STRUCTURE == MATRICE_ADIACENZA_SEMI_DINAMICA ||\
DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA 

void visita( unsigned v ) {

/* imposta v a visitato e incrementa contatore di monete raccolte */
raggiungibili[ v ] = true, S += monete[ v ];

/* visita ricorsivamente i nodi adiacenti */
for ( unsigned i = 0 ; i < N ; i++ )
	if ( archi[ v ][ i ] && !raggiungibili[ i ] ) visita( i );

}

#elif DATA_STRUCTURE == LISTE_ADIACENZA_STATICHE

void visita( unsigned v ) {

/* imposta v a visitato e incrementa contatore di monete raccolte */
raggiungibili[ v ] = true, S += monete[ v ];

/* visita ricorsivamente i nodi adiacenti */
for ( unsigned i = 0 ; i < numero_archi[ v ] ; i++ )
	if ( !raggiungibili[ archi[ v ][ i ] ] ) visita( archi[ v ][ i ] );

}

#elif DATA_STRUCTURE == LISTE_ADIACENZA_DINAMICHE

void visita( unsigned v ) {

/* imposta v a visitato e incrementa contatore di monete raccolte */
raggiungibili[ v ] = true, S += monete[ v ];

/* visita ricorsivamente i nodi adiacenti */
for ( struct list_node *p = archi[ v ] ; p ; p = p -> next )
	if ( !raggiungibili[ p -> node ] ) visita( p -> node );

}

    #else

    void visita( unsigned v ) {

/* imposta v a visitato e incrementa contatore di monete raccolte */
raggiungibili[ v ] = true, S += monete[ v ];

/* visita ricorsivamente i nodi adiacenti */
for ( unsigned i = 0 ; i < M ; i++ )
	if ( lista_archi[ i ].first == v  && !raggiungibili[ lista_archi[ i ].second ] )
		visita( lista_archi[ i ].second );
	else if ( lista_archi[ i ].second == v  && !raggiungibili[ lista_archi[ i ].first ] )
		visita( lista_archi[ i ].first );

    }

#endif

int main( void ) {

in = fopen( "input.txt", "r" );

/* leggi prima riga input */
fscanf( in, "%u%u", &N, &M );
	
/* leggi monete */
for ( unsigned i = 0 ; i < N ; i++ ) fscanf( in, "%u", &monete[ i ] );

/* legge e memorizza grafo */
leggi_archi();

fclose( in );

/* calcola raggiungibili a partire da 0 */
visita( 0 );

/* scrivi output */
out = fopen( "output.txt", "w" );

fprintf( out, "%u\n", S );

fclose( out );

return 0;

}

Corretto. Abbiamo 10^4 \cdot 10^4 = 10^8 celle; se ciascuna richiede 4 byte si arriva a 400 MB (che supera il limite di 256 MB). Usando invece short per memorizzare i pesi degli archi ciascuna cella richiede 2 byte, per un totale di 200 MB.

Anche innalzando il limite di memoria per consentire alla soluzione con int a 4 byte di funzionare, il tuo programma va in timeout esattamente negli stessi testcase.

Ovviamente non può essere che utilizzare short in luogo di int sia più oneroso in termini di tempo (è irragionevole assumere che i calcoli con un tipo di dato più semplice richiedano più tempo).

Indagando, ho scoperto che usi short anche come contatore del numero di archi in qualche ciclo for. Poiché le assunzioni specificano M \le 100\, 000 e USHRT_MAX (ovvero il massimo numero rappresentabile con il tipo unsigned short) vale 2^{16} - 1 = 65\,535; nel caso peggiore con M = 100\,000 il tuo contatore i va in overflow con effetti disastrosi :laughing:


Nota non correlata: malloc ritorna void *, quindi sarebbe bene (a meno di usare -fpermissive) fare il casting esplicito:

node *p = (node*) malloc(...)

giusto! La cosa strana però è che altre soluzioni con algoritmi diversi ma la stessa tecnica di allocazione non vanno in errore. Forse è la combinazione con l’elevato numero di chiamate ricorsive che contribuiscono a saturare la memoria?

ma certo, era questo il problema! Grazie mille! :clap:

su questo non sono d’accordo. C++ e C sono diversi in questo particolare. In C è corretto (lo Standard lo dice in modo esplicito) assegnare un void* ad un altro tipo puntatore e viceversa senza cast in quanto avviene una conversione implicita. Quindi il cast esplicito non è necessario dal punto di vista della correttezza. Poi è una questione di gusti: sul newsgroup comp.lang.c appaiono periodicamente dei thread in cui si dibatte se sia stilisticamente meglio o peggio mettere il cast, ci sono fazioni contrapposte ciascuna delle quali elenca buone ragioni.
Io tendo a non esplicitare le conversioni se non è necessario.
Lo standard C++ invece non consente la conversione implicita da void* ad altri tipi puntatore, quindi in tale linguaggio il cast è decisamente opportuno

mi auto correggo: non è vero, nelle altre soluzioni di cui parlavo avevo già messo unsigned short come tipo della matrice

Ti sei già auto-risposto, però nota che non avrebbe avuto senso un’affermazione come la tua. Se non abbiamo fatto errori di calcolo (e direi che non ce ne sono :stuck_out_tongue: ) la sola matrice occupa 400MB; quindi ogni altra considerazione è priva di significato, visto che già la matrice da sola fa superare il limite globale di memoria.

Era veramente sottile :wink:
Consiglio generale: mai ottimizzare a questo livello il consumo di memoria. Se può avere senso chiedersi il tipo di dato per una matrice con 10^8 celle, di certo non sarà una singola variabile da 4 byte a causare problemi di eccesso di memoria.

Oops! Hai perfettamente ragione, ma avevo salvato il tuo codice .cpp senza rendermi conto che tecnicamente è scritto in C. Quindi non mi si compilava e per questo avevo fatto l’osservazione. Errore mio!