View Full Version : Occupazione struttura!
Dato questo frammento di codice:
#include <stdio.h>
#include <stdlib.h>
struct cifrabinaria
{
unsigned char c;
struct cifrabinaria *next;
};
int main()
{
printf("%u\n",sizeof(unsigned char)+sizeof(struct cifrabinaria *));
printf("%u",sizeof(struct cifrabinaria));
}
Perché eseguendolo ottengo sulla prima linea 5 byte (somma delle dimensioni dei singoli componenti della struttura) e sulla seconda linea 8 byte (dimensione della struttura)... non capisco questa differenza di 3 byte.... qualcuno mi può illuminare?
Se no mi consigliate qualche altro modo di memorizzare una stringa di lunghezza variabile di cui non è possibile fissare un limite massimo?
non ricordo perfettamente come lavora il sizeof ma probabilmente ti restituisce 8 byte nel secondo caso perché considera la memoria occupata in multipli di 4 byte (una word)
Ziosilvio
10-02-2004, 21:17
Ti sei imbattuto in una caratteristica del linguaggio C che dipende squisitamente dal compilatore e dalla macchina.
Dipende, in sostanza, da come viene "allineata" la memoria.
Ci dovrebbe essere qualcosa in proposito sul sito delle FAQ del newsgroup comp.lang.c (http://www.eskimo.com/~scs/C-faq/top.html), ma non mi ricordo in che punto.
Forse c'è qualcosa anche sul Kernighan e Ritchie, ma non ne sono sicuro.
Ma quindi quando occupa la struttura? 5 o 8 byte?
Originariamente inviato da drakend
Ma quindi quando occupa la struttura? 5 o 8 byte?
ti ha risposto bene Ziosilvio
dipende da come è organizzata la memoria. cmq quando la allochi devi prendere un multiplo di 4 byte, quindi anche se la struttura occupa 5 va a finire che ne sprechi 3
ilsensine
10-02-2004, 21:34
8 byte, a meno che il tuo compilatore non consenta di "impacchettarla" in qualche modo dentro i 5 byte.
Per curiosità, intendi usare una struttura per ogni carattere della tua stringa variabile? Non ti sembra un pò contorto?
Originariamente inviato da ilsensine
8 byte, a meno che il tuo compilatore non consenta di "impacchettarla" in qualche modo dentro i 5 byte.
Per curiosità, intendi usare una struttura per ogni carattere della tua stringa variabile? Non ti sembra un pò contorto?
Il fatto è che devo fare un programma in cui ho la necessità di sommare e sottrarre stringhe contenenti configurazioni binarie ed in più non posso mettere un limite massimo alla lunghezza di queste stringhe. Quindi non posso sicuramente usare gli array, se non creando buffer progressivamente più grandi e copiandoci gli array più piccoli, ma questo porta via un bel po' di tempo ed ho la necessità di rendere il programma il più veloce possibile (è per un esame universitario)... d'altro canto non posso nemmeno allocare un megabyte solo per il buffer stringa. Quindi inizialmente avevo pensato ad una lista strutturata come hai già visto: solo che per ogni byte ci sono 4 byte per il puntatore... non è un uso esattamente razionale della memoria. Quindi ho pensato a questo compromesso:
struct cifrabinaria
{
unsigned char cifre[32];
struct cifrabinaria *next;
};
Che ne dici?
ilsensine
10-02-2004, 22:10
realloc
Ziosilvio
10-02-2004, 22:11
Originariamente inviato da drakend
Ma quindi quando occupa la struttura? 5 o 8 byte?
Il valore restituito da sizeof corrisponde sempre al numero di byte realmente occupati.
Quindi, se sizeof dice 8, sono 8.
Originariamente inviato da ilsensine
realloc
La conosco un po' questa funzione, però se non ci dovesse essere più memoria nello heap a disposizione del programma che succede?
Ziosilvio
10-02-2004, 22:16
Originariamente inviato da ilsensine
realloc
realloc alloca blocchi contigui di memoria, per cui se la stringa è veramente molto ma molto lunga assai credo sia meglio usare la lista, magari nella seconda versione e con un conteggio dello spazio rimasto libero.
(Potrebbe non esserci 1 blocco libero da 1 gozziliardo di byte, ma esserci 2000 blocchi liberi da 1 millesimo di gozziliardo di byte.)
Originariamente inviato da Ziosilvio
realloc alloca blocchi contigui di memoria, per cui se la stringa è veramente molto ma molto lunga assai credo sia meglio usare la lista, magari nella seconda versione e con un conteggio dello spazio rimasto libero.
(Potrebbe non esserci 1 blocco libero da 1 gozziliardo di byte, ma esserci 2000 blocchi liberi da 1 millesimo di gozziliardo di byte.)
Io devo sostenere un esame di algoritmi e strutture dati, per questo mi sto scervellando nella scelta della struttura dati in cui memorizzare queste benedette stringhe binarie, stando molto attento anche a non fare semplificazioni del tipo "eh ma tanto non le metterà mai stringhe così lunghe", perché poi il caro prof mi chiede il perché ho trascurato quell'aspetto potenziale e mi boccia. Il fatto che sia statisticamente bassa la possibilità che mi dia un numero binario con milioni di cifre questo non mi autorizza ad eliminare questa possibilità, credo.
Ho pensato quindi ad una soluzione che mantenesse il vantaggio
dell'indicizzazione degli array ed eliminasse il problema della loro
dimensione statica. Fra l'altro mi sembra che realloc, se non trova
un blocco contiguo nella memoria della dimensione richiesta fallisce, vero?
Ziosilvio
10-02-2004, 22:45
Originariamente inviato da drakend
Fra l'altro mi sembra che realloc, se non trova un blocco contiguo nella memoria della dimensione richiesta fallisce, vero?
Sì.
Ragion per cui, IMHO, la soluzione con le liste è il miglior compromesso fra efficienza e complessità, purché la grandezza degli array al loro interno sia opportuna. Io direi 64, 80 o 128, in base al principio che "tanto l'utente di solito non fornisce input troppo grandi" e la tua lista avrà 2 o 3 elementi nel caso "ordinario"
struct cifrabinaria
{
unsigned int cifre;
struct cifrabinaria *next;
};
Un byte per ogni bit è uno spreco (soprattutto se poi devi leggerli/scriverli su disco visto che devi ritrasformarli in sequenza di bit)...
E poi ci accedi ai vari bit con le operazioni di and/or...
Se prevedi che la struttura sia lunga puoi subito usare un vettore:
struct cifrabinaria
{
unsigned int cifre[1024];
int bit_usati;
struct cifrabinaria *next;
};
ilsensine
11-02-2004, 14:51
Originariamente inviato da drakend
La conosco un po' questa funzione, però se non ci dovesse essere più memoria nello heap a disposizione del programma che succede?
Che il tuo programma è fatto male, in quanto gli vuoi far gestire più memoria di quanto è possibile ;)
Il fatto è che devo fare un programma in cui ho la necessità di sommare e sottrarre stringhe contenenti configurazioni binarie
Se intendi cose tipo "011011...", allora fai come ti ha consigliato Cionci (o simili varianti sul tema, se il numero di cifre può essere molto elevato).
Originariamente inviato da drakend realloc alloca blocchi contigui di memoria
No, alloca blocchi contigui di indirizzi virtuali. Ogni s/o ne mette a disposizione 2 o 3 GB indipendentemente dalla memoria disica disponibile.
Ho risolto il problema della struttura dati da utilizzare: alloco un unsigned int e poi uso gli operatori bitwise per manipolare i singoli bit... Così ho 32 configurazioni disponibili con soli 4 byte... con possibilità di espandere la struttura ulteriormente mediante puntatore. Che ne dite della soluzione?
Mi si presenta però un altro problema: "passare" come sorta di parametro di input della funzione un pezzo di cifre che sta nello standard input viola il principio di indipendenza delle funzioni dal contesto in cui sono collocate?
Ovviamente non c'è alcun passaggio reale di parametro, è solo per rendere l'idea...
Originariamente inviato da drakend
Ho risolto il problema della struttura dati da utilizzare: alloco un unsigned int e poi uso gli operatori bitwise per manipolare i singoli bit... Così ho 32 configurazioni disponibili con soli 4 byte... con possibilità di espandere la struttura ulteriormente mediante puntatore. Che ne dite della soluzione?
Cioè come ti avevo detto io ?!?!?
Allocarne uno alla volta è un graaaande spreco di memoria... Fare una lista in questo modo:
struct bits
{
unsigned int data;
struct bits *next;
};
Comporta l'allocazione di 8 byte per ogni 32 bit... Di conseguenza sprechi la metà della memoria allocata...
Originariamente inviato da drakend
Mi si presenta però un altro problema: "passare" come sorta di parametro di input della funzione un pezzo di cifre che sta nello standard input viola il principio di indipendenza delle funzioni dal contesto in cui sono collocate?
Ovviamente non c'è alcun passaggio reale di parametro, è solo per rendere l'idea...
:confused: non ho capito...
Originariamente inviato da cionci
Cioè come ti avevo detto io ?!?!?
Allocarne uno alla volta è un graaaande spreco di memoria... Fare una lista in questo modo:
struct bits
{
unsigned int data;
struct bits *next;
};
Comporta l'allocazione di 8 byte per ogni 32 bit... Di conseguenza sprechi la metà della memoria allocata...
:confused: non ho capito...
Sì come avevi detto tu! Ti ringrazio per avermi nominato gli operatori bitwise, non me li ricordavo! :D
Per quanto riguarda la questione dello standard input intendo dire che avrei una funzione che mi prende dei caratteri da lì (mettiamo la tastiera ad es) e poi me li mette dentro la struttura. Mi spiego meglio: io devo fare un programma che interpreta righe di comando del tipo
s 11001110
s è il nome dell'operazione da fare, e la uso per selezionare la funzione specifica... poi il restante pezzo lo farei "digerire" alla funzione specifica. Mi domando se questo ragionamento costituisca una violazione del principio di indipedenza delle funzioni o meno.
Semplice...fai fare la lettura dell stdin da un'altra funzione... Questa funzione avrà il compito di interpretare i comandi e di estrarre le informazioni...
Ad esempio:
#define LEN 128
#define BYTELEN 32
struct bits
{
unsigned int data[BYTELEN];
int pos; /*indica il primo libero*/
struct bits *next;
};
int inserisci_bit(struct bits **data, char cbit)
{
unsiegned int op;
if(!(cbit == '0' || cbit == '1'))
return -1;
if((*data)->pos == LEN) /* è pieno */
{
while((*data)->next)
(*data) = (*data)->next;
(*data)->next = alloca_bits();
(*data) = (*data)->next;
}
op = 1 << ((*data)->pos)%(sizeof(int)*8);
if(cbit == '1')
((*data)->data[((*data)->pos)/(sizeof(int)*8)] |= op;
else
((*data)->data[((*data)->pos)/(sizeof(int)*8)] &= ~op;
return 0;
}
int inserisci(struct bits *data, char *sbits)
{
if(!sbits || !data)
return -1;
while(strlen(sbits) > 0) {
if(inserisci_bit(&data, *sbits))
return -1;
++sbits;
}
return 0;
}
int leggi_input(FILE *in = stdin)
{
struct bits *data;
data = alloca(data);
/*ora leggi da "in" l'input,
quando hai trovato il comando e la stringa di bit
semplicemente richiami: */
inserisci(data, stringa_bits);
}
Quale principio viola ? L'inserimento si potrebbe in teoria fare meglio... Invece di un bit alla volta si potrebbero inserire tutti i bit contemporaneamente (o quasi tutti)...
Scoperchiatore
11-02-2004, 20:17
mi chiedo come farò a fare Algoritmi e strutture dati in Java :confused: :confused:
Originariamente inviato da cionci
Semplice...fai fare la lettura dell stdin da un'altra funzione... Questa funzione avrà il compito di interpretare i comandi e di estrarre le informazioni...
[...]
Quale principio viola ? L'inserimento si potrebbe in teoria fare meglio... Invece di un bit alla volta si potrebbero inserire tutti i bit contemporaneamente (o quasi tutti)...
Anche io ci avevo pensato, però devo leggere le cifre binarie e metterle al volo dentro la struttura dati, non è che posso crearmi un array in cui mettermi le cifre, anche perché altrimenti perderebbe senso l'uso della struttura dati dinamica, che è ben più laboriosa da gestire.
Quindi tu mi dici che leggendo un pezzo di stdin in una funzione e l'altro nella funzione chiamata è corretto dal punto di vista concettuale? A me potrebbe non fregarmene di meno, però ai professori di algoritmi penso di sì :D
Inoltre sai come potrei recuperare il bit scartato da uno shift? Il problema mi sorge perché quando acquisisco le stringhe binarie da stdin queste si trovano nell'ordine MSB->LSB. Sommandone due però poi nella struttura ho la cifra in ordine LSB->MSB e quindi sorgono problemi quando devo sommarne una terza. O creo un'altra struttura in cui metto ricreo l'ordine MSB-LSB o faccio in modo di estrarre i bit da sinistra e non da destra (appunto ma come faccio?)
Scusa se stresso, ma non ho mai usato il C con gli operatori bitwise :)
Originariamente inviato da drakend
Anche io ci avevo pensato, però devo leggere le cifre binarie e metterle al volo dentro la struttura dati, non è che posso crearmi un array in cui mettermi le cifre, anche perché altrimenti perderebbe senso l'uso della struttura dati dinamica, che è ben più laboriosa da gestire.
E perchè perderebbe senso ?!?!!? Fare un vettore di 32 interi è illegale ? In quel vettore di 32 interi ci infilo 128 bit ;)
Fare una lista di interi non ha senso... E' solo un spreco...
Originariamente inviato da drakend
Quindi tu mi dici che leggendo un pezzo di stdin in una funzione e l'altro nella funzione chiamata è corretto dal punto di vista concettuale? A me potrebbe non fregarmene di meno, però ai professori di algoritmi penso di sì :D
Nell'esempio che ti ho fatto lo stdin viene letto solamente da leggi_input...
Originariamente inviato da drakend
Inoltre sai come potrei recuperare il bit scartato da uno shift? Il problema mi sorge perché quando acquisisco le stringhe binarie da stdin queste si trovano nell'ordine MSB->LSB. Sommandone due però poi nella struttura ho la cifra in ordine LSB->MSB e quindi sorgono problemi quando devo sommarne una terza. O creo un'altra struttura in cui metto ricreo l'ordine MSB-LSB o faccio in modo di estrarre i bit da sinistra e non da destra (appunto ma come faccio?)
Scusa se stresso, ma non ho mai usato il C con gli operatori bitwise :)
Se leggi LSB e lo metti nella parte LSB di un intero e leggi MSB e lo metti nella parte MSB di un intero...che problema c'è ?
Ma leggi sempre 8 bit alla volta ?
Originariamente inviato da cionci
E perchè perderebbe senso ?!?!!? Fare un vettore di 32 interi è illegale ? In quel vettore di 32 interi ci infilo 128 bit ;)
Fare una lista di interi non ha senso... E' solo un spreco...
Nell'esempio che ti ho fatto lo stdin viene letto solamente da leggi_input...
Se leggi LSB e lo metti nella parte LSB di un intero e leggi MSB e lo metti nella parte MSB di un intero...che problema c'è ?
Allocare 32 interi per contenere la lunghezza massima della cifra binaria praticamente sarebbe la scelta più rapida, tanto non credo che il prof metta mai stringhe così lunghe... il fatto è che quando va a controllare il codice sorgente mi chiede perché ho messo quel limite e lì mi castra, dato che non vuole limitazioni a priori sulla dimensione delle cifre binarie. Da questa considerazione e dalle discussioni in questo post ho dedotto che era il caso di allocare una struttura con un intero e il puntatore alla struttura successiva nel caso di numeri più lunghi di 32 bit. Dell'intero ne faccio un uso molto improprio: lo uso come stack per metterci dentro un bit alla volta! :D
Ovviamente il primo bit che mi troverei ad estrarre per l'operazione di addizione sarebbe LSB: nel risultato però l'ordine dei bit si capovolgerebbe. Potrei estrarre i bit da sinistra usando una maschera di bit e facendone l'and con il risultato, però quanto deve essere lunga questa maschera? 32 bit? L'unsigned int è sempre di 4 byte in ogni sistema secondo lo standard ANSI?
Originariamente inviato da cionci
Ma leggi sempre 8 bit alla volta ?
No, scrivo e leggo 1 bit per volta. Per scrivere dentro il mio "stack" faccio l'or fra il campo intero e il numero binario proveniente da stdin e poi faccio uno scorrimento a sinistra. Per fare il contrario dovrei fare l'and con il campo intero e poi scorrere a destra (o a sinistra, nel caso di ordine ribaltato) il campo stesso.
Originariamente inviato da drakend
Allocare 32 interi per contenere la lunghezza massima della cifra binaria praticamente sarebbe la scelta più rapida, tanto non credo che il prof metta mai stringhe così lunghe... il fatto è che quando va a controllare il codice sorgente mi chiede perché ho messo quel limite e lì mi castra, dato che non vuole limitazioni a priori sulla dimensione delle cifre binarie. Da questa considerazione e dalle discussioni in questo post ho dedotto che era il caso di allocare una struttura con un intero e il puntatore alla struttura successiva nel caso di numeri più lunghi di 32 bit. Dell'intero ne faccio un uso molto improprio: lo uso come stack per metterci dentro un bit alla volta! :D
Allora non hai guardato il mio codice ;)
Ho messo un vettore di 32 interi...ma non per contenere tutti i possibili valori immessi...
struct bits
{
unsigned int data[BYTELEN];
int pos; /*indica il primo libero*/
struct bits *next;
};
Se noti bene quella è una lista !!! Quando sono finiti gli interi puoi sempre allocare altre strutture (come d'altronde faccio nel codice successivo)...
Allora, se vuoi usare la struttura come uno stack è comuqnue facile...
Comunque mi hai detto tu che dovevi leggere taaanti bit... E questa è la struttura migliore per leggerne tanti (non allocare ogni volta un solo int, che sarebbe uno spreco di spazio, per 32 bit allochi anche 32 bit di puntatore)... Magari per un programma scolastico può anche andare bene... Comunque nel mio prog se metti BYTELEN a 1 ottieni praticamente lo stesso risultato ;)
Gli interi sono a 32 bit su tutti i sistemi a 32 bit (il codice che ho scritto con un piccolo cambiamento può funzionare con qualsiasi dimensione degli interi)...ed anche tu dovresti farlo in grado di funzionare con qualsiasi dimensione degli interi...
Con piccoli cambiamenti si può adattare alla tua situazione...
#define BYTELEN 32
#define LEN BYTELEN*sizeof(int)
struct bits
{
unsigned int data[BYTELEN];
int pos; /*indica il primo libero*/
struct bits *next;
};
/* se vuoi una struttura come stack */
struct bits *alloca_stack(struct bits *next)
{
struct bits *nuovo;
int i;
nuovo = (struct bits *)malloc(sizeof(struct bits *));
/* le strutture esistenti vengono messe in coda */
nuovo->next = next;
nuovo->pos = 0;
for(i = 0; i < BYTELEN; ++i)
nuovo->data[i] = 0;
return nuovo;
}
int inserisci_bit(struct bits **data, char cbit)
{
unsiegned int op;
if(!(cbit == '0' || cbit == '1'))
return -1;
if((*data)->pos == LEN) /* è pieno */
(*data) = alloca_stack(*data);
/* il bit viene inserito a partire dal LSB dell'int */
op = 1 << ((*data)->pos)%(sizeof(int)*8);
if(cbit == '1')
((*data)->data[((*data)->pos)/(sizeof(int)*8)] |= op;
else /*inserimento dello 0*/
((*data)->data[((*data)->pos)/(sizeof(int)*8)] &= ~op;
return 0;
}
int inserisci(struct bits **data, char *sbits)
{
if(!sbits || !*data)
return -1;
while(strlen(sbits) > 0) {
if(inserisci_bit(data, *sbits))
return -1;
++sbits;
}
return 0;
}
int leggi_input(FILE *in = stdin)
{
struct bits *data;
data = alloca_stack(NULL);
/*ora leggi da "in" l'input,
quando hai trovato il comando e la stringa di bit
semplicemente richiami: */
inserisci(data, stringa_bits);
}
Originariamente inviato da drakend
No, scrivo e leggo 1 bit per volta. Per scrivere dentro il mio "stack" faccio l'or fra il campo intero e il numero binario proveniente da stdin e poi faccio uno scorrimento a sinistra. Per fare il contrario dovrei fare l'and con il campo intero e poi scorrere a destra (o a sinistra, nel caso di ordine ribaltato) il campo stesso.
Non importa fare lo shift...basta tenere un contatore...
Altrimenti quando hai una intera lista di interi quando fai uno shift devi farlo su tutti e devi recuperare l'ultimo bit che esce e metterlo nella struttura successiva (un macello)...
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.