Trouver le numéro de plage intersection
Quel est le meilleur moyen pour savoir si le nombre deux plages se croisent?
Mon numéro de plage est 3023-7430, maintenant je veux le test de la suite de nombre de plages se croisent avec elle: <3000, 3000-6000, 6000-8000, 8000-10000, >10000. La réponse devrait être 3000-6000 et 6000-8000.
Ce qui est le gentil, efficace mathématiques moyen de faire cela dans n'importe quel langage de programmation?
C'est un problème similaire à celui de réponse ici stackoverflow.com/questions/143552/comparing-date-ranges
Très agréable, graphique explication. Merci.
Très agréable, graphique explication. Merci.
OriginalL'auteur deceze | 2008-10-22
Vous devez vous connecter pour publier un commentaire.
Juste un pseudo code deviner:
OriginalL'auteur Chris Kimpton
Je ferais une Gamme de classe et de lui donner une méthode boolean coupe(Plage) . Ensuite, vous pouvez faire
L'intersection en lui-même est quelque chose comme
OriginalL'auteur Hans-Peter Störr
Cela dépend fortement de vos gammes. Une gamme peuvent être grands ou petits, et regroupés ou non en cluster. Si vous avez de grandes, en grappes plages (pensez à "positive dans tous les nombres entiers de 32 bits qui peut être divisé par 2), l'approche la plus simple avec la Gamme(bas, haut) ne réussira pas.
Je suppose que je peux dire la chose suivante:
si vous avez peu de plages (clustering ou pas de clustering n'a pas d'importance ici), pensez à bitvectors. Ces petites bestioles sont ultra rapides à l'égard de l'union, d'intersection et de l'adhésion les tests, même si itération sur tous les éléments pourrait prendre un certain temps, selon la taille. En outre, parce qu'ils n'en utiliser qu'un seul bit pour chaque élément, ils sont assez petits, à moins que vous lancer d'énormes plages.
si vous avez moins de, grandes plages, puis une classe de Gamme comme décrit par otherswill suffit. Cette classe possède les attributs inférieur et supérieur et l'intersection(a,b) est fondamentalement b.supérieur < un.inférieur ou un.supérieur > b.bas. L'Union et l'intersection peut être mis en œuvre en temps constant pour unique plages et pour compisite plages, le temps augmente avec le nombre de sous-intervalles (donc vous ne voulez pas pas trop de peu de valeur)
Si vous avez un grand espace où vos numéros peut être, et les plages sont distribués dans un méchant de fasion, vous devez prendre un regard sur les diagrammes de décision binaires (BDDs). Ces astucieux schémas sont deux terminaux, le Vrai et le Faux et la prise de nœuds pour chaque peu de l'entrée. Une décision nœud a un peu, ça les regarde et deux noeuds d'un graphe: un pour les "bits est une" et une pour "bit est égal à zéro". Compte tenu de ces conditions, vous pouvez encoder une grande plage dans le petit espace. Tous les entiers positifs pour arbitrairement grand nombre, peuvent être encodées dans 3 nœuds dans le graphe -- au fond, une décision unique nœud pour le bit le moins significatif qui va à Faux sur 1 et sur True 0.
Intersection et l'Union sont assez élégante algorithmes récursifs, par exemple, l'intersection prend essentiellement en deux nœuds dans chaque BDD, de traverser les 1-bord jusqu'à un résultat pop-up s'ouvre et vérifie: si l'un des résultats est le Faux-Terminal, créer une 1-branche de la Fausse-terminal dans le résultat BDD. Si les deux sont le Vrai-Terminal, créer une 1-branche de la Vraie-terminal dans le résultat BDD. Si c'est quelque chose d'autre, de créer une 1-branche de ce quelque chose d'autre dans le résultat BDD. Après cela, certains de minimisation des coups de pied (si le 0 et le 1-branche d'un nœud aller à la même suivant BDD /terminal, retirez-le et tirez les transitions entrantes à la cible) et vous êtes de l'or. Nous sommes allés encore plus loin que cela, nous avons travaillé sur la simulation d'outre des ensembles d'entiers sur les BDDs, afin d'accroître la valeur de prédiction afin d'optimiser les conditions.
Ces considérations impliquent que vos opérations sont limités par la quantité de bits dans votre gamme de nombre, qui est, par log_2(MAX_NUMBER). Il suffit de penser, vous pouvez croiser arbitraire des ensembles de 64 bits entiers dans la quasi-constante de temps.
Plus d'informations peuvent être par exemple dans le Wikipedia et les documents référencés.
En outre, si les faux positifs sont supportables et vous avez besoin d'une existence chèque uniquement, vous pouvez regarder les filtres de Bloom. Les filtres de Bloom utilisation d'un vecteur de hachages, afin de vérifier si un élément est contenu dans l'ensemble. Intersection et l'Union est la constante de temps. Le problème majeur ici est que vous obtenez une augmentation du taux de faux positifs si vous remplissez l'bloom-filtre trop.
De l'Information, de nouveau, dans le Wikipedia, par exemple.
Hach, la représentation est un plaisir de terrain. 🙂
OriginalL'auteur Tetha
En python
OriginalL'auteur Andrea Ambu
Si vous utilisez Java
Commons Lang Gamme
a un
overlapsRange(Gamme) méthode.
OriginalL'auteur TAN70