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

Algorithmes et structures de données Discussion :

Tester l'inclusion d'une valeur dans un ensemble d'intervalle


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2006
    Messages
    127
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2006
    Messages : 127
    Par défaut Tester l'inclusion d'une valeur dans un ensemble d'intervalle
    Bonjour,


    Je recherche une approche efficace pour résoudre le problème suivant:

    Sur l'ensemble d'entiers [[0, X]], je dispose d'un ensemble d'intervalles en cardinal limité (disons < 10).

    Je cherche une approche me permettant de tester rapidement si une valeur est incluse dans au moins un des intervalles de l'ensemble.

    Exemple: Soit les intervalles entiers [[0, 4]], [[6, 12]], [[100, 110]].

    Je désire soumettre une valeur à une fonction de telle sorte que celle-ci me renvoie si un intervalle de l'ensemble d'intervalles contienne cette valeur.

    Ma première implémentation consiste à maintenant une liste d'intervalle et à parcourir linérairement cette liste, en arretant la recherche dès qu'à été trouvé un intervalle contenant la valeur a été trouvé (renvoie alors vrai) ou si la fin de la liste est atteinte (renvoie faux).

    Cependant, la complexité est en O(n), n étant la taille de la liste.

    Une autre solution que j'ai envisagé est de trier la liste d'intervalle par bornes inférieures croissantes. Alors, par tri dichotomique, on trouve l'intervalle dont la borne inférieure est juste avant la valeur à tester en o(ln(n)).

    Une autre solution que j'ai envisagée consiste à exprimer l'ensemble d'intervalles par un tableau de booléens. La taille de ce tableau serait de X+1 (pour chaque valeur de 0 à X) et chaque case de ce tableau d'indice i spécifie si la valeur entière i est dans un intervalle. La complexité est alors en o(1) mais l'occupation mémoire inacceptable.

    N'ayant pas trouver de littérature concernant ce problème, avez-vous d'autres approches à me suggérer?

    Vous remerciant par avance,

    Cordialement,
    Benoît.

  2. #2
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 77
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    Une autre solution que j'ai envisagé est de trier la liste d'intervalle par bornes inférieures croissantes. Alors, par tri dichotomique, on trouve l'intervalle dont la borne inférieure est juste avant la valeur à tester en o(ln(n)).
    Oui, mais si les intervalles sont a priori dans un ordre quelconque, l'opération préalable de tri est en O(nln(n)) (avec un tri rapide).
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  3. #3
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    je dispose d'un ensemble d'intervalles en cardinal limité (disons < 10).
    Ca fait au pire 10 comparaisons. Ca vaut vraiment la peine de chercher une optimisation ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 77
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    Ca fait au pire 10 comparaisons. Ca vaut vraiment la peine de chercher une optimisation ?
    Au temps (autant) pour moi (lu trop vite).
    Effectivement ...
    Cependant
    Alors, par tri dichotomique, on trouve l'intervalle dont la borne inférieure est juste avant la valeur à tester en o(ln(n)).
    le n ici c'est le nombre d'intervalles, non?
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  5. #5
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2006
    Messages
    127
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2006
    Messages : 127
    Par défaut
    Citation Envoyé par Zavonen Voir le message
    Au temps (autant) pour moi (lu trop vite).
    Effectivement ...
    Cependant

    le n ici c'est le nombre d'intervalles, non?
    Oui c'est le nombre d'interval. Cependant, à l'avenir il sera potentiellement supérieur à 10. Et je me dois d'optimiser le problème que je décris ici car il est responsable de 30% du temps de calcul d'une application scientifique dont les calculs durent plusieurs heures.

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Benoit_T Voir le message
    Oui c'est le nombre d'interval. Cependant, à l'avenir il sera potentiellement supérieur à 10. Et je me dois d'optimiser le problème que je décris ici car il est responsable de 30% du temps de calcul d'une application scientifique dont les calculs durent plusieurs heures.
    Dans ce cas, tu peux construire un arbre binaire (en prenant soin de fusionner les intervalles qui se chevauchent).

    Ou sinon, plus simple mais moins optimal, une discrétisation de ton espace avec dans chaque case la liste des intervalles possibles.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. tester l'existence d'une valeur dans un tableau
    Par aymench1985 dans le forum MATLAB
    Réponses: 6
    Dernier message: 16/04/2015, 02h09
  2. Réponses: 1
    Dernier message: 10/10/2012, 15h31
  3. Tirer au hasard une valeur dans un ensemble
    Par damilari dans le forum MATLAB
    Réponses: 14
    Dernier message: 17/08/2009, 19h58
  4. Comment tester la présence d'une valeur dans une liste?
    Par jeo13 dans le forum Macros et VBA Excel
    Réponses: 2
    Dernier message: 03/06/2008, 16h09
  5. Tester l'inclusion d'une chaine dans une autre
    Par Anubis dans le forum Langage
    Réponses: 4
    Dernier message: 28/08/2007, 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