Discussion :

[mido1951]

Bonjour,
voici mon problème:
j'ai des intervalles voici un exemple: [5,10],[30,90][70,89],[15,45],[67,87],[6,9].....

comme vous voyez l'intervalle [6,9] est inclut dans [5,10] et l'intervalle [70,89] est inclut dans [30,90] et [67,87] est inclut dans [30,90].
Moi je veux éliminer ces intervalles et bien en même temps diminuer la taille du tableau d'intervalles.
voici mon code:

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
void table_optimiser(ligne table[], int n){
int i=0;int j=0;int k=0;
    for(i=0;i<n;i++) //pour fixer chaque intervalle
    {
     for(j=1;j<n;j++) //pour parcourir les autres intervalles et trouver les intervalles inclut.
     {
        if((table[i].posin<=table[j].posin)&&(table[i].posend>=table[j].posend))
        {
            for (k=j;k<n;k++)
            {
               table[k]=table[k+1]; //pour parcourir le reste du tableau et éliminer l'intervalle inclut
            }
            n--;
        }
     }
    }
    for (j = 0; j < n; j++){affichage_table(table[j],j);}
}

est-ce que vous avez une idée? ou une autres approches?
Merci.

[ternel]

Par exemple, tu pourrais faire une fonction qui détermine l'intersection de deux ensembles, et une autre qui détermine si un ensemble contient un autre.
Ca simplifierait la suite du code.

Tu devrais te pencher sur les listes chainées, plutot que les tableaux.

[mido1951]

est-ce que ma solution n'est pas exacte?

[ternel]

exacte, si, ca a l'air, mais elle te coute très très cher.
Alors que tu pourrais avoir une liste (triée?) qui diminuerait la complexité du traitement.

Et en passant par des sous fonctions, tu peux plus facilement tester (et prouver) ton code, et aussi t'en resservir

[mido1951]

exacte, si, ca a l'air, mais elle te coute très très cher.
Alors que tu pourrais avoir une liste (triée?) qui diminuerait la complexité du traitement.

Et en passant par des sous fonctions, tu peux plus facilement tester (et prouver) ton code, et aussi t'en resservir

même si la logique est exacte mais elle ne marche pas dans mon cas.

[Abacar94]

exacte, si, ca a l'air, mais elle te coute très très cher.
Alors que tu pourrais avoir une liste (triée?) qui diminuerait la complexité du traitement.

Et en passant par des sous fonctions, tu peux plus facilement tester (et prouver) ton code, et aussi t'en resservir

ta méthode est plus professionnel.........tu pourrais lui donner un début de code pour qu'il puisse l'essayer; histoire qu'il vois la différence

[stendhal666]

Premier point, comme le dit leternel, la question n'est pas seulement de savoir si un intervalle en inclut un autre mais de savoir s'il y a intersection entre eux: on peut simplifier [5, 10] et [8, 12] par [5, 12].

Si le tableau est trié la fusion des intervalles se fait en un seul passage. Le tri prend grosso modo n×log n donc au total tu as n*(log n + 1) tandis que tu es à n^3 à première vue.

[foetus]

on peut simplifier [5, 10] et [8, 12] par [5, 12].

Cela dépend du terme "inclusion"

Par exemple, prenons 3 intervalles [30,90], [25,55], [15,45]

L'intervalle [25, 55] est inclus dans l'union [15,45] U [30,90], mais pas inclus ni dans [30,90] ni dans [15,45].
Donc on ne devrait pas l'exclure.

[ternel]

Pour donner du code, il faudrait que je me remette sérieusement à écrire du C.
C'est un bon exercice je verrai ca ce soir, je pense

[ternel]

Dans ton code, il y a un gros soucis:
Ton commentaire dit://pour parcourir les autres intervalles et trouver les intervalles inclut..
C'est très bien, mais où est le code qui dit "autres"?

Quand tu auras résolu ca, ton problème précis sera corrigé

[stendhal666]

Je vois que la discussion est résolue, mais comme le problème m'a intéressé... si l'on n'écarte que les intervalles effectivement inclus, sans fusionner les intervalles qui se recoupent partiellement, l'algorithme est plus compliqué. J'en ai trouvé un qui a le défaut d'être moche, mais qui est incomparablement plus rapide que l'algorithme basique de mido1951 (je l'ai corrigé et comparé au mien: la différence est peu sensible tant que le nombre d'intervalles est faible, plus élevé ensuite (rapport de 1 à 10 pour 10 000 intervalles, de 1 à 75 pour 100 000, et pour 1 000 000, j'ai arrêté celui de mido1951 au bout d'une minute, il n'avait pas terminé -moins d'une seconde pour le mien). Il est en revanche d'autant plus favorable que la dispersion des intervalles est faible. Le voici. Il fonctionne sur un tableau d'intervalle trié (critère majeur: la taille de l'intervalle (plus faible en premier), critère mineur, l'indice de de départ (plus élevé en premier). La fonction de tri:

Code :

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

1
2
3
4
5
6
7
8
int ivl_cmp(const void* va, const void* vb) {
  const ivl *a = va;
  const ivl *b = vb;
  int asz = a->high - a->low, bsz = b->high - b->low;
  if (asz > bsz) return 1;
  if (asz < bsz) return -1;
  return b->low - a->low;
}

d'où:

Code :

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

qsort(ivls, ni, sizeof(*ivls), &ivl_cmp);

Ensuite le principe est de partitionner le tableau par des swaps successifs: après l'indice de partition, tous les intervalles inclus dans l'intervalle pivot. Puis je mets le pivot au début du tableau, en prenant soin de restaurer l'ordre de tri initial en déplaçant d'un cran vers la droite les éléments à gauche de la dernière position du pivot:

la fonction de partition:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int partition(ivl* tab, size_t len, int (*include_fn) (const ivl* a, const ivl* b)) {
  int ix = len-1, i, swapped = len-1; 
  ivl piv = tab[ix]; // on utilise comme pivot l'intervalle le plus grand
  if (len == 1) return 1;
  for (i = len-2; i >= 0; --i) {
    if (include_fn(&piv, &tab[i]))  {
      swap(&tab[i], &tab[ix--]); // on déplace dans les indices les plus à droite les intervalles inclus dans le pivot
      swapped = i; // on sauvegarde la dernière position du pivot
    }
  }
  memmove(tab+1, tab, swapped*(sizeof piv)); // on met le pivot au tout début en préservant l'ordre de tri des intervalles à gauche de sa dernière position
  *tab = piv;
  return len-ix; // len - ix (nv intervalles inclus)
}

La partition est contrôlée par la fonction de fusion des intervalles, qui restreint à chaque fois le tableau aux éléments restant à vérifier et renvoie in fine la longueur du tableau optimisé:

Code :

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

1
2
3
4
5
6
int ivlmerge(ivl* tab, int len) {
  int p;
  if (len < 2) return len; // 1 ou 0 élements, plus rien à faire
  p = partition(tab, len, &includes);
  return 1 + ivlmerge(tab+1, len-p); // tab+1 car le pivot à gauche n'est plus à vérifier, len - p (nombre d'éléments écartés par la partition) 
}

PS: j'utilise un compilateur C assez ancien, d'où les déclarations en début de fonction