Trouver l'intersection de la plage de numéros

Question

Quelle est la meilleure façon de déterminer si deux plages de nombres se croisent?

Ma plage de numéros est 3023-7430, maintenant je veux tester lequel des plages de numéros suivants se croisent avec elle: < 3000, 3000-6000, 6000-8000, 8000-10000,> 10000. La réponse devrait être 3000-6000 et 6000-8000.

Quelle est la façon mathématique efficace de faire cela dans n'importe quel langage de programmation?

Answer 1

Juste un code pseudo estimation:

Set<Range> determineIntersectedRanges(Range range, Set<Range> setofRangesToTest) 
{ 
    Set<Range> results; 
    foreach (rangeToTest in setofRangesToTest) 
    do 
    if (rangeToTest.end <range.start) continue; // skip this one, its below our range 
    if (rangeToTest.start >range.end) continue; // skip this one, its above our range 
    results.add(rangeToTest); 
    done 
    return results; 
} 

Answer 2

Je voudrais faire une classe Range et lui donner une méthode intersects booléennes (Range). Ensuite, vous pouvez faire une

foreach(Range r : rangeset) { if (range.intersects(r)) res.add(r) } 

L'intersection lui-même est quelque chose comme

this.start <= other.end && this.end >= other.start 

Answer 3

Cela dépend fortement de vos gammes. Une plage peut être grande ou petite et groupée ou non groupée. Si vous avez de grandes plages agglomérat (penser à « tous les entiers 32 bits positifs qui peuvent être divisées par 2), l'approche simple avec gamme (inférieure, supérieure) ne réussira pas.

Je suppose que je peux dire ce qui suit : Si vous avez des petites plages (le clustering ou le clustering n'a pas d'importance ici), pensez aux bitvectors Ces petites créatures sont très rapides en termes de tests d'union, d'intersection et d'appartenance, même si l'itération de tous les éléments peut prendre un certain temps. De plus, parce qu'ils n'utilisent qu'un seul bit pour chaque élément, ils sont assez petits, à moins que vous ne leur lanciez d'énormes gammes

si vous avez moins de gammes plus grandes, alors une classe Range comme décrit par d'autres suffira Cette classe a l'attribut es inférieur et supérieur et l'intersection (a, b) est fondamentalement plus grand que < a.lower ou a.upper> b.lower. Union et intersection peuvent être mises en œuvre en temps constant pour les plages simples et pour les plages compisites, le temps augmente avec le nombre de sous-plages (donc vous ne voulez pas trop de petites plages)

Si vous avez un grand espace où vos nombres peuvent être, et les plages sont distribuées dans un fasion méchant, vous devriez jeter un oeil aux diagrammes de décision binaires (BDDs). Ces diagrammes astucieux ont deux nœuds terminaux, True et False et des nœuds de décision pour chaque bit de l'entrée. Un nœud de décision a un bit qu'il regarde et deux nœuds de graphes suivants - un pour "bit is one" et un pour "bit is zero". Dans ces conditions, vous pouvez encoder de grandes plages dans un espace réduit. Tous les nombres entiers positifs pour les nombres arbitrairement grands peuvent être codées en 3 noeuds dans le graphique - essentiellement un seul nœud de décision pour le moins significatif qui va à faux sur 1 et True sur 0.

intersection et l'Union sont assez élégant algorithmes récursifs, par exemple, l'intersection prend essentiellement deux nœuds correspondants dans chaque BDD, traverse le 1-edge jusqu'à ce que le résultat apparaisse et vérifie: si l'un des résultats est le False-Terminal, créer une 1-branche au False- terminal dans le résultat BDD. Si les deux sont True-Terminal, créez une 1-branche au True-Terminal dans le résultat BDD. Si c'est quelque chose d'autre, créez une 1-branche à ce quelque chose d'autre dans le résultat BDD. Après quoi, une certaine minimisation intervient (si les branches 0 et 1 d'un nœud vont au même BDD/terminal, supprimez-le et tirez les transitions entrantes vers la cible) et vous êtes en or.Nous sommes même allés plus loin que cela, nous avons travaillé à simuler l'addition d'ensembles d'entiers sur des BDD afin d'améliorer la prédiction de valeur afin d'optimiser les conditions. Ces considérations impliquent que vos opérations sont limitées par la quantité de bits dans votre plage de numéros, c'est-à-dire par log_2 (MAX_NUMBER). Pensez-y, vous pouvez croiser des ensembles arbitraires d'entiers 64 bits dans un temps presque constant.

Plus d'informations peuvent être par exemple dans le Wikipedia et les papiers référencés. En outre, si les faux positifs sont supportables et que vous n'avez besoin que d'une vérification d'existence, vous pouvez consulter les filtres Bloom. Les filtres Bloom utilisent un vecteur de hachage pour vérifier si un élément est contenu dans l'ensemble représenté. Intersection et Union est un temps constant. Le problème majeur ici est que vous obtenez un taux de faux positif croissant si vous remplissez trop le filtre bloom. Information, encore une fois, dans le Wikipedia, par exemple.

Hach, la représentation de l'ensemble est un champ amusant. :)

Answer 4

En python

class nrange(object): 
    def __init__(self, lower = None, upper = None): 
     self.lower = lower 
     self.upper = upper 
    def intersection(self, aRange): 
     if self.upper < aRange.lower or aRange.upper < self.lower: 
      return None 
     else: 
      return nrange(max(self.lower,aRange.lower), \ 
          min(self.upper,aRange.upper)) 

Answer 5

Si vous utilisez Java Commons Lang Range a une méthode overlapsRange (gamme Range).