[C] Programmare multicore per sveltire i tempi di esecuzione.. Aiutino?

[akylle95]

Ciao a tutti, ho scritto alla veloce questo programma che deve generare in modo completamente CASUALE, quindi senza nessun tipo di schema dei "tornei" per delle squadre
In particolare le condizioni sono
10 squadre giocano tutte insieme, ma in incontri 1 vs 1
Ci sono 5 giochi, tutte le squadre in una giornata di tornei devono fare una e una sola volta ogni gioco
Le colonne indicano il gioco, quindi in ogni colonna ogni squadra non può ripetersi e le righe invece rappresentano la partita
ad esempio
GIOCO 1 2 3 4 5
TURNO 1 A-B C-D E-F G-H I-L
TURNO 2 C-D I-L G-H E-F A-B
TURNO 3 G-H A-B C-D I-L E-F
TURNO 4 I-L E-F A-B C-D G-H
TURNO 5 E-F G-H I-L A-B C-D
Per praticità ho tenuto costanti le coppie in questo esempio, ma lo scopo del programma e della sua casualità è proprio questo: tentare di fare un calendario senza nessun tipo di schema o simile, cosa che un essere umano nel pensarlo inevitabilmente crea, mentre facendolo fare in modo casuale non evitiamo al 100% la ripetizione di un incontro fra due stesse squadre, però quantomeno è una cosa casuale
Ora nasce il problema: proprio per la sua natura casuale e per il numero di controlli che deve fare (evitare ripetizioni in ogni riga e colonna) il programma mi sta girando da quasi 24 ore e non ha ancora trovato uno schema che vada bene
Mi sta usando però solo il 10% della cpu, e quindi vorrei riuscire a sfruttare il processore al massimo per sveltire i tempi ma non ho idea di come si faccia
Qualcuno sa darmi una mano per favore o sa indicarmi dove posso imparare a farlo?
Grazie mille in anticipo

Akylle

Questo è il codice.. Sono ben accetti suggerimenti per migliorarlo se ne avete (per praticità ho usato nella matrice che simula la tabella, dei numeri che identificano le varie squadre, che poi alla fine nel visualizzare vengono convertiti in colori, ovvero i nomi delle squadre)

Il codice in pratica esegue questo
1)casualmente genera dei numeri che vengono messi in una matrice 5x12 (la prima e l'ultima colonna sono vuote), precedentemente azzerata
2)ad ogni assegnazione di un numero della matrice, viene azzerato il numero corrispondente in un vettore (e quindi prima di assegnarlo di nuovo controlla questo vettore, se è stato azzerato lo genera di nuovo)
3)passando alla riga successiva il controllo aumenta: si controlla anche che quel numero non sia presente in nessuna delle "celle" soprastanti)
4) la matrice viene visualizzata convertendo i nomi

EDIT: ora mi sono accorto di un dettaglio, un controllo in eccesso che forse rende impossibile trovare una soluzione alle condizioni imposte, modifico il codice e lo aggiorno
EDIT 2: codice aggiornato, ora non fa più i controlli in eccesso e le prime due righe le "calcola" in pochi secondi. La terza ci sta impiegando diversi minuti.. Poi non so dirvi

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

int main()
{
clock_t start,end;
double tempo;
start=clock();
char A1[6]={'R','O','S','S','I'}; int b1=5;
char A2[8]={'A','Z','Z','U','R','R','I'}; int b2=7;
char A3[8]={'A','R','A','N','C','I','O'}; int b3=7;
char A4[6]={'L','I','L','L','A'}; int b4=5;
char A5[8]={'B','I','A','N','C','H','I'}; int b5=7;
char A6[8]={'V','.','S','C','U','R','O'}; int b6=7;
char A7[9]={'V','.','C','H','I','A','R','O'}; int b7=8;
char A8[5]={'R','O','S','A'}; int b8=4;
char A9[7]={'G','I','A','L','L','I'}; int b9=6;
char A10[4]={'B','L','U'}; int b10=3;
int i=0;
int j=0;
int k=0;
FILE *turniPTR;
if((turniPTR=fopen("turni.txt","w")==NULL))
{printf("Il file <turni.txt> non può essere aperto\n");}

/*CREA E AZZERA LA TABELLA*/

int tab[5][12];
for(i=0;i<5;i++)
{
for(j=0;j<12;j++)
{
tab[i][j]=5;
}
}

/*ASSEGNAZIONE DEL SEME CASUALE*/
srand(time(NULL));

int random;

/*PRIMA RIGA*/
i=0;
int controllo1[11]={0,1,2,3,4,5,6,7,8,9,10};
for(j=1;j<11;j++)
{
casuale1:
random=(rand()%10)+1;
if(controllo1[random]==0)
{goto casuale1;}
else
{tab[i][j]=random;}
controllo1[random]=0;
}
/*SECONDA RIGA*/
i=1;
int controllo2[11]={0,1,2,3,4,5,6,7,8,9,10};
for(j=1;j<11;j++)
{
casuale2:
random=(rand()%10)+1;
if(j%2==1)
{
if(controllo2[random]==0 || tab[0][j]==random || tab[0][j+1]==random )
{goto casuale2;}
else
{tab[i][j]=random;}
controllo2[random]=0;
}
else if(j%2==0)
{
if(controllo2[random]==0 || tab[0][j]==random || tab[0][j-1]==random)
{goto casuale2;}
else
{tab[i][j]=random;}
controllo2[random]=0;
}

}
/*TERZA RIGA*/
i=2;
int controllo3[11]={0,1,2,3,4,5,6,7,8,9,10};
for(j=1;j<11;j++)
{
casuale3:
random=(rand()%10)+1;
if(j%2==1)
{
if(controllo3[random]==0 || tab[0][j]==random || tab[0][j+1]==random || tab[1][j]==random || tab[1][j+1]==random)
{goto casuale3;}
else
{tab[i][j]=random;}
controllo3[random]=0;
}
else if(j%2==0)
{
if(controllo3[random]==0 || tab[0][j]==random || tab[0][j-1]==random || tab[1][j]==random || tab[1][j-1]==random)
{goto casuale3;}
else
{tab[i][j]=random;}
controllo3[random]=0;
}
}
/*QUARTA RIGA*/
i=3;
int controllo4[11]={0,1,2,3,4,5,6,7,8,9,10};
for(j=1;j<11;j++)
{
casuale4:
random=(rand()%10)+1;
if(j%2==1)
{
if(controllo4[random]==0 || tab[0][j]==random || tab[0][j+1]==random || tab[1][j]==random || tab[1][j+1]==random || tab[2][j]==random || tab[2][j+1]==random)
{goto casuale4;}
else
{tab[i][j]=random;}
controllo4[random]=0;
}
else if(j%2==0)
{
if(controllo4[random]==0 || tab[0][j]==random || tab[0][j-1]==random || tab[1][j]==random || tab[1][j-1]==random || tab[2][j]==random || tab[2][j-1]==random)
{goto casuale4;}
else
{tab[i][j]=random;}
controllo4[random]=0;
}
}
/*QUINTA RIGA*/
i=4;
int controllo5[11]={0,1,2,3,4,5,6,7,8,9,10};
for(j=1;j<11;j++)
{
casuale5:
random=(rand()%10)+1;
if(j%2==1)
{
if(controllo5[random]==0 || tab[0][j]==random || tab[0][j+1]==random || tab[1][j]==random || tab[1][j+1]==random || tab[2][j]==random || tab[2][j+1]==random || tab[3][j]==random|| tab[3][j+1]==random)
{goto casuale5;}
else
{tab[i][j]=random;}
controllo5[random]=0;
}
else if(j%2==0)
{
if(controllo5[random]==0 || tab[0][j]==random || tab[0][j-1]==random || tab[1][j]==random || tab[1][j-1]==random || tab[2][j]==random || tab[2][j-1]==random || tab[3][j]==random|| tab[3][j-1]==random)
{goto casuale5;}
else
{tab[i][j]=random;}
controllo5[random]=0;
}
}
/*CONVERSIONE DEI NUMERI NELLA TABELLA IN STRINGHE DI CARATTERI, NOMI DELLE SQUADRE E VISUALIZZAZIONE A SCHERMO*/
for(i=0;i<5;i++)
{
for(j=1;j<11;j++)
{
if(tab[i][j]==1)
{
for(k=0;k<b1;k++)
{
printf("%c",A1[k]);
}
}
if(tab[i][j]==2)
{
for(k=0;k<b2;k++)
{
printf("%c",A2[k]);
}
}
if(tab[i][j]==3)
{
for(k=0;k<b3;k++)
{
printf("%c",A3[k]);
}
}
if(tab[i][j]==4)
{
for(k=0;k<b4;k++)
{
printf("%c",A4[k]);
}
}
if(tab[i][j]==5)
{
for(k=0;k<b5;k++)
{
printf("%c",A5[k]);
}
}
if(tab[i][j]==6)
{
for(k=0;k<b6;k++)
{
printf("%c",A6[k]);
}
}
if(tab[i][j]==7)
{
for(k=0;k<b7;k++)
{
printf("%c",A7[k]);
}
}
if(tab[i][j]==8)
{
for(k=0;k<b8;k++)
{
printf("%c",A8[k]);
}
}
if(tab[i][j]==9)
{
for(k=0;k<b9;k++)
{
printf("%c",A9[k]);
}
}
if(tab[i][j]==10)
{
for(k=0;k<b10;k++)
{
printf("%c",A10[k]);
}
}
if(j%2!=0)
printf("-");
else
printf(" ");
}
printf("\n");
}
tempo=((double)(end-start))/CLOCKS_PER_SEC;
printf("Tempo di esecuzione: %f secondi\n\n", tempo);
system("PAUSE");
return 0;
}

[__ZERO_UNO__]

Ciao,
penso proprio che la libreria openMP faccia al cosa tuo (è anche già presente in gcc e altri noti compilatori).
Materiale per imparare lo trovi su google:
http://www.google.com/search?q=openmp+tutorial&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:it:official&client=firefox-a

Per esempio
http://openmp.org/mp-documents/omp-hands-on-SC08.pdf

https://engineering.purdue.edu/~eigenman/ECE563/Handouts/ECE563-OpenMP.pdf

;)

[akylle95]

Molto interessante questa libreria.. Devo studiarmela per bene.. Nel frattempo però, avendo bisogno di questo programma funzionante al piú presto, sai dirmi per favore come implementarla? Grazie mille ancora

[U-Boat]

Non ho troppa voglia di leggere il codice, ma da quello che scrivi mi viene da pensare che il tuo problema non sia rendere parallelo il tuo programma, ma piuttosto trovare un algoritmo decente per arrivare alla soluzione.

Da come hai scritto il programma sembra che tu sia alle prime armi, quindi ti do un consiglio su come approciarti: se ti venisse chiesto di "risolvere a mano" questo problema, come lo faresti? Ipotizza quindi di non avere nemmeno un pc davanti e devi fare con carta e penna il torneo.

Un altro aiutino (anzi, aiutone). Tu adesso stai ragionando in questo modo:
genero la riga in modo completamente casuale, poi faccio la verifica; se il "caso" è stato dalla mia parte allora la tengo, altrimenti riprovo. Se ci pensi non è il massimo ed è per questo che il tuo pc sta girando da ore.
Ma se prendiamo il tuo esempio e dobbiamo generare il terzo turno, le squadre A B C D non possono partecipare al primo gioco ed è quindi inutile (anzi, dannoso) poterle scegliere di nuovo... molto meglio quindi non fare più una pesca a caso tra 10 squadre, ma solo tra le 6 che ci interessano.

[akylle95]

Piú che essere alle prime armi, l'assenza di un algoritmo specifico (come quello usato per farlo a mano) è volontaria (non che abbia comunque molta esperienza..sto imparando..)

Molto interessante però l'osservazione sul terzo turno, ad esempio, e sull'esclusione delle squadre già citate in ogni colonna
Riflettendo però risulta un problema potenzialmente irrisolvibile: facedolo a mano, in modo lineare come fa il programma, non è sempre possibile arrivare all'ultima cella e piazzare le due squadre che rimangono escluse nell'ultima riga
Serve ragionare in modo piú globale e focalizzare di meno sulla singola coppia di ogni riga
Ma non ho idea di come fare!