Discussion :

[Médinoc]

Je pense que les listes sont beaucoup trop creuses pour des bitmaps.

En plus, vu le nombre de mots, ça m'étonnerait que leur donner à chacun un buffer de 60k soit une bonne idée pour les performances...

[Graffito]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Je pense que les listes sont beaucoup trop creuses pour des bitmaps.

A première vue OUI, c'est pourquoi j'avais laissé tomber cette voie quand LittleWhite avait indiqué que les documents pouvaient comporter un grand nombre de lignes.

En réfléchissant un peu, il y a une solution qui consiste à organiser les bitmaps ainsi:
Prenons l'exemple d'un document de 3000 lignes, avec un mot qui apparait en ligne 0, 2090 et 2091 (2091=2*32*32+2*32+3).
Les chaines de bits sont des entiers 32 bits, l'indication "..." indique des bits finaux à 1, 1024=32*32.

• Bitmaps de niveau 3 : 101... // blocs A et B contenant des mots : [1024*0:1024*1[ et [1024*2:1024*3[
• Bitmaps de niveau 2 (A): 1... // bloc X contenant des mots entre [1024*0+32*0:1024*0+32*1 [
• Bitmaps de niveau 2 (B): 001... //bloc Y contenant des mots entre [1024*2+32*2:1024*2+32*3[
• Bitmap de niveau 1 (X) : 1.... // ligne 1024*0+32*0+0=0
• Bitmap de niveau 1 (Y) : 0011.... // lignes 1024*2+32*2+2=2090 et 1024*2+32*2+3=2091

Schématiquement, ça donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
   (Document)
   |   |   |
  (A)  °  (B)
   |       |
   X     __Y__
   |    |     |
   0   2090  2091

Le nombre de niveaux dépend du nombre de lignes du document:
- moins de 32 lignes : 1 niveau,
- moins de 32*32 (1024) : 2 niveaux,
- moins de 32*32*32 (32468) : 3 niveaux
- ...

Comme n'apparaissent dans la structure que les bitmaps contentenant au moins un "1", la taille est raisonnable et on peut utiliser des AND entre bitmaps de même niveau correspondant aux même blocs!

PS : Pour compter le nombre de 1 dans un BITMAP, on peut au départ calculer le tableau T de 64K bytes donnant le nombre de 1 de chaque nombre entre 0 et 64K. Pour un int N de 32 bits, le nombre de bits à 1 sera égal à T[high(N)]+T[Low(N)]

[LittleWhite]

Bonjour à tous,

Merci pour toute vos réponses, mais je vais devoir stopper cette discussion ( à moins que vos ne vouliez parler plus longtemps sur les champs de bits ... )

Premièrement, les solutions apportées ici, ne sont pas mauvaises ( juste pas vraiment applicables dans mon cas ). L'histoire du saut par N cases est une que j'ai mis en place, mais, le problème est que pour mettre ses optimisations en place, cela rajoute des tests ... donc les gains sont vites perdus ( sachant qu'il était très facile que j'ai des tableaux ou le N optimal est 2 ou 3 ), du coup, les tests fait juste avant bouffaient le gain.

La réecriture de mon code, est une bonne chose, car il y a moins de tests. Donc celle là est une vraie optimisation mais toujours trop faible.

Les champs de bits, me semble une pas trop mauvaise idée ( désolé je n'ai pas implémenté ), mais j'ai toujours cette impression que cela allait prendre plus de temps, qu'en gagné.

Mais, alors pourquoi arrêter la conversation. Tout simplement parce que je me suis rendu compte que cela ne servait à rien d'essayer d'optimiser une fonction qui n'était pas trop mal dans sa première écriture. En fait, c'est tout mon programme qui est lent. Et donc, certes c'était cette fonction qui prenait le plus de temps, mais l'optimisation n'était pas à faire dans la fonction, mais dans le design du programme.
Après réflexion j'ai réussi à trouver un moyen pour diminuer significativement le nombre d'appel à cette fonction. Du coup j'ai gagné un temps fou.

Voilà tout, merci pour vos réponses, je suis désolé de vous avoir fait perdre du temps sur un problème mal défini.

(Note: dois-je mettre le sujet en résolu, ou pas?)

[eyquem]

Bonjour,



Je crois avoir compris que le champ lignes d’une structure Mot est un tableau contenant certaines lignes seulement d’un fichier X extérieur à Mot, à savoir les lignes de X comportant le char* mot;
Il n’y a donc pas d’extraction de lignes à faire de X pour obtenir cette liste, elle est déjà là toute prête dans une structure Mot.

De ce fait on n’a à se préoccuper ni de ce qu’est le fichier X, ni de ce qu’est char* mot; , ni de la nature de ce que contient le tableau d’une structure Mot : au plus simple, on peut dire qu’un tel tableau lignes contient des éléments sans se préoccuper de les connaître précisément, et il suffit de savoir qu’on peut comparer les éléments de deux tableaux de structures Mot.



Ainsi reformulé, je comprends alors le problème ainsi:

soient deux tableaux de structures Mot
T1 = (a,b,c,d,e,f,g,h,i,j,k)
T2 = (f,w,t,k,e,r,p,x,a,u)
il faut extraire l’information que (a,e,f,k) est l’ensemble des éléments communs aux deux tableaux.

Est-ce bien ça ?
Si c’est le cas, je me permets d’apporter mon grain de sel.






Premièrement,
n’y a-t-il pas en langage C un moyen de tester si un truc donné appartient à une structure ou non , au lieu de passer en revue tous les éléments de la structure et tester s’il y a égalité de chacun avec le truc en question ?

C’est à dire, n’y a-t-il rien de mieux comme instruction que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if ( mot1->lignes.tableau[compteur1] == mot2->lignes.tableau[compteur2] )

pour savoir si mot1->lignes.tableau[compteur1]
est dans mot2->lignes.tableau ?

Car je suppose que
mot1->lignes.tableau[compteur1] désigne l’élément du tableau de mot1 qui se trouve repéré par l’index compteur1
et que mot2->lignes.tableau[compteur2] est l’élément du tableau de mot2 repéré par compteur2.

Une expression du genre
if ( mot1->lignes.tableau[compteur1] in mot2->lignes.tableau )
n’existe-t-elle pas en C ?


Je sens que vous allez trouver cette question idiote dans le cadre de C: vous allez me répondre que l’instruction que j’écris avec in est une instruction typique d’un langage du haut niveau et que C, étant un langage du bas niveau, ne peut pas faire autre chose que le boulot précis que l’instruction avec in recouvre.
Tapez pas trop fort, je suis contaminé par les facilités de Python.








Secondement,
je ne comprends pas pourquoi la proposition de Ubiquité dans le message #3 a été écartée aussi rapidement.

Il est vrai qu’elle est exposée succintement et maladroitement: il ne s’agit pas de concaténer deux listes et de LES trier,
mais de concaténer deux listes et de trier LA liste résultante.

C’est sans doute le minimalisme de cette explication qui lui vaut la réponse que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

L'algorithme initial correspond déjà au dernier pas d'un tri-fusion.

Mais au risque de paraître débile, je ne vois pas où il y a un tri-fusion dans l’exposé du problème, ni dans le code du message #1. Dans le code il est dit que la liste de chaque structure Mot sera triée pour facilter le traitement; bon d’accord les listes sont donc triées avant de les passer à la fonction unsigned int nbCommunes(). Mais ensuite, dans la fonction, il n’y a qu’un décompte, pas de réorganistion de tableaux......




Donc moi je trouve l’idée de Ubiquité bonne:
T1 = (a,b,c,d,e,f,g,h,i,j,k)
T2 = (f,w,t,k,e,r,p,x,a,u)
On concaténe T1 et T2:
T vaut (a,b,c,d,e,f,g,h,i,j,k,f,w,t,k,e,r,p,x,a,u)
On trie T => T vaut:
(a,a,b,c,d,e,e,f,f,g,h,i,j,k,k,w,t,r,p,x,u)
On passe T à la moulinette:
- on initialise un compteur count à 0
- du second élément (d’index 1) de T au dernier élément, on compare chaque élément au précédent: s’ils sont identiques on incrémente count de 1

En Python, ça donne:

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
T1 = ['a','b','c','d','e','f','g','h','i','j','k']
T2 = ['f','w','t','k','e','r','p','x','a','u']
 
T = T1 + T2
T.sort()
print T
 
count = 0
x = T[0]
for y in T[1:]:
    if y==x:
        print y
        count = count + 1
    x = y
 
print count

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
['a', 'a', 'b', 'c', 'd', 'e', 'e', 'f', 'f', 'g', 'h', 'i', 'j', 'k', 'k', 'p', 'r', 't', 'u', 'w', 'x']
a
e
f
k
4

Bien sûr , en C il faudra un peu plus de code: déclaration de variables, gestion des pointeurs ou de la mémoire, et surtout codage du tri sans doute en dur, sans faire appel à une fonction toute prête. Je ne sais pas exactement, je ne connais pas C. Mais dans le principe, je ne vois pas ce que ça aurait de plus difficile.

Les impressionnants développements dans lesquels vous vous êtes lancés me font douter que cette solution aussi simple corresponde bien au problème posé. Ne connaissant pas C, il y a peut être quelque chose qui m’échappe.









Troisièmement,
si la proposition ci-dessus est valide pour la détermination du nombre de co-occurences de deux mots( = nombre de lignes communes à deux mots), ou trois, dans les mêmes lignes,
et si on peut envisager répéter le processus pour comparer 2 à 2 un petit nombre de mots,
il est toutefois certain que quand on veut déterminer les co-occurences de 2 mots extraits d’un vaste ensemble de mots (issus d’un texte de 500000 lignes), ce n’est plus jouable.

Le problème m’a alors fait pensé aux solutions avec emploi de dictionnaire apportées dans le cadre de la discussion suivante:
http://www.developpez.net/forums/d65...-fichier-long/
particulièrement à partir du message #46 de cette file.


La fabrication de structures Mot (une par mot) à partir du fichier X résulte en effet en une perte d’information par rapport au fichier X:

si je ne me suis pas trompé en disant que le tableau lignes d’une structure contient une sélection de lignes du fichier X, et non pas toutes les lignes, cela veut dire que le numéro d’ordre d’une ligne dans un tableau lignes n’est plus le même que son niuméro d’ordre dans le fichier X, et d’autre part, une ligne donnée va avoir des index différents dans le tableau lignes selon la structure Mot que l’on va considérer. On ne peut donc pas faire des comparaisons basées sur les index des mots dans les tableaux lignes. C’est dommage.


Restons donc au niveau du fichier x. Je suppose qu’il contient par exemple le texte:
1 - A B C E G H
2 - A B C D F
3 - C D F G H
4 - D E F G
5 - A F G H
6 - B G H

les 1 2 3 4 5 6 étant les numéros de lignes.

Construisons à partir de ce fichier le dictionnaire référençant les numéros de lignes en fonctions des mots existant dans le texte.
A : 1 2 5
B : 1 2 6
C : 1 2 3
D : 2 3 4
E : 1 2
F : 2 3 4 5
G : 1 3 4 5 6
H : 1 3 5 6

Si maintenant on veut connaître le lignes communes contenant à la fois les mots B et G, c’est simple on intersecte
(1 , 2 , 6) et ( 1 , 3 , 4 , 5 , 6)
ce qui donne
(1 , 6)


La constitution de ce dictionnaire ne nécessite qu’un passage dans le texte: à chaque ligne on enregistre le numéro d’ordre de la ligne dans le dictionnaire aux clés qui sont les mots présents dans la ligne examinée.


Pour chaque couple de mots dont on veut le nombre de co-occurences, il reste à faire l’intersection selon un procédé comme dans mon deuxièmement ou un autre, ceci ne change pas. Mais on s’évite un parcours de deux tableaux lignes à chaque fois, même s’ils sont moins grands que le fichier original. Et on s’épargne aussi le travail de constitution des structures Mot pour tous les mots.


Enfin bref, ma proposition correspond à ta conclusion:

l'optimisation n'était pas à faire dans la fonction, mais dans le design du programme.

Je suis par ailleurs intéressé de connaître quel type de moyen tu as trouvé pour

diminuer significativement le nombre d'appel à cette fonction.

[LittleWhite]

Tout d'abord interessante réponse. J'ai eu juste un peu de mal à suivre, mais ça, c'est le problème de mon cerveau.

Je crois avoir compris que le champ lignes d’une structure Mot est un tableau contenant certaines lignes seulement d’un fichier X extérieur à Mot, à savoir les lignes de X comportant le char* mot;
Il n’y a donc pas d’extraction de lignes à faire de X pour obtenir cette liste, elle est déjà là toute prête dans une structure Mot.

De ce fait on n’a à se préoccuper ni de ce qu’est le fichier X, ni de ce qu’est char* mot; , ni de la nature de ce que contient le tableau d’une structure Mot : au plus simple, on peut dire qu’un tel tableau lignes contient des éléments sans se préoccuper de les connaître précisément, et il suffit de savoir qu’on peut comparer les éléments de deux tableaux de structures Mot.

Ainsi reformulé, je comprends alors le problème ainsi:

soient deux tableaux de structures Mot
T1 = (a,b,c,d,e,f,g,h,i,j,k)
T2 = (f,w,t,k,e,r,p,x,a,u)
il faut extraire l’information que (a,e,f,k) est l’ensemble des éléments communs aux deux tableaux.

Est-ce bien ça ?
Si c’est le cas, je me permets d’apporter mon grain de sel.

Oui c'est bien ça .

Premièrement,
n’y a-t-il pas en langage C un moyen de tester si un truc donné appartient à une structure ou non , au lieu de passer en revue tous les éléments de la structure et tester s’il y a égalité de chacun avec le truc en question ?

C’est à dire, n’y a-t-il rien de mieux comme instruction que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if ( mot1->lignes.tableau[compteur1] == mot2->lignes.tableau[compteur2] )

pour savoir si mot1->lignes.tableau[compteur1]
est dans mot2->lignes.tableau ?

Car je suppose que
mot1->lignes.tableau[compteur1] désigne l’élément du tableau de mot1 qui se trouve repéré par l’index compteur1
et que mot2->lignes.tableau[compteur2] est l’élément du tableau de mot2 repéré par compteur2.

Une expression du genre
if ( mot1->lignes.tableau[compteur1] in mot2->lignes.tableau )
n’existe-t-elle pas en C ?


Je sens que vous allez trouver cette question idiote dans le cadre de C: vous allez me répondre que l’instruction que j’écris avec in est une instruction typique d’un langage du haut niveau et que C, étant un langage du bas niveau, ne peut pas faire autre chose que le boulot précis que l’instruction avec in recouvre.
Tapez pas trop fort, je suis contaminé par les facilités de Python.

Non, il n'y a pas de facilité comme celle ci dans le C ( sinon, on me l'a bien caché ). De plus, d'après moi, ce que fait in, est surement très proche de ce que je fais ( en mieux optimiser, peut être ).

Secondement,
je ne comprends pas pourquoi la proposition de Ubiquité dans le message #3 a été écartée aussi rapidement.

Il est vrai qu’elle est exposée succintement et maladroitement: il ne s’agit pas de concaténer deux listes et de LES trier,
mais de concaténer deux listes et de trier LA liste résultante.

C’est sans doute le minimalisme de cette explication qui lui vaut la réponse que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

L'algorithme initial correspond déjà au dernier pas d'un tri-fusion.

Mais au risque de paraître débile, je ne vois pas où il y a un tri-fusion dans l’exposé du problème, ni dans le code du message #1. Dans le code il est dit que la liste de chaque structure Mot sera triée pour facilter le traitement; bon d’accord les listes sont donc triées avant de les passer à la fonction unsigned int nbCommunes(). Mais ensuite, dans la fonction, il n’y a qu’un décompte, pas de réorganistion de tableaux......




Donc moi je trouve l’idée de Ubiquité bonne:
T1 = (a,b,c,d,e,f,g,h,i,j,k)
T2 = (f,w,t,k,e,r,p,x,a,u)
On concaténe T1 et T2:
T vaut (a,b,c,d,e,f,g,h,i,j,k,f,w,t,k,e,r,p,x,a,u)
On trie T => T vaut:
(a,a,b,c,d,e,e,f,f,g,h,i,j,k,k,w,t,r,p,x,u)
On passe T à la moulinette:
- on initialise un compteur count à 0
- du second élément (d’index 1) de T au dernier élément, on compare chaque élément au précédent: s’ils sont identiques on incrémente count de 1

En Python, ça donne:

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
T1 = ['a','b','c','d','e','f','g','h','i','j','k']
T2 = ['f','w','t','k','e','r','p','x','a','u']
 
T = T1 + T2
T.sort()
print T
 
count = 0
x = T[0]
for y in T[1:]:
    if y==x:
        print y
        count = count + 1
    x = y
 
print count

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
['a', 'a', 'b', 'c', 'd', 'e', 'e', 'f', 'f', 'g', 'h', 'i', 'j', 'k', 'k', 'p', 'r', 't', 'u', 'w', 'x']
a
e
f
k
4

Bien sûr , en C il faudra un peu plus de code: déclaration de variables, gestion des pointeurs ou de la mémoire, et surtout codage du tri sans doute en dur, sans faire appel à une fonction toute prête. Je ne sais pas exactement, je ne connais pas C. Mais dans le principe, je ne vois pas ce que ça aurait de plus difficile.

Les impressionnants développements dans lesquels vous vous êtes lancés me font douter que cette solution aussi simple corresponde bien au problème posé. Ne connaissant pas C, il y a peut être quelque chose qui m’échappe.

En c, nous avons un tri qui est super facile à utiliser ( je l'utilise déjà souvent dans mon programme ) qui est sous la forme d'une fonction appelé qsort(). De mémoire, elle fait un quicksort() qui est quand même assez rapide.
Sauf que entre ma solution, et la votre:
La mienne si je ne me trompe pas à une complexité de O(m + n) ( ou m et n sont les tailels des tableaus ).
Alors que vous, vous faite un tri. J'ose croire que le tri sera plus lent. ( Je ne me rapelle plus de la complexité ).
Et puis, après, vous comptez les elements, donc un parcours des deux tableaux, donc on revient à O(n + m). Donc je pense que c'est plus lent

Troisièmement,
si la proposition ci-dessus est valide pour la détermination du nombre de co-occurences de deux mots( = nombre de lignes communes à deux mots), ou trois, dans les mêmes lignes,
et si on peut envisager répéter le processus pour comparer 2 à 2 un petit nombre de mots,
il est toutefois certain que quand on veut déterminer les co-occurences de 2 mots extraits d’un vaste ensemble de mots (issus d’un texte de 500000 lignes), ce n’est plus jouable.

Le problème m’a alors fait pensé aux solutions avec emploi de dictionnaire apportées dans le cadre de la discussion suivante:
http://www.developpez.net/forums/d65...-fichier-long/
particulièrement à partir du message #46 de cette file.


La fabrication de structures Mot (une par mot) à partir du fichier X résulte en effet en une perte d’information par rapport au fichier X:

si je ne me suis pas trompé en disant que le tableau lignes d’une structure contient une sélection de lignes du fichier X, et non pas toutes les lignes, cela veut dire que le numéro d’ordre d’une ligne dans un tableau lignes n’est plus le même que son niuméro d’ordre dans le fichier X, et d’autre part, une ligne donnée va avoir des index différents dans le tableau lignes selon la structure Mot que l’on va considérer. On ne peut donc pas faire des comparaisons basées sur les index des mots dans les tableaux lignes. C’est dommage.

Cela ne serai pas revenu au champs de bits proposé juste avant?

Restons donc au niveau du fichier x. Je suppose qu’il contient par exemple le texte:
1 - A B C E G H
2 - A B C D F
3 - C D F G H
4 - D E F G
5 - A F G H
6 - B G H

les 1 2 3 4 5 6 étant les numéros de lignes.

Construisons à partir de ce fichier le dictionnaire référençant les numéros de lignes en fonctions des mots existant dans le texte.
A : 1 2 5
B : 1 2 6
C : 1 2 3
D : 2 3 4
E : 1 2
F : 2 3 4 5
G : 1 3 4 5 6
H : 1 3 5 6

Si maintenant on veut connaître le lignes communes contenant à la fois les mots B et G, c’est simple on intersecte
(1 , 2 , 6) et ( 1 , 3 , 4 , 5 , 6)
ce qui donne
(1 , 6)


La constitution de ce dictionnaire ne nécessite qu’un passage dans le texte: à chaque ligne on enregistre le numéro d’ordre de la ligne dans le dictionnaire aux clés qui sont les mots présents dans la ligne examinée.


Pour chaque couple de mots dont on veut le nombre de co-occurences, il reste à faire l’intersection selon un procédé comme dans mon deuxièmement ou un autre, ceci ne change pas. Mais on s’évite un parcours de deux tableaux lignes à chaque fois, même s’ils sont moins grands que le fichier original. Et on s’épargne aussi le travail de constitution des structures Mot pour tous les mots.

Avoir mes mots me semble une meilleure idée car je n'ai pas que cette utilisation dans tout le programme. Mais il faut dire que c'est la partie que je n'ai pas trop compris. Veuillez m'en excuser.
[/QUOTE]

Juste que au début, je faisait un check, de tout les mots du fichiers, et que après un éclair de lucidité, j'ai compris que je n'avais pas besoin de vérifié tout le fichier de manière méthodique et idiote, mais juste les mots qu'il me restait dans ma tables de hachages.
Sachez que d'un fichier qui contient 15Milliards de mots, il n'y en a que ~77000 d'unique. Donc il est quand même beaucoup mieux de faire les calculs qu'une seule fois ...
( Vous pouvez me traiter de boulet, je le comprendrai très bien ).
( C'est aussi pour cela que je m'excuse d'avoir pris votre temps sur cette discussion ( fertile certes )).

[mikhailo]

Salut,

Désolé pour le lagtime =) En fait, mon projet était bien moins complexe que ce que tu fais, donc je ne pense pas que tu serais intéressé par mon code. Ton travail a l'air intéressant, par contre! Pourrais-tu en dire plus sur l'objectif global que tu cherches à atteindre? Sauf si top secret, bien sûr

[Médinoc]

Les tableaux sont triés à la fin de leur construction, lorsqu'on est sûr qu'ils ne changeront plus. Ils sont également "purifiés" de leur doublons, normalement. Ceci se fait avant que démarre le parcours pour les comptages.

S'il était question d'une simple recherche de la première ligne commune, on pourrait peut-être s'en sortir sans parcours, mais comme il s'agit ici de comptage, je pense que le parcours linéaire des tableaux triés (complexité: O(m + n)) reste le meilleur algorithme.

PS: Pour info, il existe en C deux fonctions de recherche dans un tableau, bsearch() et lsearch() (respectivement trié et non-trié). Mais ici, je doute qu'elles soient plus rapide que ce qu'on utilise.

[étoile de mer]

Salut,

Désolé pour le lagtime =) En fait, mon projet était bien moins complexe que ce que tu fais, donc je ne pense pas que tu serais intéressé par mon code. Ton travail a l'air intéressant, par contre! Pourrais-tu en dire plus sur l'objectif global que tu cherches à atteindre? Sauf si top secret, bien sûr

Bonjour Mikhailo,
LittleWhite et moi on bosse ensemble, donc je vais vous répondre.
on a deux gros fichier texte en français et en anglais comportant chacun 500K ligne.
Le but c'est d'extraire les mots distincts et pour chaque mot en français on calcule sa "probabilité " d'apparition avec chacun des mot en anglais, pour mesurer leurs corrélation.
Ça c'est grossomodo (sans entrer dans les détails ).

[mikhailo]

C'est-à-dire, on verrait, par exemple, si les mots utilisés souvent en français sont aussi souvent utilisés par nos amis anglophones? Et on pourrait, par exemple, savoir du coup si les écrivains francophones emploient plus souvent tel ou tel champ sémantique que les anglophones?

[étoile de mer]

oui, entre autre