orale esame di informatica: chi mi fa questo programma?
- Autore discussione Nicola156
- Data d'inizio
ld) fai te a che livello del Lato Oscuro sono arrivato :lol2)decodifica del file, modo "serio"/1
Per decodificare un file di questo genere la procedura "vera" (non per ingegneri :asd) ) è duplice, a seconda che si voglia "sporcarsi" le mani o volare alto.
La scelta chiaramente dipende dalla cardinalità dei dati.
Cmq
caso 1: monoCPU
- apri il file (non con le funzioni C, con quelle del SO), prendi
la dimensione
- allochi un chunk di memoria opportuno
- carichi in un colpo solo tutto il file (non lo leggi quindi una riga alla volta!)
- chiudi il file
- crei un vettore di puntatori fatto così
squadra.puntatoreNumero
squadra.puntatoreNome
- fai una procedurina in C (io la farei in assembler) che
scansiona la memoria fino a trovare il primo carattere non numerico,
ci mette uno zero (in pratica "crea" una stringa C null-terminata), mette l'indirizzo nel "puntatoreNumero", poi continua la ricerca fino a trovare la fine stringa (\r\n), ci mette un altro zero e memorizza l'indirizzo iniziale nel vettore.
Alla fine in pratica NON crei una copia dei dati "ben messa", ma tieni unicamente i due puntatori che poi userai nella procedura di output per scrivere le stringhe C direttamente.
Nel caso di un ciclo così tight chiaramente ci si metterà dentro un riferimento di lettura fittizio ad una cella diciamo 64byte dopo la fine del numero (questo per rendere più facile il caricamento TLB ed il riempimento cache, generando automaticamente i cache-miss in anticipo rispetto alla richiesta dei dati)
---
metodo 2: multithread (adatto oggi per i sistemi multicore).
Come sopra leggi il file in un colpo solo dentro la RAM, poi dividi la dimensione del file per il numero dei thread (core), poniamo 4.
Poi crei 4 thread di ricerca dati come sopra, che partono da 0, 0+N/4, 0+N/2, 0+N/3, leggermente modificati (i thread maggiori del primo hanno un ciclo iniziale che cerca i \r\n per eliminare gli eventuali "sfridi" di dati)
In questo caso essendo perfettamente partizionato (il problema) non hai alcun problema di località: i thread funzionano senza "pestarsi" i piedi
Ci vorrà alla fine un monitor o dei semafori per la sincronizzazione (non è detto che i thread abbiano la medesima priorità e quindi vengano eseguiti veramente in parallelo), ma è robetta.
Tutto questo, chiaramente, è moooolto più facile con un compilatore C che disponga del fork (in pratica per un programma Linux), dove è "naturale" un approccio del genere.
Sotto *ndox la situazione non è così rosea (intendo la creazione di thread simmetrici), chiaramente si può ugualmente fare con un po' di lavoro in più.
:OK)
Per decodificare un file di questo genere la procedura "vera" (non per ingegneri :asd) ) è duplice, a seconda che si voglia "sporcarsi" le mani o volare alto.
La scelta chiaramente dipende dalla cardinalità dei dati.
Cmq
caso 1: monoCPU
- apri il file (non con le funzioni C, con quelle del SO), prendi
la dimensione
- allochi un chunk di memoria opportuno
- carichi in un colpo solo tutto il file (non lo leggi quindi una riga alla volta!)
- chiudi il file
- crei un vettore di puntatori fatto così
squadra.puntatoreNumero
squadra.puntatoreNome
- fai una procedurina in C (io la farei in assembler) che
scansiona la memoria fino a trovare il primo carattere non numerico,
ci mette uno zero (in pratica "crea" una stringa C null-terminata), mette l'indirizzo nel "puntatoreNumero", poi continua la ricerca fino a trovare la fine stringa (\r\n), ci mette un altro zero e memorizza l'indirizzo iniziale nel vettore.
Alla fine in pratica NON crei una copia dei dati "ben messa", ma tieni unicamente i due puntatori che poi userai nella procedura di output per scrivere le stringhe C direttamente.
Nel caso di un ciclo così tight chiaramente ci si metterà dentro un riferimento di lettura fittizio ad una cella diciamo 64byte dopo la fine del numero (questo per rendere più facile il caricamento TLB ed il riempimento cache, generando automaticamente i cache-miss in anticipo rispetto alla richiesta dei dati)
---
metodo 2: multithread (adatto oggi per i sistemi multicore).
Come sopra leggi il file in un colpo solo dentro la RAM, poi dividi la dimensione del file per il numero dei thread (core), poniamo 4.
Poi crei 4 thread di ricerca dati come sopra, che partono da 0, 0+N/4, 0+N/2, 0+N/3, leggermente modificati (i thread maggiori del primo hanno un ciclo iniziale che cerca i \r\n per eliminare gli eventuali "sfridi" di dati)
In questo caso essendo perfettamente partizionato (il problema) non hai alcun problema di località: i thread funzionano senza "pestarsi" i piedi
Ci vorrà alla fine un monitor o dei semafori per la sincronizzazione (non è detto che i thread abbiano la medesima priorità e quindi vengano eseguiti veramente in parallelo), ma è robetta.
Tutto questo, chiaramente, è moooolto più facile con un compilatore C che disponga del fork (in pratica per un programma Linux), dove è "naturale" un approccio del genere.
Sotto *ndox la situazione non è così rosea (intendo la creazione di thread simmetrici), chiaramente si può ugualmente fare con un po' di lavoro in più.
:OK)
Nicola156":1p9qgdlo ha detto:
temo concretamente che la tua preparazione sia un po'... carente...
ho cercato di usare un metodo "semplice", che potrebbe essere adatto ad un niubbo
---
dubito fortissimamenete di aver tempo di fare il secondo esercizio, sono alle prese con la sostituzione di un server
// convenzioni nomi parametri: i_xxx parametro di input; o_xxx parametro di i/output
// convenzioni costanti: D_ define; _G globale
#define D_G_MAX_LUNGHEZZA_NOME_SQUADRA 25 // max lunghezza nome di una squadra
#define D_G_MAX_NUMERO_SQUADRE 8 // max 8 squadre
#define D_G_MAX_LUNGHEZZA_NUMERO_SQUADRE 2 // fino a 2 caratteri per nr. squadra
#define D_G_MAX_LUNGHEZZA_LINEA 60 // max lunghezza di una riga file input
#include <stdio>
#include <stdlib>
struct squadra
{
char nomeSquadra[D_G_MAX_LUNGHEZZA_NOME_SQUADRA+1];
int codiceSquadra;
};
struct incontro
{
int codiceSquadra1;
int codiceSquadra2;
};
struct squadra squadreInput [D_G_MAX_NUMERO_SQUADRE+1];
struct incontro arrayScontri[D_G_MAX_NUMERO_SQUADRE / 2+1]; // gli scontri sono la metà delle squadre
// lettura file input; parametri handle lettura, puntatore squadre
// ritorna il numero di squadre lette (o zero in caso di errore)
int leggiFileInput(FILE* i_handleFile,struct squadra* o_squadre)
{
// la funzione riconosce righe contenenti caratteri non numerici
// esempio spazi prima del numero, possibile usare anche numeri più
// lunghi di un carattere
// esempi righe ammissibili
// 1 Juventus
// 2 Inter
// c3 Milan
// MANCA la gestione di righe vuote o non ben formattate
char linea[D_G_MAX_LUNGHEZZA_LINEA];
int i;
int indiceSquadraCorrente;
char numeroSquadraStringa[D_G_MAX_LUNGHEZZA_NUMERO_SQUADRE];
char backupCarattere;
char* inizioNumeroSquadra;
char* fineNumeroSquadra;
int codiceSquadraCorrente;
char* inizioNomeSquadra;
indiceSquadraCorrente=0;
if (i_handleFile)
while (!feof(i_handleFile))
{
if (fgets(linea,D_G_MAX_LUNGHEZZA_LINEA,i_handleFile))
{
i=0;
while(!isdigit(linea[i++]) && i<strlen(linea)); // saltiamo i caratteri non numerici
inizioNumeroSquadra=linea+i-1;
while (isdigit(linea[i++]) && i<strlen>D_G_MAX_NUMERO_SQUADRE)
{
printf("Errore di overflow:trovate troppe squadre nel file, max %d\r\n",D_G_MAX_NUMERO_SQUADRE);
system("PAUSE"); // per DOS. Nota non ci interessa chiudere il file
exit(0); // perchè lo fa il main in tutti i casi
}
}
}
return indiceSquadraCorrente;
}
// metodo per generazione incontri.
// ritorna zero in caso di errore, altrimenti gli incontri generati
int generaIncontri(struct squadra* i_squadre,int i_quanteSquadre,struct incontro* i_array)
{
int i;
int scontriOK;
int numeroRandom;
int arraySequenzaCasuale[D_G_MAX_NUMERO_SQUADRE+1];
int flagNumeroGiaPresente;
if ((i_quanteSquadre % 2) || (!i_quanteSquadre)) // controllo preliminare congruenza input
{
printf("generaAndata: Errore grave: i_quanteSquadre non >0 e pari\r\n");
return 0;
}
// inizializziamo il vettore arraySequenaCasuale a dati che sicuramente non possono
// corrispondere ad un codicesquadra. Sono flag di occupazione.
for (i=0;i<i_quanteSquadre;i++)
{
arraySequenzaCasuale=D_G_MAX_NUMERO_SQUADRE+1000;
i_array.codiceSquadra1=D_G_MAX_NUMERO_SQUADRE+1000; // questo ci serve per situazioni di errore
i_array.codiceSquadra2=D_G_MAX_NUMERO_SQUADRE+1000; // (ovvero nel main), non strettamente necessari
}
srand(time(NULL)); // inizializza generatore numeri casuali
scontriOK=0;
while (scontriOK<i_quanteSquadre)
{
numeroRandom=rand() % i_quanteSquadre; // numero casuale tra 0 e numero squadre
flagNumeroGiaPresente=0; // flag: il numero è già stato generato (0=falso, 1=vero)
for (i=0;i<scontriOK;i++) // cerchiamo all'interno del vettore (scontriOK rappresenta
// la cardinalità dei numeri casuali "buoni" (non
// ripetuti)
if (arraySequenzaCasuale==numeroRandom) // se il numero è già nel vettore...
{
flagNumeroGiaPresente=1; // settiamo il flag
break; // ed usciamo dal ciclo
}
if (!flagNumeroGiaPresente) // a questo punto se il numero NON è presente...
// lo memorizziamo. Attenzione al "++" che
// incrementa il numero di scontri già generati
arraySequenzaCasuale[scontriOK++]=numeroRandom;
}
// per intercettare eventuali bug filliamo inizialmente il vettore con dati "assurdi"
// che ci permettano di capire se l'algoritmo lascia "buchi"
// esempio 1008 1008 1008 1008 1008 1008 1008 1008 significa che il vettore è vuoto
// generazione casuale numero 2
// 2 1008 1008 1008 1008 1008 1008 1008 il primo numero viene memorizzato
// generazione casuale numero 3
// 2 3 1008 1008 1008 1008 1008 1008 il secondo numero viene memorizzato
// generazione casuale numero 2
// 2 3 1008 1008 1008 1008 1008 1008 il terzo numero NON viene memorizzato
printf("Array casuale\r\n"); // scriviaamo a video
for (i=0;i<i_quanteSquadre;i++)
printf("%.2d ",arraySequenzaCasuale);
printf("\r\n");
for (i=0;i<i_quanteSquadre;i+=2) // memorizziamo. Attenzione che il numero degli
// scontri è pari alla META' delle squadre, e
// quindi c'è un "i+=2" che significa i=i+2
{
i_array[i/2].codiceSquadra1=arraySequenzaCasuale; // e qui dividiamo per due i
i_array[i/2].codiceSquadra2=arraySequenzaCasuale[i+1]; // (i è pari sicuramente, controllo iniziale)
}
return scontriOK/2; // ritorniamo il numero degli scontri
}
// questa funzione scrive su un file gli scontri, attingendo il nome dal parametro i_squadre
// se il primo parametro (i_flagInverti) è a zero scrive "andate", altrimenti "i ritorni"
// semplicemente inverte la stampa
void scrivi_output(int i_flagInverti,int i_quantiScontri,struct squadra* i_squadre,struct incontro* i_incontri,FILE* i_output)
{
int i;
// controlli vari sui parametri di input
if (!i_output)
{
printf("scrivi_output: errore grave, parametro file output vuoto\r\n");
return;
}
if (!i_quantiScontri)
{
printf("scrivi_output: errore grave, parametro quantiScontri a zero \r\n");
return;
}
if (!i_squadre)
{
printf("scrivi_output: errore grave, parametro squadre NULL\r\n");
return;
}
if (!i_incontri)
{
printf("scrivi_output: errore grave, parametro incontri NULL\r\n");
return;
}
// scrive due volte: una su video, una su file. La differenza tra le due versioni
// è semplicemente che scrive codiceSquadra1-codiceSquadra2 oppure codiceSquadra2-codiceSquadra1
for (i=0;i<i_quantiScontri;i++)
if (i_flagInverti)
{
printf("%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
fprintf(i_output,"%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
}
else
{
printf("%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra2].nomeSquadra,i_squadre[i_incontri.codiceSquadra1].nomeSquadra);
fprintf(i_output,"%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
}
}
int main(int argc, char *argv[])
{
FILE* handleInput;
FILE* handleOutput;
char nomeFileInput[250];
char nomeFileOutput[250];
int i;
int quanteSquadre;
int scontri;
if (argc!=3) // ci devono essere esattamente due parametri
{
printf("Parametri : nomefileinput nomefileoutput\n");
printf("Esempio : c:\\input.txt c:\\output.txt\n");
return 1;
}
// argv[0] è il nome del file eseguibile del programma
// argv[1] è il primo parametro (file di input)
// argv[2] è il secondo parametro (file di output)
sprintf(nomeFileInput ,"%s",argv[1]);
sprintf(nomeFileOutput ,"%s",argv[2]);
// copiamo argv[1] in nomeFileInput e argv[2] in nomeFileOutput perchè
// in fase di debug è oneroso mettere sempre i parametri a riga di comando:
// togliendo i commenti alle righe successive si impostano automaticamente
// i parametri
//sprintf(nomeFileInput,"%s","c:\\input.txt");
//sprintf(nomeFileOutput,"%s","c:\\output.txt");
printf("Apro file |%s|\r\n",nomeFileInput);
handleInput=fopen(nomeFileInput,"r"); // apro il file
if (handleInput) // controllo che sia effettivamente aperto
{
// leggo le squadre dal file di input e chiudo l'handle
quanteSquadre=leggiFileInput(handleInput,squadreInput);
// nota bene: il controllo successivo è ridondante, ma è possibile
// che la funzione leggiFileInput alteri lo stato del file e quindi,
// per buona abitudine, meglio mettere comunque il controllo di validità
// prima di chiuderlo.
// altra nnota: se leggiFileInput ritorna 0 siamo in situazione di errore
if (handleInput)
fclose(handleInput);
if (!quanteSquadre)
{
printf("main: errore in lettura squadre: abortisco\r\n");
return 1;
}
// adesso generiamo gli scontri
scontri=generaIncontri(squadreInput,quanteSquadre,arrayScontri);
printf("Squadre %.2d scontri %.2d OK\r\n",quanteSquadre,scontri);
// verifichiamo anche qui che non ci siano problemi (avrei scontri=0)
if (scontri)
{
handleOutput=fopen(nomeFileOutput,"w"); // apriamo il file in scrittura
if (handleOutput) // se OK
{
printf("File output aperto\r\n"); // stampiamo le squadre a video
for (i=0;i<quanteSquadre;i++)
printf("%.2d |%s|\r\n",squadreInput.codiceSquadra,squadreInput.nomeSquadra);
// doppie scritte (video + file), come richiesto dall'esercizio
printf("Quarti di finale 2006/2007\r\n");
fprintf(handleOutput,"Quarti di finale 2006/2007\r\n");
printf("Partite di andata\r\n");
fprintf(handleOutput,"Partite di andata\r\n");
// scriviamo l'andata. Attenzione al primo parametro di scrivi_output ZERO
scrivi_output(0,scontri,squadreInput,arrayScontri,handleOutput);
printf("Partite di ritorno\r\n");
fprintf(handleOutput,"Partite di ritorno\r\n");
// scriviamo l'andata. Attenzione al primo parametro di scrivi_output UNO
// che farà sì che la funzione inverta le squadre
scrivi_output(1,scontri,squadreInput,arrayScontri,handleOutput);
// chiudiamo il file, sempre con controllo aggiuntivo ridondante poichè
// abbiamo chiamato delle funzioni che, in teoria, avrebbero potuto
// chiudere il file "a tradimento"
if (handleOutput)
fclose(handleOutput);
}
else
{
// non siamo riusciti a scrivere sul file
printf("main: problema grave impossibile scrivere su file %s\r\n",nomeFileOutput);
if (handleInput) // nota test ridondante, ma è sempre bene metterlo
fclose(handleInput);
}
}
}
else
// non si è riusciti ad aprire il file di input
printf("main: problema grave impossibile aprire file %s\r\n",nomeFileInput);
system("PAUSE"); // per DOS
return 0; // se arriviamo fino a qui ritorniamo ZERO (tutto OK) alla shell
}
Commenti: il numero di squadra nel file di input non serve ad una cippa, ma l'ho lasciato per il tuo docente.
Non è gestito il caso in cui una riga sia vuota (o meglio abortisce e basta)
Questo è un'esecuzione di esempio
File di input
1 Juventus
2 Inter
c3 Milan
4 San Giovanni al Natisone
5 Bari
6 Castellamare di Stabia
7 Triestina
8 Udinese
file di output
Quarti di finale 2006/2007
Partite di andata
Udinese - Milan
Triestina - San Giovanni al Natisone
Inter - Bari
Castellamare di Stabia - Juventus
Partite di ritorno
Udinese - Milan
Triestina - San Giovanni al Natisone
Inter - Bari
Castellamare di Stabia - Juventus
Se vuoi togliere la giustificazione a DESTRA delle seconde squadre (come nell'esempio di output) devi cambiare qui
if (i_flagInverti)
{
printf("%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
fprintf(i_output,"%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
}
else
{
printf("%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra2].nomeSquadra,i_squadre[i_incontri.codiceSquadra1].nomeSquadra);
fprintf(i_output,"%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
}
}
mettendoci semplicemente %s invece di %25s
PS mi sono accorto di aver messo in giro dei "\r\n" invece dei "\n", è deformazione Linux, normalmente uso gcc :asd) , vabbè ho cambiato il sorgente che trovi qui
http://www.franzauker.com/main.c
:OK)
Non è gestito il caso in cui una riga sia vuota (o meglio abortisce e basta)
Questo è un'esecuzione di esempio
File di input
1 Juventus
2 Inter
c3 Milan
4 San Giovanni al Natisone
5 Bari
6 Castellamare di Stabia
7 Triestina
8 Udinese
file di output
Quarti di finale 2006/2007
Partite di andata
Udinese - Milan
Triestina - San Giovanni al Natisone
Inter - Bari
Castellamare di Stabia - Juventus
Partite di ritorno
Udinese - Milan
Triestina - San Giovanni al Natisone
Inter - Bari
Castellamare di Stabia - Juventus
Se vuoi togliere la giustificazione a DESTRA delle seconde squadre (come nell'esempio di output) devi cambiare qui
if (i_flagInverti)
{
printf("%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
fprintf(i_output,"%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
}
else
{
printf("%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra2].nomeSquadra,i_squadre[i_incontri.codiceSquadra1].nomeSquadra);
fprintf(i_output,"%25s - %25s\r\n",i_squadre[i_incontri.codiceSquadra1].nomeSquadra,i_squadre[i_incontri.codiceSquadra2].nomeSquadra);
}
}
mettendoci semplicemente %s invece di %25s
PS mi sono accorto di aver messo in giro dei "\r\n" invece dei "\n", è deformazione Linux, normalmente uso gcc :asd) , vabbè ho cambiato il sorgente che trovi qui
http://www.franzauker.com/main.c
:OK)