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.

Citation:

---

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).

Citation:

---

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 ?

Citation:

---

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

Citation:

---

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?

Citation:

---

Envoyé par Zavonen

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.

Citation:

---

Envoyé par Benoit_T

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.

Citation:

---

Oui c'est le nombre d'interval(les).

---

Et bien dans ce cas la remarque que j'avais faite sur la complexité du tri préalable reprend du service.

Citation:

---

Envoyé par Zavonen

Et bien dans ce cas la remarque que j'avais faite sur la complexité du tri préalable reprend du service.

---

Oups pardon pour la faute d'orthographe. Effectivement, le tri est en n*ln(n), cependant, le nombre de tests est très supérieur au nombre de générations d'ensembles d'intervalles. En conséquence, le temps de calcul accaparé par les tris bien que de complexité en n*ln(n) est négligeable.

Cordialement,
Benoît.

Si la borne superieure X n'est pas trop élevée, tu peux précalculer le résultat dans un tableau de dimension X.
Ce précalcul est long, mais la lecture est immédiate.