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 :

Élimination intervalles inclus


Sujet :

C

  1. #1
    Membre très actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2011
    Messages
    317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Meuse (Lorraine)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2011
    Messages : 317
    Par défaut Élimination intervalles inclus
    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.

  2. #2
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    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.

  3. #3
    Membre très actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2011
    Messages
    317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Meuse (Lorraine)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2011
    Messages : 317
    Par défaut
    est-ce que ma solution n'est pas exacte?

  4. #4
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    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

  5. #5
    Membre très actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2011
    Messages
    317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Meuse (Lorraine)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2011
    Messages : 317
    Par défaut
    Citation Envoyé par leternel Voir le message
    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.

  6. #6
    Membre actif Avatar de Abacar94
    Homme Profil pro
    L2 Math-informatique
    Inscrit en
    Novembre 2015
    Messages
    103
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Niger

    Informations professionnelles :
    Activité : L2 Math-informatique

    Informations forums :
    Inscription : Novembre 2015
    Messages : 103
    Par défaut
    Citation Envoyé par leternel Voir le message
    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

  7. #7
    Membre Expert

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2013
    Messages
    610
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2013
    Messages : 610
    Billets dans le blog
    21
    Par défaut
    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.

  8. #8
    Expert confirmé
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    Juillet 2013
    Messages
    4 786
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 4 786
    Par défaut
    Citation Envoyé par stendhal666 Voir le message
    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.

  9. #9
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    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

  10. #10
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

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

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    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é

  11. #11
    Membre Expert

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Avril 2013
    Messages
    610
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2013
    Messages : 610
    Billets dans le blog
    21
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 22
    Dernier message: 03/03/2014, 16h16
  2. Réponses: 1
    Dernier message: 04/04/2013, 10h37
  3. Inclusion d'intervalles entiers et structure de donnée
    Par SpiceGuid dans le forum Langages fonctionnels
    Réponses: 8
    Dernier message: 03/05/2012, 15h50
  4. Tester l'inclusion d'une valeur dans un ensemble d'intervalle
    Par Benoit_T dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 22/06/2010, 16h19
  5. éliminer un caractere d'un string
    Par no-vice dans le forum Langage
    Réponses: 5
    Dernier message: 09/08/2002, 14h55

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