Quel est le moyen le plus efficace de tester les deux entier plages de chevauchement?

Donné deux inclusive entier intervalle [x1:x2] et [y1:y2], où x1 ≤ x2 et y1 ≤ y2, ce qui est le moyen le plus efficace pour tester s'il existe un chevauchement des deux gammes?

Une simple mise en œuvre est comme suit:

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

Mais je m'attends il y a des moyens plus efficaces pour le calcul de ce.

Quelle méthode serait la plus efficace en termes de minimum d'opérations.

Peut-être il est intéressant de noter liés pour certains - stackoverflow.com/q/17138760/104380

InformationsquelleAutor WilliamKF | 2010-07-16

369

Ce qui signifie pour les plages à se chevauchent? Cela signifie qu'il existe un certain nombre de C qui est dans les deux gammes, c'est à dire
```
x1 <= C <= x2
```
et
```
y1 <= C <= y2
```
Maintenant, si l'on peut supposer que les plages sont bien formées (de sorte que x1 <= x2 et y1 <= y2), alors il est suffisant de le tester
```
x1 <= y2 && y1 <= x2
```
- Je crois qu'il devrait être x1 <= y2 && y1 >= x2, non?
- non, si y1 > x2 puis les plages ne se chevauchent pas (par exemple, considérer [1:2] et [3:4]: y1 = 3 et x2 = 2, donc y1 > x2, mais il n'y a pas de chevauchement).
- est une bonne façon de résoudre ce problème lorsque vous avez beaucoup de gammes? certains efficace pour croquer toutes les gammes ensemble et ensuite de les comparer à C?
- Cela ne fonctionne pas si les plages sont égaux, par exemple [1:1] et [1:1] ?
- Pour N gammes, voir Intervalle tree
- ce serait une meilleure réponse si vous l'avez expliqué le raisonnement un peu plus
- Deoraj - Pourquoi pensez-vous que cela ne fonctionne pas? x1 = 1, y1 = 1, x2 = 1, y2 = 1, donc x1 <= y2 && y1 <= x2 est vrai, donc, il y a un chevauchement.
- L'explication est ici: stackoverflow.com/questions/325933/...
- Cette réponse pourrait être élargi pour inclure nombre ou demi-ouvertes intervalles.
- NB les fourchettes peuvent être contigus dans ce cas. [x:x2] et [x2:y2]. Salman est question de moitié ouvert intervalles est un bon.
InformationsquelleAutor Simon Nickerson
120

Donné deux plages [x1,x2], [y1,y2]
```
def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)
```
- seulement pas de manière efficace, parce que lorsque ce contrôle est effectué plusieurs fois par seconde, fonction d'appel est quelque chose que vous voulez éviter, et faire autant de maths vous-même, de le garder à la base
- Les navigateurs modernes seront inline & optimiser les fonctions comme les Mathématiques.max, il devrait y avoir aucun impact notable sur la performance.
- intéressant. avez-vous un article expliquant ce qui est incorporé et ce qui ne l'est pas?
- Non, mais je suis sûr que vous pouvez trouver l'information dont vous-même
- En outre, notez que min(x2,y2) - max(x1,y1) fournit la quantité de chevauchement dans le cas où vous avez besoin que.
InformationsquelleAutor KFL
44

Cela peut facilement fausser un cerveau humain normal, j'ai donc trouvé une approche visuelle pour être plus facile à comprendre:

le Explication

Si deux gammes sont "trop gras" à insérer dans un slot, c'est exactement la somme de la largeur de deux, puis ils se chevauchent.

Pour des gammes [a1, a2] et [b1, b2] ce serait:
```
/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
  //too fat -- they overlap!
}
```
- Il y a plus de cas que celui indiqué sur les photos. E. g., que faire si w2 commence avant w1 et se termine après w1?
- la logique des stands de vrai
- D'accord, mais je pense que cela pourrait aider à fournir un tiers de l'image.
- ensuite, vous avez besoin beaucoup plus d'images il y a 16 combinaisons différentes que 2 plages peuvent être placés dans...
- Wikipedia offre un argument similaire, sans max/min calculs: m1 = (x1 + y1), m2 = (x2 + y2), d1 = (y1 - x1), d2=(y2-x2) se chevauchent = abs(m2 - m1) < d1 + d2
- Le calcul de l'abs(m2-m1) est la même chose que de trouver le max(m2,m1). Si m2>m1 puis abs(m2-m1)=m2-m1 d'autre abs(m2-m1)=m1-m2. Ce qui revient à la même chose que ci-dessus.
- Merci pour énoncer l'évidence. J'étais juste en montrant une autre méthode équivalente, facilement trouvable dans l'Internet ouvert. Je ne voulais pas dire de les comparer.
- Sera-ce la logique de tenir plus de 2 gammes?
- non, il ne sera pas. Si vous pourriez récursive de diviser le problème en paires (et l'utilisation de cette méthode), il y a des moyens plus efficaces de lutter contre elle.
- Soyez prudent si vous utilisez cette méthode, car la somme a2 - a1 + b2 - b1 risque de déborder. Pour le corriger, de changer la formule de max(a2, b2) - a2 - b2 < min(a1, b1) - a1 - b1, ce qui simplifie à max(a1, b1) < min(a2, b2), d'économie d'arithmétique et d'éviter tout débordements (c'est l'AXE des Laboratoires de réponse ci-dessous). Dans le cas spécial où vous savez b2-b1=a2-a1, un autre utile réarrangement de FloatingRock la formule est max(a2, b2) - min(a1, b1) - (b2 - b1) < a2-a1, qui devient abs(b1-a1) < a2 - a1.
- Pour les futurs googlers-à l'aide de flotteurs, de la soustraction peut underflow. Pour le plein de la justesse de tous les bords-cas, vous devriez éviter de l'arithmétique et de l'utilisation purement conditionnelles à la place (ie. utiliser la réponse sommet, après la détermination de a1/a2 est plus grande dans le 1% des cas où vous ne savez pas déjà)
InformationsquelleAutor FloatingRock
35

Grande réponse de Simon, mais pour moi, il était plus facile de penser à la situation inverse.

Quand dois-2 gammes se chevauchent pas? Ils ne se chevauchent pas quand l'un d'eux commence après les autres, on finit:
```
dont_overlap = x2 < y1 || x1 > y2
```
Maintenant, il est facile à exprimer quand ils ne se chevauchent:
```
overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)
```
InformationsquelleAutor damluar
19

Soustrayant le Minimum de l'extrémité de la chaîne à partir de la valeur Maximale du début semble faire l'affaire. Si le résultat est inférieur ou égal à zéro, nous avons un chevauchement. Cette visualise bien:
- Cela couvre tous les cas
- Cela pourrait être la meilleure utilisation d'une feuille de calcul jamais...
InformationsquelleAutor AXE-Labs
10

Je suppose que la question a été au sujet de la manière la plus rapide, pas le plus court de code. La version la plus rapide d'avoir à éviter les branches, nous pouvons donc écrire quelque chose comme ceci:

pour les cas simple:
```
static inline bool check_ov1(int x1, int x2, int y1, int y2){
    //insetead of x1 < y2 && y1 < x2
    return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};
```
ou, pour ce cas:
```
static inline bool check_ov2(int x1, int x2, int y1, int y2){
    //insetead of x1 <= y2 && y1 <= x2
    return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};
```
- Avoir la foi dans votre compilateur. L'expression x1 <= y2 && y1 <= x2 n'ont pas de branches en elle soit, en supposant un raisonnablement compétente du compilateur et de l'architecture du PROCESSEUR (même en 2010). En fait, sur x86, le code généré est fondamentalement identique pour la simple expression et le code dans cette réponse.
InformationsquelleAutor ruslik
7
```
return x2 >= y1 && x1 <= y2;
```
InformationsquelleAutor BlueRaja - Danny Pflughoeft
2

Si nous avions affaire à deux gammes de [x1:x2] et [y1:y2], naturel /anti-ordre naturel des plages, dans le même temps où:
- ordre naturel: x1 <= x2 && y1 <= y2 ou
- anti-ordre naturel: x1 >= x2 && y1 >= y2
alors vous pouvez l'utiliser pour vérifier:

elles sont recouvertes <=> (y2 - x1) * (x2 - y1) >= 0

où seulement quatre opérations sont impliqués:
- deux soustractions
- une multiplication
- une comparaison
InformationsquelleAutor Yankuan Zhang
0

Vous avez le plus efficace de représentation déjà - c'est le strict minimum qui doit être vérifié, sauf si vous savez certainement que x1 < x2 etc, puis utiliser les solutions d'autres, ont apporté.

Vous devriez noter que certains compilateurs fait l'optimiser pour vous, en les retournant dès qu'un de ces 4 expressions de retourner la valeur true. Si l'on retourne true, le résultat final - alors que les autres vérifications peuvent être simplement ignoré.
- Tous les compilateurs. Tous (à ma connaissance) actuellement utilisés langues avec C-la syntaxe de style (C, C++, C#, Java, etc.) employer la court-circuiter les opérateurs booléens et il fait partie des diverses normes qui régissent ces langues. Si le résultat de la valeur de gauche est suffisante pour déterminer le résultat de l'opération, le bras droit de valeur n'est pas évalué.
- Marque H-le compilateur va sauter sur la deuxième clause si elle peut: donc, si vous avez une fonction qui dit: foo(int c) { int i=0; if (c < 3 || ++i == argc) printf("à l'Intérieur de\n"); printf("i est %d\n", i); Foo(2) impression: à l'Intérieur de i est 0 et Foo(4) d'impression: je est 1 (testé sur gcc 4.4.3, mais je me suis appuyé sur ce comportement pour les moches, les code dans la cpi en tant que bien)
InformationsquelleAutor Mark H

Si quelqu'un est à la recherche d'un one-liner qui calcule le chevauchement:

int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations

Si vous voulez un couple moins d'opérations, mais un couple de plusieurs variables:

bool b1 = x2 <= y1;
bool b2 = y2 >= x1;
int overlap = ( !b1 || !b2 ) ? 0 : (y2 >= y1 && b1 ? y1 : y2) - ( x2 <= x1 && b2 ? x1 : x2) + 1; //max 9 operations

InformationsquelleAutor Victor.dMdB

0

Pense que dans le chemin inverse: comment faire les 2 gammes se chevauchent pas? Compte tenu de [x1, x2], puis [y1, y2] devrait être à l'extérieur [x1, x2], c'est à dire, y1 < y2 < x1 or x2 < y1 < y2 qui est équivalent à y2 < x1 or x2 < y1.

Par conséquent, la condition de faire les 2 gammes de chevauchement: not(y2 < x1 or x2 < y1), ce qui est équivalent à y2 >= x1 and x2 >= y1 (même avec la accepté de répondre par Simon).

InformationsquelleAutor Duke

Mon cas est différent. je veux vérifier deux plages de temps de chevauchement. il ne devrait pas être une unité de temps se chevauchent. ici, c'est d'Aller de mise en œuvre.

    func CheckRange(as, ae, bs, be int) bool {
    return (as >= be) != (ae > bs)
    }

Cas de Test

if CheckRange(2, 8, 2, 4) != true {
        t.Error("Expected 2,8,2,4 to equal TRUE")
    }

    if CheckRange(2, 8, 2, 4) != true {
        t.Error("Expected 2,8,2,4 to equal TRUE")
    }

    if CheckRange(2, 8, 6, 9) != true {
        t.Error("Expected 2,8,6,9 to equal TRUE")
    }

    if CheckRange(2, 8, 8, 9) != false {
        t.Error("Expected 2,8,8,9 to equal FALSE")
    }

    if CheckRange(2, 8, 4, 6) != true {
        t.Error("Expected 2,8,4,6 to equal TRUE")
    }

    if CheckRange(2, 8, 1, 9) != true {
        t.Error("Expected 2,8,1,9 to equal TRUE")
    }

    if CheckRange(4, 8, 1, 3) != false {
        t.Error("Expected 4,8,1,3 to equal FALSE")
    }

    if CheckRange(4, 8, 1, 4) != false {
        t.Error("Expected 4,8,1,4 to equal FALSE")
    }

    if CheckRange(2, 5, 6, 9) != false {
        t.Error("Expected 2,5,6,9 to equal FALSE")
    }

    if CheckRange(2, 5, 5, 9) != false {
        t.Error("Expected 2,5,5,9 to equal FALSE")
    }

vous pouvez le voir il y a XOR le modèle dans les limites de la comparaison

InformationsquelleAutor Ajeet47

-7

Voici ma version:
```
int xmin = min(x1,x2)
  , xmax = max(x1,x2)
  , ymin = min(y1,y2)
  , ymax = max(y1,y2);

for (int i = xmin; i < xmax; ++i)
    if (ymin <= i && i <= ymax)
        return true;

return false;
```
Sauf si vous êtes l'exécution de certains de haute performance de la gamme checker sur des milliards de largement espacés entiers, nos versions devraient effectuer de la même façon. Mon point est, c'est la micro-optimisation.
- Je pense que vous êtes allés sur la spécification ici. Il est supposé que x1 à x2 est de montée/descente (de toute façon, c'est triée) - il n'y a pas besoin d'une boucle, vous avez uniquement besoin de vérifier la tête et la queue éléments. Je préfère le min/max de la solution si - tout simplement parce que c'est plus facile à lire quand vous revenez sur le code plus tard.
- -1: ce n'est pas de la micro-optimisation; c'est le choix d'un algorithme approprié. Votre algorithme est O(n) quand il y a une simple O(1) choix.
- C'est ce qui arrive quand "l'optimisation prématurée est la racine de tout mal" devient inviolable, religieux principe de l'inepte au lieu de mi-sérieux remarque sur quelques le modèle de comportement.
InformationsquelleAutor Haywood Jablomey

Vous devez vous connecter pour publier un commentaire.

le Explication