IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Calcul du nombres de lignes communes entre deux mots


Sujet :

C

  1. #21
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2006
    Messages
    432
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2006
    Messages : 432
    Points : 593
    Points
    593
    Par défaut
    Citation Envoyé par LittleWhite Voir le message
    Je vois, mais en fait, je ne vois pas comment on fait pour ne pas se louper, en faisant cette technique.
    Je veux dire, je veux bien avancé de deux par deux ... mais comment je ne loupe pas une ligne ( je vais tenter un truc tout de suite ) ... mais je reste perplexe.
    Ben tu testes avant d'avancer de N.
    if( Mot1.lignes[compteur1+N] < Mot2.lignes[compteur2])
    compteur1+=N;

    ou plutôt :

    while( Mot1.lignes[compteur1+N] < Mot2.lignes[compteur2])
    compteur1+=N;

  2. #22
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    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.

  3. #23
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    Citation Envoyé par Ubiquité Voir le message
    Ben tu testes avant d'avancer de N.
    if( Mot1.lignes[compteur1+N] < Mot2.lignes[compteur2])
    compteur1+=N;

    ou plutôt :

    while( Mot1.lignes[compteur1+N] < Mot2.lignes[compteur2])
    compteur1+=N;
    Je commence à voir le code qui en découle \o/. Je suis aussi lent que mon premier code, ce matin

    Il faudrait trop un else sur la condition du while, ça serait super
    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.

  4. #24
    Expert éminent Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Points : 7 903
    Points
    7 903
    Par défaut
    Je vois, mais en fait, je ne vois pas comment on fait pour ne pas se louper, en faisant cette technique.
    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].

    L'incrémentation de Compteur1 (instruction "Compteur1++") se fait après le While.
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  5. #25
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    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:

    gcc -std=c99 -DNDEBUG -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -O3 -lpthread -Wall -Wextra -lm *.c -o generateur
    Note: le -DNDEBUG est ultra important, il enlève les assertions
    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.

  6. #26
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    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.

  7. #27
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2006
    Messages
    432
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2006
    Messages : 432
    Points : 593
    Points
    593
    Par défaut
    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;
    }

  8. #28
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    Citation Envoyé par Ubiquité Voir le message
    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:
    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++;
    Ne fait pas avancé le tableau de N, mais de N+1 car nous vérifions la valeur à N :p

    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.

  9. #29
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    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.

  10. #30
    Expert éminent Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Points : 7 903
    Points
    7 903
    Par défaut
    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

  11. #31
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    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.

  12. #32
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    J'aurais écrit la boucle simple comme ceci:
    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++;
            }		
        }
    La technique s'étend facilement à 3 sources, pas besoin de les gérer deux par deux.

    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.

  13. #33
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    Citation Envoyé par Jean-Marc.Bourguet Voir le message
    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.
    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.

  14. #34
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    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.

  15. #35
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2006
    Messages
    432
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2006
    Messages : 432
    Points : 593
    Points
    593
    Par défaut
    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...

  16. #36
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    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.

  17. #37
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2006
    Messages
    432
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2006
    Messages : 432
    Points : 593
    Points
    593
    Par défaut
    Citation Envoyé par LittleWhite Voir le message
    Première note ... je n'ai pas encore utilisé la stl
    Je suis bête tu programme en C ?

    Sinon, si tout les fichiers font 500 000 lignes ca voudrai dire un bitset de 62,5Ko par mot, c'est pas la mort.

  18. #38
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par LittleWhite Voir le message
    Et cela veut aussi dire, que chaque mot contient sa bitmap ... je sens que cela va faire un grand impact en mémoire :s.
    Si tu es dense (plus d'une ligne sur 32 avec le mot), ça pendra moins de place que le tableau qui contient les numéros de lignes.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  19. #39
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 288
    Points
    218 288
    Billets dans le blog
    117
    Par défaut
    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.

  20. #40
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par LittleWhite Voir le message
    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 ?
    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.

+ Répondre à la discussion
Cette discussion est résolue.
Page 2 sur 3 PremièrePremière 123 DernièreDernière

Discussions similaires

  1. Nombre d'éléments communs entre deux tableaux
    Par momo-mtl dans le forum Général JavaScript
    Réponses: 16
    Dernier message: 19/02/2015, 11h08
  2. Calcul de nombre de jours ouvrable entre deux date
    Par etienneborms dans le forum Débuter
    Réponses: 6
    Dernier message: 30/01/2012, 11h53
  3. Réponses: 7
    Dernier message: 16/12/2009, 15h10
  4. Réponses: 1
    Dernier message: 10/08/2006, 15h43
  5. Réponses: 15
    Dernier message: 17/06/2006, 12h49

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo