Probleme pour comparer des intervalles

Version imprimable

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):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #!/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.

Bonjour et bienvenu,
Si je retiens l'hypothèse que tes deux fichiers sont triés selon la borne inférieur de l'intervalle, tu dois pouvoir simplifier en parcourant 'simultanément' les deux fichiers :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Intervale_fic_1 = premier intervalle du fichier 1 Intervale_fic_2 = premier intervalle du fichier 2 tant que (Intervale_fic_1!= dernier intervalle du fichier 1) et (Intervale_fic_2!= dernier intervalle du fichier 2) si Intervale_fic_2 est inclus dans Intervale_fic_1 rajouter Intervale_fic_2 au résultat ++Intervale_fic_2 sinon si Intervale_fic_2.borne Inferieur < Intervale_fic_1.Borne inferieur ++Intervale_fic_2 sinon ++Intervale_fic_1 fin si fin si fin tant que
à vérifier mais l'idée est là. C'est l'idée utilisée dans la STL pour l'algo d'union

Salut,

Si tes deux fichiers sont triés, tu peux envisager de, tout simplement, récupérer tes données dans une collection "qui va bien" (par exemple, la std::list) et utiliser directement la fonction set_intersection fournie par le standard...

Cela pourrait se traduire par un code proche de

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
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
struct Data
{
    std::string id;  // l'identifiant
    size_t begin; // la valeur de depart de l'intervale
    size_t end; // la valeur de fin d'intervale
    /* l'algorithme a juste besoin de pouvoir comparer deux structures
     * afin de déterminer si la première est plus petite que la deuxième
     */
    bool operator<(Data const& d2)
    {
        /* Ce qui va bien pour assurer que l'objet en cours est plus petit
         * que l'objet "d2"
         */
    }
};
 
void foo(std::string const& file1, std::string const& file2)
{
    std::ifstream first(file1.c_str());
    std::ifstream second(file2.c_str());
    std::list<Data> firstData; // la liste des données du premier fichier
    std::list<Data> secondData; // la liste des données du deuxième fichier
    std::string temp;
    while(std::getline(first, temp)) // tant qu'il y a des valeurs à récupérer
                                     // dans le premier fichier
    {
        // nous convertissons les informations
        std::stringstream ss;
        ss<<temp;
        Data dat;
        ss>>dat.id>>dat.begin>>dat.end;
        // et nous insérons la données dans la première liste
        firstData.push_back(dat);
        /* juste l'affichage de l'objet récupéré, pour nous assurer qu'il a
         * été correctement lu 
         */
        std::cout<<"lu "<<dat.id<<"\t"<<dat.begin<<"\t"<<dat.end<<std::endl;
    }
    /* ceci aussi n'est qu'une vérification visuelle ;) */
    std::cout<<firstData.size()<<" donnees lues dans le premier fichier"
             <<std::endl;
    while(std::getline(second, temp)) // tant qu'il y a des valeurs à
                                      // récupérer dans le deuxième fichier
    {
        // nous convertissons les informations
        std::stringstream ss;
        ss<<temp;
        Data dat;
        ss>>dat.id>>dat.begin>>dat.end;
        // et nous insérons la données dans la deuxième liste
        secondData.push_back(dat);
        /* juste l'affichage de l'objet récupéré, pour nous assurer qu'il a
         * été correctement lu 
         */
        std::cout<<"lu "<<dat.id<<"\t"<<dat.begin<<"\t"<<dat.end<<std::endl;
    }
    std::cout<<secondData.size()<<" donnees lues dans le deuxieme fichier "
             <<std::endl;
    /* Nous allons utiliser un vector pour le résultat car il permet l'acces
     * aléatoire aux itérateurs...
     *
     * Nous savons que, quoi qu'il arrive, il sera composé d'un nombre 
     * d'éléments au 
     * maximum égal au nombre le plus petit d'élément des deux listes
     */
    std::vector<Data> result(secondData.size()< firstData.size()?
                             secondData.size() : firstData.size());; 
    /* set_intersection renvoie un itérateur sur le dernier élément placé 
     * ... profitons-en ;)
     */
    std::vector<Data>::iterator it = std::set_intersection(
                                     firstData.begin(), firstData.end(),
                                     secondData.begin(),secondData.end(),
                                     result.begin());
    /* affichons le nombre d'éléments similaires trouvés */
    std::cout<<int(it-result.begin())<<" elements similaires trouves"
             <<std::endl;
}

Cette fonction nécessite l'inclusion du fichier d'en-tête algorithm, en plus des fichiers d'en-têtes nécessaires pour la gestion des chaines de caractères (<string>), des flux de fichiers (<fstream>), des flux de conversion (<sstream>), des entrées/sorties standards (<iostream>), des listes (<list>) et des vecteur (<vector>)

31/03/2009, 17h24
3DArchi

Citation:

Envoyé par koala01

Salut,

Si tes deux fichiers sont triés, tu peux envisager de, tout simplement, récupérer tes données dans une collection "qui va bien" (par exemple, la std::list) et utiliser directement la fonction set_intersection fournie par le standard...

Je crois que c'est un problème de perf, donc tout charger en mémoire n'est peut être pas possible/souhaitable.
31/03/2009, 21h31
mslider

réponse

merci Koala01 pour ta réponse mais vu que je suis débutant en C++,
je pense pas pouvoir maitriser les structures dont tu parles.
Je pensais à une réponse un peu plus simple.
Archid est ce que tu pourrais formuler ton algorithme en utilisant du pseudo-code, comme des boucles while, des if et des else, sans pour autant tenir
compte des initialisations de variables et autres précisions.

Merci

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Intervale_fic_1 <- Lire premier intervalle du fichier 1
Intervale_fic_2 <- Lire premier intervalle du fichier 2
tant que (on n'est pas à la fin du fichier 1) et (on n'est pas à la fin du fichier 2)
      si Intervale_fic_2 'est inclus' dans Intervale_fic_1
              rajouter Intervale_fic_2 au résultat
              Intervale_fic_2 <-Lire intervalle suivant
       sinon 
          si Intervale_fic_2.borne Inferieur < Intervale_fic_1.Borne inferieur
                Intervale_fic_2 <- Lire intervalle suivant
          sinon
                Intervale_fic_1<-Lire intervalle suivant
           fin si
       fin si
fin tant que
'est inclus' := Borne min de intervalle_fic2 >(=?) borne min de intervalle_fic1 ET Borne max de intervalle_fic2 <(=?) borne max de intervalle_fic1

01/04/2009, 11h31
koala01
Citation:

Envoyé par mslider

merci Koala01 pour ta réponse mais vu que je suis débutant en C++,
je pense pas pouvoir maitriser les structures dont tu parles.

Le fait est que l'idéal reste de toujours prendre dés le départ les bonnes habitudes...

Or, si on ne t'oriente pas correctement vers les bonnes solutions (utilisation de std::string, std::ifstream, std::stringstream), tu risque de recourir à des souvenirs de l'époque où tu apprenais le C, et de partir sur des développements "branlants" (car beaucoup trop inspirés du C)...

C'est pourquoi, je ne peux que t'inciter très fortement à t'intéresser dés le départ aux classes fournies par le standard, telles que les chaines de caractères (string), les flux de fichiers, les flux de conversion et les différents conteneurs.

Et ce d'autant plus que ces différentes classes te serviront tout au long de ta vie de programmeur C++ et te la faciliteront énormément ;)

Il n'est pas forcément nécessaire, dans un premier temps, d'étudier par coeur toutes les possibilités qui te sont offertes par le langage, mais il est clairement utile de t'intéresser en priorité à ce qu'il te faut connaitre pour atteindre ton objectif ou pour te permettre de faire le choix "le meilleur"...

Tu trouvera dans la FAQ une série de réponses à la plupart des questions que tu pourrais te poser... Profites en ;)

Citation:

Je pensais à une réponse un peu plus simple.

Archid est ce que tu pourrais formuler ton algorithme en utilisant du pseudo-code, comme des boucles while, des if et des else, sans pour autant tenir
compte des initialisations de variables et autres précisions.

Merci

Quel que soit l'algorithme utilisé, il faut bien te rendre compte que, de toutes manières, tu devras:
- manipuler des fichiers pour lire
- convertir ce que tu a lu dans le fichier en une structure "qui va bien"
- effectuer des comparaisons
Tu auras donc fatalement besoin des flux de fichiers, des chaines de caractères (qui restent le meilleur moyen de lire des informations dans un flux), des flux de conversions (qui restent le meilleur moyen de convertir une chaine de caractères en autre chose et vice-versa), d'au moins un conteneur (qui reste le meilleur moyen de gérer des collections d'objets) et d'au moins une structure personnalisée capable de représenter les informations que tu auras récupérées ;)