Au même moment, j'avais codé ça en premier essai:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 while ( pMot1Tab < limiteMot1 || pMot2Tab < limiteMot2 ) { if ( *pMot1Tab == *pMot2Tab ) { lignesCommunes++; // On peut passer à la ligne suivante pMot1Tab++; pMot2Tab++; // Si on matche le dernier mot ... on a pas besoin de continuer ( principe d'unicité des elements ) if ( pMot1Tab >= limiteMot1 ) { break; } if ( pMot2Tab >= limiteMot2 ) { break; } } else if ( *pMot1Tab < *pMot2Tab ) { if ( pMot2Tab < limiteMot2 - (1+N) && *(pMot1Tab+N) < *pMot2Tab ) { pMot1Tab += N; while ( pMot2Tab < limiteMot2 - (1+N) && *(pMot1Tab+N) < *pMot2Tab ) { pMot1Tab += N; } } else if ( pMot1Tab < limiteMot1 - 1 ) // -1 pour pouvoir continuer à utiliser l'élément courant { pMot1Tab++; } else { // Fin de la recherche break; } } else // Soit mot1.lignes.tableau[compteur1] > mot2.lignes.tableau[compteur2] { if ( pMot2Tab < limiteMot2 - (1+N) && *pMot1Tab < *(pMot2Tab+N) ) { pMot2Tab += N; while ( pMot2Tab < limiteMot2 - (1+N) && *pMot1Tab < *(pMot2Tab+N) ) { pMot2Tab += N; } } else if ( pMot2Tab < limiteMot2 - 1 ) // -1 pour pouvoir continuer à utiliser l'élément { pMot2Tab++; } else { // Fin de la recherche break; } } }
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Par exemple, on peut avancer de 10 sur Compteur1 , si et seulement si, la condition de comparaison entre Ligne[Compteur1] et Ligne[Compteur2] est aussi vérifiée entre Ligne[Compteur1+N] et Ligne[Compteur2].Je vois, mais en fait, je ne vois pas comment on fait pour ne pas se louper, en faisant cette technique.
L'incrémentation de Compteur1 (instruction "Compteur1++") se fait après le While.
" Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson
Merci pour la précision supplémentaire Graffito, cette fois, je pense que je vais réussir à écrire un truc bien \o/
De plus, dans mon essai rapide ( code que j'ai envoyé ), il y a un gain de temps ( avec un N à 3 ). Je pense que l'on pourra facilement faire monté N à 10, dans les cas réelles de l'application ( Oui je teste sur des cas réduits ).
Donc, je n'ai plus qu'a amélioré le code
Maintenant, je vais un peu détourner la discussion ( je suis désolé ) . Mais savez vous si on peu faire plus d'optimisation au niveau du compilateur après avoir utilisé de tel flag:
Note: le -DNDEBUG est ultra important, il enlève les assertionsgcc -std=c99 -DNDEBUG -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -O3 -lpthread -Wall -Wextra -lm *.c -o generateur
le -O3 demande les optimisations au niveau du compilateurs ... mais peut on avoir plus?
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Bon finalement, l'histoire de l'avancement dans le tableau en sautant des N éléments n'est pas une solution convenable.
Lorsque j'arrive à coder cette méthode pour qu'elle donne des bons résultats elle est lente. Le premier essai que j'ai écrit ce matin, et aussi le morceau de code d'Ubiquité, sont assez rapide, mais ne donne pas les bons résultats
Lorsque j'écris un bon code, je n'ai pas vraiment de gain ( ou pas assez ). Je ne sais plus vraiment quoi faire...
Pour l'idée des flags de compilation, même en spécifiant une architecture -march, on ne gagne pas.
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Ben c'est juste qu'on l'a mal codé.
Déjà dans mon code je suis à peu prés sûr d'avoir fait une erreur dans le teste du while (Surprenant !).
Essayes ça :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 const int N = 10; unsigned int nbCommunes(const Mot* const mot1, const Mot* const mot2) { // Récupération des tailles des tableaux unsigned int limiteMot1 = mot1->lignes.taille; unsigned int limiteMot2 = mot2->lignes.taille; unsigned int limiteMot1MoinsN = limiteMot1-N; unsigned int limiteMot2MoinsN = limiteMot2-N; unsigned int compteur1 = 0; unsigned int compteur2 = 0; unsigned lignesCommunes = 0; while() { while(mot1->lignes.tableau[compteur1] < mot2->lignes.tableau[compteur2] && compteur1 < limiteMot1 - 1 ) if( compteur1 < limiteMot1MoinsN && mot1->lignes.tableau[compteur1+N] < mot2->lignes.tableau[compteur2]) compteur1+=N; else compteur1++; while(mot1->lignes.tableau[compteur1] > mot2->lignes.tableau[compteur2] && compteu2 < limiteMot2 - 1 ) if( compteur2 < limiteMot2MoinsN && mot1->lignes.tableau[compteur1] > mot2->lignes.tableau[compteur2+N]) compteur2+=N; else compteur2++; if( mot1->lignes.tableau[compteur1] == mot2->lignes.tableau[compteur2] ) { lignesCommunes++; // On peut passer à la ligne suivante compteur1++; compteur2++; // Si on matche le dernier mot ... on a pas besoin de continuer ( principe d'unicité des elements ) if ( compteur1 >= limiteMot1 ) { break; } if ( compteur2 >= limiteMot2 ) { break; } } if(mot1->lignes.tableau[compteur1] < mot2->lignes.tableau[compteur2] && compteur1 == limiteMot1-1) break; if(mot1->lignes.tableau[compteur1] > mot2->lignes.tableau[compteur2] && compteur2 == limiteMot2-1) break; } return lignesCommunes; }
Après la correction des erreurs de compilation,
Après la correction d'une boucle infini,
Oui cette algo accèlère un peu ... mais ne me donne pas les résultats identique à ma référence. Du coup j'ai un doute sur ma référence
Sinon je voudrais faire une précision avec tout ce que l'on dit depuis le début.
Le while suivant:
Ne fait pas avancé le tableau de N, mais de N+1 car nous vérifions la valeur à N :p
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 while(mot1->lignes.tableau[compteur1] < mot2->lignes.tableau[compteur2] && compteur1 < limiteMot1 - 1 ) if( compteur1 < limiteMot1MoinsN && mot1->lignes.tableau[compteur1+N] < mot2->lignes.tableau[compteur2]) compteur1+=N; else compteur1++;
Par contre, c'est toujours un peu lent par rapport à mes objectifs ...
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Bon après debugguage de la version d'Ubiquité, ( bug qui était qu'il faut utilisé des limite en int, car lors du calcul de la limite, si N plus grand que la taille du tableau qui contient des lignes ), bah on va dans un etat très faux.
Et puis, après cette correction, la version d'Ubiquité est devenue super ultra lente ( par rapport à toute les autres versions jusqu'à présent ) ... donc ... je pense continuer avec la mienne, même si je n'obtient pas une vitesse satisfaisante.
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Y_a-t'il un gain en remplaçant mot1->lignes.tableau par une variable tableau1 (idem avec tableau2) ?
" Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson
Si gain il y a, il est peu ou pas visible.
Le code, tel qu'il est avec le remplacement:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98 /** * Nous avons un avantage pour ces deux fonctions * Le liste des lignes sera trié ( car nous lisons un fichier de haut en bas :D ) * Ce qui fera que la recherche des lignes communes sera facilité ( en terme de calcul ) */ unsigned int nbCommunes(Mot* const mot1, Mot* const mot2) { // Récupération des tailles des tableaux int* limiteMot1 = mot1->lignes.tableau + mot1->lignes.taille; int* limiteMot2 = mot2->lignes.tableau + mot2->lignes.taille; int* pMot1Tab = mot1->lignes.tableau; int* pMot2Tab = mot2->lignes.tableau; //unsigned int compteur1 = 0; //unsigned int compteur2 = 0; unsigned lignesCommunes = 0; while ( pMot1Tab < limiteMot1 || pMot2Tab < limiteMot2 ) { if ( *pMot1Tab == *pMot2Tab ) { lignesCommunes++; // On peut passer à la ligne suivante pMot1Tab++; pMot2Tab++; // Si on matche le dernier mot ... on a pas besoin de continuer ( principe d'unicité des elements ) if ( pMot1Tab >= limiteMot1 ) { break; } if ( pMot2Tab >= limiteMot2 ) { break; } } else if ( *pMot1Tab < *pMot2Tab ) { if ( pMot1Tab < limiteMot1 - (1+N1) && *(pMot1Tab+N1) < *pMot2Tab ) { while ( pMot1Tab < limiteMot1 - (1+N1) && *(pMot1Tab+N1) < *pMot2Tab ) { pMot1Tab += N1; } } /* else if ( pMot1Tab < limiteMot1 - (1+N2) && *(pMot1Tab+N2) < *pMot2Tab ) { pMot1Tab += N2; } */ else if ( pMot1Tab < limiteMot1 - 1 ) // -1 pour pouvoir continuer à utiliser l'élément courant { pMot1Tab++; } else { // Fin de la recherche break; } } else // Soit mot1.lignes.tableau[compteur1] > mot2.lignes.tableau[compteur2] { if ( pMot2Tab < limiteMot2 - (1+N1) && *pMot1Tab > *(pMot2Tab+N1) ) { while ( pMot2Tab < limiteMot2 - (1+N1) && *pMot1Tab > *(pMot2Tab+N1) ) { pMot2Tab += N1; } } /* else if ( pMot2Tab < limiteMot2 - (1+N2) && *pMot1Tab > *(pMot2Tab+N2) ) { pMot2Tab += N2; } */ else if ( pMot2Tab < limiteMot2 - 1 ) // -1 pour pouvoir continuer à utiliser l'élément { pMot2Tab++; } else { // Fin de la recherche break; } } } #ifdef _DEBUG printf("(%s,%s) ont %u lignes communes\n",mot1.mot, mot2.mot, lignesCommunes); #endif return lignesCommunes; }
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
J'aurais écrit la boucle simple comme ceci:
La technique s'étend facilement à 3 sources, pas besoin de les gérer deux par deux.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13 while (compteur1 < limiteMot1 && compteur2 < limiteMot2) { if (tableau1[compteur1] == tableau2[compteur2]) { lignesCommunes++; compteur1++; compteur2++; } else if (tableau1[compteur1] < tableau2[compteur2]) { compteur1++; } else { compteur2++; } }
Est-ce que tes tableaux sont denses? Si oui, tu peux les remplacer par des bitmap et faire des et binaires avant de compter les bits à un.
Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.
Certains tableaux sont denses, d'autres non.
L'histoire des bitmaps, je n'ai pas très bien compris. Mais tableau ne sont pas de la même longueur, donc je ne vois pas trop comment vous voulez faire.
Donc si vous pouviez expliciter cette histoire de bitmap, j'en serai ravie .
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Le bit l du bitmap serait à un si la ligne l contient le mot.
Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.
Si vous parlez des bitset de la stl le problème c'est qu'il faut fixer la taille (nombre de ligne du fichier) à la compilation.
EDIT : J'avais pas pensé à boost...
Première note ... je n'ai pas encore utilisé la stl
Deuxième chose, cela voudrait dire qu'il faut un bitmap de 500 000 lignes
Et qu'il faut que je trouve un moyen de le géré
J'ai compris le principe, mais comme c'est la première fois, il faut m'expliquer comment on code ça proprement.
Et cela veut aussi dire, que chaque mot contient sa bitmap ... je sens que cela va faire un grand impact en mémoire :s.
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Donc, j'imagine pour le calcul, ça me fait un parcours de:
500 000 / 32
32: Autant faire des AND sur 32 bits
Et comment je relis mes bits? après ( comment je compte, je veux dire )
Cela semble plus long, non ?
Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi
Ma page sur DVP
Mon Portfolio
Qui connaît l'erreur, connaît la solution.
Cherche popcount, certains processeurs ont une instruction pour (la légende veut que ce soit la NSA qui soit derrière), certains compilo, gcc par exemple, l'ont en intrinsic et il y a quelques trucs bien connus qui font que c'est pas trop couteux à calculer si il n'y a pas d'intrinsic pour.
Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager