[C] come utlizzare al meglio la memoria

[cocca81]

Ciao.
devo leggere da un file quante volte un carattere è ripetuto se consecutivo, per poi scriverlo in un file nuovo ad esempio: aaabb ccd...ecc ecc, diventerà 3a2b(spazio)2c1d...ecc. e fin qui è tutto facile. Per il docente
questa è considerata un'implementazione banale, perchè viene utilizzato un carattere (1 char, ovvero 1 byte) per ogni cifra del numero di occorrenze del carattere da ripetere; quindi devo utilizzare al meglio la memoria per quanto riguarda la memorizzazione delle cifre. Mi sono
documentata sull'aritmetica binaria, ad esempio i numeri da 0 a 3,
li posso rappresentere con 2 bit, quelli da 4 a 7 con 3 bit,da 8 a 15 con 4 bit e così via, ma non riesco a capire come posso implemetare questa soluzione.
Cmq avrei anche già creato una lista:
struct carattere
{
char carat; //carattere che leggo dal file
int NumVolRip; //conta quante volte un carattere è consecutivo
struct carattere *next;

};
Potrebbe già andare bene così?
Grazie per l'aiuto!!! Ciao ciao

[cionci]

perchè viene utilizzato un carattere (1 char, ovvero 1 byte) per ogni cifra del numero di occorrenze del carattere da ripetere
Spiega meglio cosa fai attualmente

[DanieleC88]

Stai facendo una sorta di RLE, insomma... be', se utilizzi un formato di questo tipo:
48a
per dire che ci sono 48 caratteri 'a' uguali e consecutivi tra di loro, puoi semplicemente evitare di codificare il tutto in ASCII e scrivere un solo byte che vale quante sono le ripetizioni (che occupa 8 bit e potrà quindi rappresentare un numero da 0 a 255: ma dal momento che 0 è un valore impossibile nel tuo caso, puoi prendere il tutto e considerarlo incrementato di 1 per riuscire a contare da un minimo di 1 ad un massimo di 256 ripetizioni). Non credo che ti serva affatto una struttura dati per conservare queste informazioni... a meno che non sia un requisito dell'esercizio.

Spero di non aver capito male il tuo problema o di averti confuso più che aiutato... in bocca al lupo. ;)

[Apollo86]

Stai facendo una sorta di RLE, insomma... be', se utilizzi un formato di questo tipo:
48a
per dire che ci sono 48 caratteri 'a' uguali e consecutivi tra di loro, puoi semplicemente evitare di codificare il tutto in ASCII e scrivere un solo byte che vale quante sono le ripetizioni (che occupa 8 bit e potrà quindi rappresentare un numero da 0 a 255: ma dal momento che 0 è un valore impossibile nel tuo caso, puoi prendere il tutto e considerarlo incrementato di 1 per riuscire a contare da un minimo di 1 ad un massimo di 256 ripetizioni). Non credo che ti serva affatto una struttura dati per conservare queste informazioni... a meno che non sia un requisito dell'esercizio.

Spero di non aver capito male il tuo problema o di averti confuso più che aiutato... in bocca al lupo. ;)

Si, ma se le ripetizioni superano il valore di 256? Non ti basta più 1 byte ....:ciapet:

[rеpne scasb]

■

[Apollo86]

Non è completamente esatto.

Ciao

puoi approfondire il tuo intervento? detto così non mi aiuti a comprendere il mio errore ne tantomeno "cocca81" a risolvere il suo quesito

grazie

[rеpne scasb]

■

[Tommo]

E' vero. Ho pero' suscitato la tua curiosita'.

In sostanza:

Si possono utilizzare i valori compresi tra 0 e 254 (1 byte) per indicare il numero di ripetizioni comprese tra 1 e 255, il valore 255 (0FFh) lo si puo' riservare come codice speciale indicante che il numero di ripetizioni e' un numero che necessita di 2 byte per poter essere rappresentato. Ad esempio, si vogliano rappresentare i seguenti valori:

17 -> |16|
100 -> |99|
1 -> |0|
255 -> |254|
256 -> |255|0|0|
300 -> |255|44|0|
1000 -> |255|232|2|
10000 -> |255|16|38|

Questa tecnica e' conveniente se sono molti i valori minori di 255 e pochi i valori maggiori di 255, altrimenti conviene una codifica a 2 byte.

Quoto... se i numeri però sono soprattutto bassi (< 500) si potrebbe fare meglio:
Il valore 255 significa che il numero "continua" sul prossimo byte, e che il suo valore è 255 + il valore del prossimo byte.
In questa maniera si possono fare "catene", tipo |255|255|10| = 523.
Questo approccio ha il vantaggio che puoi salvare numeri grossi quanto ti pare, però per numeri grandi è meglio come fa repne scasb.

potresti allora riservare 255 per dire che il numero è composto da altri due bytes da leggere insieme, e 254 per dire che c'è ancora un byte.
Così combineresti entrambi i vantaggi, penso :D

[cionci]

Diciamo che si può fare tutto e il contrario di tutto, dipende dalla distribuzione in frequenza delle sequenze.
Ad esempio si potrebbe pensare ad una codifica differenziale.

[DanieleC88]

Si, ma se le ripetizioni superano il valore di 256? Non ti basta più 1 byte ....:ciapet:
Come al solito, non c'è mai un'unica strada che puoi percorrere, la mia era giusto un'idea abbozzata.
Possiamo elaborarla:

spezzi le ripetizioni ogni volta che raggiungi i 256 caratteri ed inserisci in coda una nuova serie di ripetizioni per lo stesso carattere (esempio: carattere 'a' ripetuto 260 volte → |255|a|3|a)
utilizzi una codifica come quella di repne scasb che si adatta "dinamicamente" al numero di ripetizioni
utilizzi una forma |n|byte1..n|carattere|, dove n indica la lunghezza della serie di byte che lo seguono, i quali a loro volta rappresentano il numero delle ripetizioni del carattere salvato alla fine (ad esempio per 65536 ripetizioni di 'a' → |2|255|255|a, che viene valutato come 256 * 256).


Preciso che nella 3) avresti dei numeri pesati a seconda della loro posizione. Nell'esempio che ti ho fatto per 65536 ripetizioni ti bastano 3 byte: il primo indica che il numero è lungo 2 byte. Questi ultimi due sono c1 e c0, che valgono 255 e 255. Il risultato è quindi (256^(n-1) * c1) + (256^(n-2) * c0) + 1 = (256^1 * 255) + (256^0 * 255) + 1 = 65280 + 255 + 1 = 65536.
Credo si possa risparmiare un ulteriore byte, ma al momento ho altro a cui pensare. :asd:

ciao ;)

[cocca81]

Grazie per tutti gli interventi!!! Quindi devo cmq sempre costruire una lista!?? Ma però nel tuo modo, non riesco a capire come devo impostare la struttara dati! cmq oggi pomeriggio mi ci rimetto dietro!!!

[DanieleC88]

Non credo ti servano né una lista né una struttura dati di appoggio, basta un contatore per le ripetizioni consecutive e una funzione di "codifica". :)