Vous êtes ici : Accueil / Forums & ML / Forums Python / Forum général Python / Dictionnaire d'intervalles

Dictionnaire d'intervalles

Remonter à Forum général Python
  • Dictionnaire d'intervalles

    Envoyé par haypo le 18 Mars 2006 à 03:52
    Salut,

    J'aurai besoin d'une structure de donnée qui sache associer intervalle à une valeur (comme un dict() en fait, mais avec des intervalles en clé). Exemple :
    0..4 => "bleu"
    5..9 => "blanc"
    10..13 => "rouge"

    Je voudrais pouvoir retrouver "blanc" à partir de la valeur 6.

    (j'ai largement simplifié mon problème pour me concentrer sur la question)

    Mes intervalles ne sont pas forcément contigüs, par contre, il ne se chevauchent pas. Exemples :
    (0..19, 30..100, 101..102) : ok
    (0..19, 13..100) : pas ok

    J'ai besoin d'un temps d'accès en 0(1) voir O(log(n)) (avec n: nombre d'intervalles).

    Je ne voudrais pas coder cette structure si elle existe déjà !

    Cette structure sera succeptible d'être modifiée plusieurs fois après sa création : découpage en sous-intervalles, fusion d'intervalles contigüs, décalage d'un intervalle (insertion d'un "trou").

    Si jamais je dois vraiment la coder, je pense que j'utiliserai le type 'set' qui est vraiment sympatoche (rapide pour tester si une valeur est dans un intervalle ou non).

    Haypo
    • Re: Dictionnaire d'intervalles

      Envoyé par ogrisel le 19 Mars 2006 à 03:21
      Bon, j'avais commencé une implementation naive avec 2 listes (une pour les limites et une pour les valeurs) et puis je me suis dit que google avait surement ca en cache:

      http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/457411

      avec deux listes _bounds et _items.

      AMA c'est du code assez algorithmique qui doit bien marcher avec psyco -> faire des bench avec timeit

      Sinon, y a moyen de l'ecrire en pyrex pour optimiser les perfs.
    • Re: Dictionnaire d'intervalles

      Envoyé par ogrisel le 19 Mars 2006 à 02:40
      Est ce que tous tes intervalles sont dans les entiers ? Je ne vois pas comment utiliser le type set a moins de faire un stockage exhaustif s'ils sont de taille finis pas ca me parait pas SPACE-efficace si tes donnees sont 'sparse' (désolé pour les anglicismes, il est tard ;).
Rendu par Ploneboard