Compromis efficience/complexité d'un solveur de mots mêlés
Bonjour,
Ce post a été initialement mis au mauvais endroit (rubrique "Téléchargements". Je le place ici pour plus de visibilité. Il fait référence à un programme dont le code entier est consultable das le rubrique téléchargements.
Le problème qu'il résoud est relativement académique: les grilles de mots mêlés. J'ai trois questions à vous poser.
En planchant sur un tuto pour expliquer le projet, je me suis rendu compte que les callocs successifs utilisent trop de mémoire. (8*données*sizeof(long)).
En attendant le programme fait le job. Les plus grande grilles de données existantes taillent 1200 caractères.
Ma question.
Faut-il mixer l'algo de création de la liste d'indices...
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#define BOUCLE_1 for(j=0;j<th;j++) { for(i=0;i<((th-j>dim_min)?dim_min:th-j);i++)
#define INDICE_1 i*(th+1)+j
#define BOUCLE_2 for(i=1;i<tv;i++) { for(j=0;j<((tv-i>dim_min)?dim_min:tv-i);j++)
#define INDICE_2 th*(j+i)+j
#define AJOUT_DIM_MIN dim_min=(tv>th)?th:tv;
long * calculer_indices_se(register int th, register int tv)
{
int dim_min;
long *p_i; /*pointeur sur l'élément courant du tableau*/
long *p_rv; /*pointeur sur la valeur de retour*/
long k;
register long i,j;
p_rv=p_i=(long *) calloc((th+1)*(tv+1)+2,sizeof(long));
if (p_rv==NULL)
{
printf("CALCULER_INDICES: erreur pointeur\n");
return NULL;
};
/*tout est initialisé à -1*/
for(k=0;k<(th+1)*(tv+1)+2;k++)
*p_i++=EOF_INDEX_LIST;
p_i=p_rv;
AJOUT_DIM_MIN
BOUCLE_1
*p_i++= INDICE_1 ;
*p_i++=EOF_WORD;
};
BOUCLE_2
*p_i++= INDICE_2 ;
*p_i++=EOF_WORD;
};
*--p_i=EOF_INDEX_LIST; /*le dernier élément doit être -1 et pas -2 */
return p_rv;
}
#undef BOUCLE_1
#undef BOUCLE_2
#undef INDICE_1
#undef INDICE_2
#undef AJOUT_DIM_MIN |
qui est utilisé 4 fois, et suivi de 4 appels à une fonction d'inversion de la liste d'indices
avec...
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
long *trouver_indices_mot(struct tab_mm *p_tmm,long *p_indexes, char *mot)
{
register long i,j;
register int k;
long *p_rv=NULL; /*valeur de retour, par d‚faut … NULL*/
char *p_c=p_tmm->t;
for(i=0;*(p_indexes+i)!=EOF_INDEX_LIST;i++)
{
for(k=0;mot[k]!='0' && p_c[*(p_indexes+i+k)]==mot[k];k++);
if (k>0 && mot[k]=='\0')
/*trouvé!*/
{
p_rv=(long *) calloc(strlen(mot)+1,sizeof(long));
if (p_rv==NULL)
{
printf("TROUVER_INDICES_MOT: erreur pointeur destination\n");
return NULL;
};
for(j=0;j<strlen(mot);j++)
*(p_rv+j)=*(p_indexes+i+j);
*(p_rv+strlen(mot))=EOF_INDEX_LIST; /*dernier element est -1*/
};
};
return (long *)p_rv;
} |
qui trouve les mots à partir d'une liste d'indices donnée ?
Les + : - moins de mémoire utilisée par les callocs.
- solution plus élégante
Les - : - 8 fonctions de recherche différentes (une pour chaque direction)
- lisibilité moindre de l'algorithme la recherche se fait vie un if dans 3 boucles for imbriquées
- une inflation du code due à la multiplication des fonctions
Trois questions donc :
1) Faut-il préférer la solution existante ou la solution plus complexe mais moins coûteuse en ressources ?
2) Votre avis serait-il différent dans le cas d'un développement pro ? (pas d'actualité, mais votre avis m'intéresse)
3) Enfin, et c'est le plus important : souhaitez-vous estimez-vous utile un tutoriel portant sur sa structure et les choix faits en cours de développement ?
Merci
