slacky.eu

Ragazzi Sono Giorni che Mi sto scervellando con il seguente esercizio da realizzare in C:

implementare un algoritmo che legga e scriva matrici (di interi e
di char) da/su file in maniera efficiente, gestendo per esempio in
modo compatto le matrici sparse

Qualche Consiglio??

Provato wikipedia?

io nono ho capito gran che...
ti serve un database?

puoi leggere e scrivere matrici usando un doppio ciclo for

Non so se ho capito bene... credo che il fulcro di quell'esercizio sia trovare una rappresentazione efficiente di una matrice sparsa, magari basata su liste di incidenza o cose del genere. Mi spiego meglio, se hai una matrice NxN dove N è qualcosa dell'ordine di 1000000 vado a caso, e la maggior parte degli elementi sono 0, più che usare un array multidimensionale con 1000000000000 elementi, quello che puoi fare è tenere delle liste di righe (colonne) che contengono l'indice della colonne (righe) degli elementi che non sono 0 (ovviamente questo nel caso di una matrice con 0 e 1... se ci sono altri valori dovrai tenerne traccia e memorizzare la coppia <indice, valore>).
Questa è la prima cosa che mi è venuta in mente... sicuramente esisteranno soluzioni migliori di questa.

Ipotesi 1: Frequenti una scuola superiore.

Allora potresti utilizzare la seguente struttura.
Lista semplice concatenata formata da elementi di questo tipo (coordinata x, coordinata y,valore non nullo).
Un esempio di memorizzazione efficiente su file:

Codice: Seleziona tutto

1,2,33
1,3,88
1,7,12
2,1,32
4,5,23
4,7,22

la relativa matrice sparsa:

Codice: Seleziona tutto

00 33 88 00 00 00 12
32 00 00 00 00 00 00
00 00 00 00 00 00 00
00 00 00 00 23 00 22

Ipotesi 2: Studi all'università
L'esercizio può diventare molto più complesso.

Ciao
FireEater

Goku ssj3 ha scritto:Ragazzi Sono Giorni che Mi sto scervellando con il seguente esercizio da realizzare in C:

implementare un algoritmo che legga e scriva matrici (di interi e
di char) da/su file in maniera efficiente, gestendo per esempio in
modo compatto le matrici sparse

Qualche Consiglio??

Che rappresentazioni conosci per le matrici?

In particolare, sei interessato a rappresentare l'"entità matematica" matrice. In genere "l'entità" è una struttura di NxM elementi, ma, nel tuo caso, è fatto assunto che vi sia un valore particolare (appartenente o meno al dominio della matrice) che sia molto più comune degli altri. Come poter usare questa informazione?
Normalmente l'implementazione dell'"entità" è effettuata per mezzo di array bidimensionali (o tramite la linearizzazione di questi), ma questa rappresentazione non usa per niente il vantaggio di sapere che un certo elemento è + comune degli altri. Semplicemente il dato + comune sarà presente + volte in memoria

Un'altra rappresentazione dell'entità matrice consiste nel salvarsi a parte il valore "+ comune" e usare una lista linkata (o un array di dimensioni minori, ma la stima in questo caso può essere un azzardo) in cui ogni elemento è del tipo
{ indice_i, indice_j, valore };
Se, scandendo la lista, non si trova nessun elemento che abbia i primi due campi pari a un certo i e a un certo j, allora il valore della cella (i-esima,j-esima) sarà quello di default

Analizziamo ora l'uso della memoria:
nel primo caso abbiamo, per una matrice N*M, un'occupazione N*M*sizeof(elemento)
nel secondo caso abbiamo sizeof(elemento) + ( sizeof(elemento)+sizeof(indice)+sizeof(indice) [ +sizeof(*struct) ] ) * K, dove K è il numero di celle con valore diverso dal valore di default.

Esistono altre implementazioni per le matrici, questo è solo uno spunto

sya54M ha scritto:puoi leggere e scrivere matrici usando un doppio ciclo for

penso possa evitare il doppio ciclo for se gestisce bene gli indici cosi anzicché fare due cicli for uno che va da 0 ad n-1 e un altro che va da 0 ad m-1 potrebbe fare un ciclo che va da 0 ad m+n-1 il che potrebbe essergli utile maggiormente per le matrici sparse.

piccola dritta: comunque è meglio che alle variabili dei cicli for associ un int di tipo auto (conoscete la keyword auto, vero?!) così da ottimizzare il ciclo

Frequento L'università ^_^

Normalmente Quando Mi è stato chiesto di leggere matrici da input proveniente da utente
utilizzavo un doppio ciclo di for
E diciamo che era semplice

Tuttavia qui trovo problemi perchè si tratta di leggere e scrivere matrici da/su file
e soprattutto matrici sparse

Inoltre Ho dei problemi perchè è solo da quest anno che ho iniziato a programmare in C
(ed in più fino ad adesso non ho mai sentito parlare di matrice sparsa)

ciao,
in C non esistono propriamente le matrici. Se stai trattando matrici statiche
char m[3][3];
allora stai parlando di un'area contigua di memoria che puoi salvare su file con una sola write/fwrite.
Per quanto riguarda le matrici sparse penso che li si debba trovare un metodo per comprimere i dati.
Se una matrice sparsa è, come ho letto dal link di 4I4N (ho letto solo le prime righe però

) una matrice con la maggioranza di 0 allora devi trovare un sistema per memorizzare i dati diversi e raggruppare gli zeri risparmiando memoria.
Ho capito questo dall'esercizio, poi non so.

Gio

birg81 ha scritto: penso possa evitare il doppio ciclo for se gestisce bene gli indici cosi anzicché fare due cicli for uno che va da 0 ad n-1 e un altro che va da 0 ad m-1 potrebbe fare un ciclo che va da 0 ad m+n-1 il che potrebbe essergli utile maggiormente per le matrici sparse.

In che modo?

@birg81

birg81 ha scritto:
sya54M ha scritto: piccola dritta: comunque è meglio che alle variabili dei cicli for associ un int di tipo auto (conoscete la keyword auto, vero?!) così da ottimizzare il ciclo

Biagio forse ti riferisci all'attributo register?Perchè l'attributo "auto" è insito nella definizione di una variabile in C.(Non mi dire niente ma sono fresco fresco di "Fondamenti di Informatica").

@Goku ssj3
Per quanto riguarda la lettura scrittura di matrici su file: Nel caso standard io userei il classico doppio for con due indici.Purtroppo non so dirti niente sulle matrici sparse (poichè non le ho anora studiate).

EDIT: Ma si può parlare di matrici "sparse" di caratteri!?!?

FireEater ha scritto:
birg81 ha scritto: penso possa evitare il doppio ciclo for se gestisce bene gli indici cosi anzicché fare due cicli for uno che va da 0 ad n-1 e un altro che va da 0 ad m-1 potrebbe fare un ciclo che va da 0 ad m+n-1 il che potrebbe essergli utile maggiormente per le matrici sparse.
In che modo?

Se hai una matrice dichiarata ad esempio

#define M 3
#define N 4
int mat[M][N];
allora puoi fare come dice Biagio solo che ha sbagliato

for(int i=0; i< (M*N)-1; i++)
fwrite(mat+i,sizeof(int),1,stream);

con il mio metodo
fwrite (mat, sizeof(int), M*N, stream);

ma sempre in quel caso e ovviamente le matrici sparse ti occupano uguale, quindi in generale come soluzione va bene solo se si verifica che la matrice non è sparsa

Goku ssj3 ha scritto:...
implementare un algoritmo che legga e scriva matrici (di interi e
di char) da/su file in maniera efficiente, gestendo per esempio in
modo compatto le matrici sparse
...

Dovresti essere più chiaro:

non sai leggere e scrivere su file?
non sai gestire le matrici sparse?

Per leggere/scrivere su di un file devi vedere:

read(2) e write(2)
oppure fread(3) e fwrite(3)
o altre funzioni simili

Per gestire le matrici sparse puoi:

usare il vecchio algoritmo Yale Sparse Matrix Format, come spiegato anche (in maniera pessima) su wikipedia
Potresti salvarti due array grandi tanto quanti sono i numeri diversi da 0, il primo array contiene i valori (quelli diversi da 0) da inserire nella matrice, mentre il secondo array contiene il posto in cui inserirlo considerando la matrice "stesa".
Altri ed eventuali algoritmi

Ti spiego i due metodi con un esempio, considera la matrice 3x3

Codice: Seleziona tutto

1 0 0
2 0 5
0 4 6

con il metodo Yale Sparse Matrix Format devi salvarti questi tre array:

Codice: Seleziona tutto

a=[ 1 2 5 4 6 ]
ai=[ 1 2 4 6 ]
aj=[ 1 1 3 2 4 ]

La matrice originale la ricavi:

sapendo che gli elementi diversi da 0 sono contenuti nell'array 'a' ordinato da sinistra a destra e dall'alto in basso
Sai che nella prima riga c'è solo 1 elemento ( facendo a(2)-a(1)) posizionato alla colonna aj(1) e il valore è a(1). Nella seconda riga ci sono due elementi ( a(3)-a(2)) e sono nelle colonne aj(2) e aj(3) di valore a(2) e a(3), etc...etc..

Con il secondo metodo devi salvalrti i due array

Codice: Seleziona tutto

a = [ 1 2 5 4 6 ]
aj = [ 1 4 6 8 9 ]

La matrice originale la ricavi:

sapendo che i dati da inserire sono nell'array 'a' ordinati da destra a sinistra e dall'alto in basso
i posti sono indicati nell'array aj immaginando la matrice "stesa", ovvero come [ 1 0 0 2 0 5 0 4 6 ]

Con entrambi i metodi devi salvarti anche le dimensioni della matrice, nel caso ti occupi di matrici quadrate basta scrivere l'ordine n, nel caso di matrici qualsiasi devi salvarti i numeri m e n, con m numero di righe e n numero di colonne.
Il primo metodo occupa più spazio (m+1 interi con m numero di righe della matrice. In pratica l'array 'ai') ma è più rapido. Il secondo occupa meno spazio ma devi implementare la gestione della matrice "stesa", non è difficile ma implica più operazioni del primo algoritmo.

Spetta a te scegliere e lavorare

,
Spina

Si purtroppo Apparte
fprintf e fscanf non so leggere/scrivere su file

Per quanto riguarda le matrici io uso il doppio ciclo di for

Ma non ho mai lavorato con matrici sparse
Mentre nell esercizio si chiede un algoritmo che legga scriva matrici (di qualsiasi dimensione) sia sparse che non

Sono proprio in altro mare

slacky.eu

Aiuto Con Esercizio In C

Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C

doppio ciclo for

Re: Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C

Re: doppio ciclo for

Re: doppio ciclo for

Re: Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C

Re: Aiuto Con Esercizio In C