comparaison d'intervalles

Question

Bonjour, je cherche à faire correspondre des intervalles entre eux, je m'explique: - soit dans un premier fichier texte, disons file1.txt une suite d'intervalles de la forme: id1 3455 3463 id2 3535 3544 id3 3601 3608 id4 3622 3630 id5 3631 3913 id6 3631 3759 id7 3631 5899 id8 3760 3913 id9 3760 5630 id10 3996 4276 id11 4486 4605 id12 4706 5095 id13 5174 5326 .../... - dans un second fichier texte, disons file2.txt une aure suite d'intervalles de la forme: acc_2419732 3268 3285 acc_3041065 3565 3583 acc_362358 3640 3656 acc_3279485 3793 3813 acc_3091017 3794 3811 acc_2807380 3832 3848 acc_3105138 3832 3848 acc_3105139 3832 3848 acc_3105140 3832 3848 acc_3116450 3832 3848 acc_86708 3832 3848 acc_1987802 3922 3938 acc_1679660 4113 4129 acc_891489 4113 4129 acc_2829973 4299 4318 acc_298381 4603 4619 .../... la question est la suivante: quels sont les intervalles de mon fichier 2 (file2.txt) qui se retrouvent inclus parmi ceux du fichier 1 (file1.txt) ? en écrivant un simple script en awk (syntaxe assez proche du C): #!/usr/bin/awk -f #usage: myprog.awk file2.txt BEGIN { while((getline < "file1.txt") > 0){ cpt++ descr[cpt]=$1 start[cpt]=$2 end[cpt]=$3 } close("test.txt") } { j=1 while(start[j]<=$2 && j<=cpt){ if(end[j]>=$3){print $1,$2,$3,descr[j],start[j],end[j];j++} else{j++} } } on obtient comme résultat: acc_362358 3640 3656 id5 3631 3913 acc_362358 3640 3656 id6 3631 3759 acc_362358 3640 3656 id7 3631 5899 acc_3279485 3793 3813 id5 3631 3913 acc_3279485 3793 3813 id7 3631 5899 acc_3279485 3793 3813 id8 3760 3913 acc_3279485 3793 3813 id9 3760 5630 acc_3091017 3794 3811 id5 3631 3913 acc_3091017 3794 3811 id7 3631 5899 acc_3091017 3794 3811 id8 3760 3913 acc_3091017 3794 3811 id9 3760 5630 acc_2807380 3832 3848 id5 3631 3913 acc_2807380 3832 3848 id7 3631 5899 acc_2807380 3832 3848 id8 3760 3913 acc_2807380 3832 3848 id9 3760 5630 acc_3105138 3832 3848 id5 3631 3913 acc_3105138 3832 3848 id7 3631 5899 acc_3105138 3832 3848 id8 3760 3913 acc_3105138 3832 3848 id9 3760 5630 acc_3105139 3832 3848 id5 3631 3913 acc_3105139 3832 3848 id7 3631 5899 acc_3105139 3832 3848 id8 3760 3913 acc_3105139 3832 3848 id9 3760 5630 acc_3105140 3832 3848 id5 3631 3913 acc_3105140 3832 3848 id7 3631 5899 acc_3105140 3832 3848 id8 3760 3913 acc_3105140 3832 3848 id9 3760 5630 acc_3116450 3832 3848 id5 3631 3913 acc_3116450 3832 3848 id7 3631 5899 acc_3116450 3832 3848 id8 3760 3913 acc_3116450 3832 3848 id9 3760 5630 acc_86708 3832 3848 id5 3631 3913 acc_86708 3832 3848 id7 3631 5899 acc_86708 3832 3848 id8 3760 3913 acc_86708 3832 3848 id9 3760 5630 acc_1987802 3922 3938 id7 3631 5899 acc_1987802 3922 3938 id9 3760 5630 acc_1679660 4113 4129 id7 3631 5899 acc_1679660 4113 4129 id9 3760 5630 acc_1679660 4113 4129 id10 3996 4276 acc_891489 4113 4129 id7 3631 5899 acc_891489 4113 4129 id9 3760 5630à acc_891489 4113 4129 id10 3996 4276 acc_2829973 4299 4318 id7 3631 5899 acc_2829973 4299 4318 id9 3760 5630 acc_298381 4603 4619 id7 3631 5899. acc_298381 4603 4619 id9 3760 5630 ce qui est excellent. Sauf que lorsque mes deux fichiers dépassent les 100000 lignes le temps de calcul grandit de manière exponentielle, de telle sorte qu'il faut plus de 24h avant d'avoir le résultat. je rappelle que les deux fichiers sont triés suivant la deuxième colonne en ordre croissant. Y'aurait-il pas une méthode plus élégante de manière à obtenir une comparaison plus linéaire et non quadratique comme c'est le cas ici ? Merci.

cs_rt15 · Answer

Salut,

Heu désolé ton awk me file le mal de crâne. J'en ai pas fait assez visiblement.

Déjà pour optimiser, oublie le awk. Fait du C (Ou de l'assembleur).  Mais c'est vrai que ton gain ne sera que linéaire...

Ensuite, à ce que je comprend de ton awk, tu prend un interval de ton premier fichier, et tu parcourt ton deuxième fichier à la recherche d'une correspondance jusqu'à ce que start[j]<=$2.

Je pense que tu devrais te souvenir de là où tu te trouvais dans le fichier 2 au moment où tu passe d'un interval à l'autre dans le fichier 1. De manière à ne pas parcourir le début du fichier 2 à chaque fois, car tu sais que les intervalles du début de ton fichier 2 commencent trop tôt.

Hum. Pas sûr d'avoir été clair. Si j'y pense, je te ferais un bout de code demain.

cs_rt15 · Answer

Voilà un un bout de code. Pour l'algo global, je vois pas comment faire mieuX. Après on peut faire de optimes sur le code : 1) Utilisation de fonction perso pour le parsage. 2) Utilisation de fonctions systèmes pour la lecture du fichier, avec bufferisation pour limiter les appels. 3) Utilisation d'un cache pour par exemple ne parser qu'une seule fois les entrées du fichier 2. Et accessoirement, commenter les printf accélère certainement beaucoup le code ! Les gains peuvent être relativement important (Peut être deux fois plus rapide) en fonction des données en entrées. La consommation mémoire risque d'être plus importante aussi. Le code suivant fait ce que tu veux ? Les gains en perf sont important par rapport au awk ? Faut il aller plus loin dans les optimisations ?

#include int SafeOpenFile(char *lpFileName, char *lpMode, FILE **lpFile) { *lpFile = fopen(lpFileName, lpMode); if (! *lpFile) printf("Cannot open file: "%s" ", lpFileName); return (int)*lpFile; } int main(int argc, char **argv) { int nResult; FILE *lpF1; FILE *lpF2; FILE *lpFOut; char lpF1Desc[50]; int nF1Start; int nF1End; char lpF2Desc[50]; int nF2Start; int nF2End; long nPosInF2; nResult = 1; if (argc != 4) { printf("Trouve les intervalles inclus dans d'autres intervalles. "); printf("Intervalles fichier1 fichier2 fichier_de_sortie "); printf(" fichier1 Fichier contenant des intervalles. "); printf(" fichier2 Fichier contenant les intervalles qui doivent "); printf(" être inclus dans les intervalles de fichier1. "); printf(" fichier_de_sortie Fichier récupérant les résultats. "); goto the_end; } if (! SafeOpenFile(argv[1], "r", &lpF1)) goto the_end; if (! SafeOpenFile(argv[2], "r", &lpF2)) goto close_1; if (! SafeOpenFile(argv[3], "w", &lpFOut)) goto close_1_and_2; nPosInF2 = 0; while (! feof(lpF1)) { if (fscanf(lpF1, "%s %d %d", lpF1Desc, &nF1Start, &nF1End) != 3) break; printf("%s %d %d ", lpF1Desc, nF1Start, nF1End); fseek(lpF2, nPosInF2, SEEK_SET); while (! feof(lpF2)) { if (fscanf(lpF2, "%s %d %d", lpF2Desc, &nF2Start, &nF2End) != 3) break; printf(" %s %d %d ", lpF2Desc, nF2Start, nF2End); /* Pas la peine de relire le fichier depuis le début */ if (nF2Start < nF1Start) nPosInF2 = ftell(lpF2); /* On s'arrête quand le début de l'interval 2 est supérieur à la fin du 1 */ if (nF2Start > nF1End) break; /* Test d'inclusion du deuxième intervalle dans le premier */ if ((nF2Start >= nF1Start) && (nF2End <= nF1End)) fprintf(lpFOut, "%s %d %d %s %d %d ", lpF1Desc, nF1Start, nF1End, lpF2Desc, nF2Start, nF2End); } } nResult = 0; fclose(lpFOut); close_1_and_2: fclose(lpF2); close_1: fclose(lpF1); the_end: return nResult; }

mslider · Answer

grand merci à toi rt15,
par contre j'ai un souci à la compil, il me dit çà:

interval.c: In function `SafeOpenFile`:
interval.c:9 warning: cast from pointer to integer of different size

malgré ce, le programme tourne bien.

je l'ai lancé sur deux gros fichiers: fichier1 ~ 100000 lignes et fichier2 ~ 800000 lignes
çà a pris 3 secondes (en virant les prinf au préalable).

tu vois une optimisation de ton coté ?

cs_rt15 · Answer

Visiblement tu travailles avec un système d'exploitation 64 bits. Tes int sont donc 32 bits mais tes pointeurs en font 64. Bilan quand j'essaie de convertir ton pointeur en int pour obtenir un pseudo booléen, je tronque le pointeur. Cela peut poser problème dans certains cas (très rares : il faut que les 32 bits de poid faible soit à 0) à l'exécution. Mais bon ça ferait que considérer que l'ouverture du fichier à échouée alors qu'elle à réussit. Pour corriger, j'aurais pu passer par un long, qui devrait avoir la même taille que pointeur. Mais le plus simple reste de renvoyer directement le FILE*...

FILE * SafeOpenFile(char *lpFileName, char *lpMode, FILE **lpFile) { *lpFile = fopen(lpFileName, lpMode); if (! *lpFile) printf("Cannot open file: "%s" ", lpFileName); return *lpFile; }

[troll] 3 seconde en C par rapport aux 24 heures de awk ??? Woah ! Bin je vais encore plus avoir la conscience tranquille la prochaine fois que je vannerais un langage interprété. Après on va me dire que ton awk et mon C n'ont pas tout à fait le même algo... Mais pourquoi est-ce toujours les développeur C qui trouvent les algos les plus rapides ? /troll Pour les optimisations encore possibles, voir mon post précédent. Mais il y a du boulot et c'est du code plutôt technique. Mais c'est vrai que je serais curieux de connaître les gains. Je vais voir si je peux te faire ça... Pour du Linux/Unix 64 bits j'imagine ? Par curiosité : c'est dans quel cadre que tu as besoin de faire ça ?

cs_rt15 · Answer

Avec l'amélioration : 3) Utilisation d'un cache pour par exemple ne parser qu'une seule fois les entrées du fichier 2. Je pense que c'est celle qui est susceptible de faire le plus gagner, bien que le gain dépende des données. J'espère qu'il n'y a pas de régression. Vérifie en comparant avec un fichier produit avec un code validé. Attention, ce code peut aussi provoquer une consommation très importante de la RAM en fonction des données. Je ne pense pas implémenter les autres optimisations.

#include #include #include typedef struct _RANGE { char lpDesc[50]; int nStart; int nEnd; } RANGE, *PRANGE; FILE *SafeOpenFile(char *lpFileName, char *lpMode, FILE **lpFile) { *lpFile = fopen(lpFileName, lpMode); if (! *lpFile) printf("Cannot open file: "%s" ", lpFileName); return *lpFile; } int main(int argc, char **argv) { int nResult; FILE *lpF1; FILE *lpF2; FILE *lpFOut; char lpF1Desc[50]; int nF1Start; int nF1End; PRANGE lpF2RangesBuffer; PRANGE lpTmp; int nBufferSize; int nIndexInBuffer; int nRangeCount; nResult = 1; if (argc != 4) { printf("Trouve les intervalles inclus dans d'autres intervalles. "); printf("Intervalles fichier1 fichier2 fichier_de_sortie "); printf(" fichier1 Fichier contenant des intervalles. "); printf(" fichier2 Fichier contenant les intervalles qui doivent "); printf(" être inclus dans les intervalles de fichier1. "); printf(" fichier_de_sortie Fichier récupérant les résultats. "); goto the_end; } if (! SafeOpenFile(argv[1], "r", &lpF1)) goto the_end; if (! SafeOpenFile(argv[2], "r", &lpF2)) goto close_1; if (! SafeOpenFile(argv[3], "w", &lpFOut)) goto close_1_and_2; nBufferSize = 200; lpF2RangesBuffer = (PRANGE)malloc(sizeof(RANGE) * nBufferSize); nRangeCount = 0; while (! feof(lpF1)) { if (fscanf(lpF1, "%s %d %d", lpF1Desc, &nF1Start, &nF1End) != 3) break; /* Nettoyage du cache */ for (nIndexInBuffer = 0; nIndexInBuffer < nRangeCount; nIndexInBuffer++) if (lpF2RangesBuffer[nIndexInBuffer].nStart >= nF1Start) break; if (nIndexInBuffer > 0) { nRangeCount = nRangeCount - nIndexInBuffer; memmove(lpF2RangesBuffer, &lpF2RangesBuffer[nIndexInBuffer], sizeof(RANGE) * (nRangeCount)); } nIndexInBuffer = 0; while ((! feof(lpF2)) || (nIndexInBuffer < nRangeCount)) { /* Si on a pas l'enregistrement dans le buffer */ if (nIndexInBuffer >= nRangeCount) { /* Si on a remplit le cache, il faut en allouer un nouveau */ if (nRangeCount >= nBufferSize) { nBufferSize = nBufferSize * 2; lpTmp = (PRANGE)malloc(sizeof(RANGE) * nBufferSize); memcpy(lpTmp, lpF2RangesBuffer, sizeof(RANGE) * (nRangeCount)); free(lpF2RangesBuffer); lpF2RangesBuffer = lpTmp; } /* Mise en cache de l'enregistrement */ if (fscanf(lpF2, "%s %d %d", lpF2RangesBuffer[nIndexInBuffer].lpDesc, &lpF2RangesBuffer[nIndexInBuffer].nStart, &lpF2RangesBuffer[nIndexInBuffer].nEnd) != 3) break; nRangeCount++; } /* Interval du fichier 2 trop petit, on oublie */ if (lpF2RangesBuffer[nIndexInBuffer].nStart < nF1Start) { nIndexInBuffer = 0; nRangeCount = 0; continue; } /* On s'arrête quand le début de l'interval 2 est supérieur à la fin du 1 */ if (lpF2RangesBuffer[nIndexInBuffer].nStart > nF1End) break; /* Test d'inclusion du deuxième intervalle dans le premier */ if ((lpF2RangesBuffer[nIndexInBuffer].nStart >= nF1Start) && (lpF2RangesBuffer[nIndexInBuffer].nEnd <= nF1End)) fprintf(lpFOut, "%s %d %d %s %d %d ", lpF1Desc, nF1Start, nF1End, lpF2RangesBuffer[nIndexInBuffer].lpDesc, lpF2RangesBuffer[nIndexInBuffer].nStart, lpF2RangesBuffer[nIndexInBuffer].nEnd); nIndexInBuffer++; } } free(lpF2RangesBuffer); nResult = 0; fclose(lpFOut); close_1_and_2: fclose(lpF2); close_1: fclose(lpF1); the_end: return nResult; }

mslider · Answer

bien vu pour le pointeur 64 bits

de la RAM j'en ai 16Go, ya pas de risque de ce coté là.
bon j'ai fais les tests avec les deux versions de code, voilà le verdict:

time sur prog1:
1.851u 0.308s 0:02.16 99.5%     0+0k 0+0io 0pf+0w

time sur prog2 (celui avec le cache):
1.281u 0.230s 0:01.52 99.3%     0+0k 0+0io 0pf+0w

j'avoue que awk fait triste mine à coté, faut dire qu'il est pas du tout optimisé mon code, on en reparlera qd j'aurais calqué
ton algo en awk. Je sais que C sera plus rapide c sur.
Faut pas critiquer Awk il a le même père que C: Brian Kernighan.

Sinon pour revenir à ta question du  pourquoi du comment, c pour la biologie que j'en ai besoin, la seule matière où on se retrouve
à analyser des fichiers texte de taille avoisinant le Go. Du coup faut de la puissance informatique derrière.

au fait en C++ en utilisant un segment tree, çà le ferait pas un poil plus vite encore ?

cs_rt15 · Answer

Houch. Ca c'est du PC. Vais me mettre à la biolo moi.

C++/segment tree -> Ce serait nettement plus lent je pense.
Déjà d'une manière général, le C++ est plus lent que le C (Même en exploitant ses capacités de meta prog, d'après mes essais).
Rien n'empêche de faire un segment tree en C.

Mais surtout, tu es ici dans un cas très particulier : tes fichiers sont triés ! Bilan monter un arbre ferait perdre plus de temps qu'il n'en ferait gagner.

Si un de tes fichier n'était pas trié ce serait une toute autre histoire.

mslider · Answer

oui c vrai tu as raison mes fichiers sont triés, heureusement.
bon en tous cas merci pour ta rapidité d'exécution et ton professionalisme, tu m'as l'air rudement calé en C.
Si c pas indiscrêt tu fais quoi comme job ?
c bête j'aimerais avoir plus de temps pour approfondir ce langage, il me faudrait une année sabatique pour m'y mettre à fond.
Mais j'hésite, certains dise que le C++ est plus performant dans certains cas, d'autres comme toi l'inverse.
je sais pas, peut être dont on avoir fait le tour du C avant de se pencher sur le C++.

cs_rt15 · Answer

Je suis ingénieur en informatique, et à la base développeur autodidacte.

Mais je t'ai pas dit : je facture mes prestations 60 euros.

[quote=mslider]
Mais j'hésite, certains dise que le C++ est plus performant dans certains cas, d'autres comme toi l'inverse.
/quote

La syntaxe et les librairies du C++ permettent de faire certaines choses avec moins de code que si on le faisait en pur C.

Mais sur le plan des performances à l'exécution, je n'ai pas trouvé de cas où il est meilleur, même dans des cas où il est censé l'être.
(Dernier post de ce thread).

En informatique, il est facile de dire tel ou tel chose, style écrire sur le web : "Le Java est presque aussi rapide que le C".
Mais si on fait des vrais tests, on s'aperçoit que le certaines personne on une idée particulière du "presque".

[quote=mslider]
je sais pas, peut être dont on avoir fait le tour du C avant de se pencher sur le C++.
/quote

Ca c'est la voix de la raison ! Le C++ étant globalement un sur-ensemble du C, il vaut mieux commencer par le C.

mslider · Answer

et bien moi javapasbien.
java faut pas m'en parler, qd j'étais en DESS on nous a fait apprendre ce langage de prog plutot que d'apprendre le C.
aujourd'hui encore on continu à enseigner ce langage objet digne héritier de Smaltalk. 
Pour moi c'est une grosse usine à gaz, avec des librairies, des constructeurs et des méthodes comme s'il en pleuvait.
je prefere le purisme de C de loin, c'est plus carré.
Et puis résultat des courses aujourd'hui j'ai plus besoin d'un langage comme C ou C++ que de Java.

Comparaison d'intervalles

10 réponses

Votre réponse

Discussions similaires