Quel est le moyen le plus efficace de tester deux plages de nombres entiers pour le chevauchement?

Étant donné deux intervalles entiers inclusifs [x1: x2] et [y1: y2], où x1 ≤ x2 et y1 ≤ y2, quel est le moyen le plus efficace de vérifier s’il existe un chevauchement des deux plages?

Une implémentation simple est la suivante:

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

Mais je pense qu’il existe des moyens plus efficaces pour calculer cela.

Quelle méthode serait la plus efficace en termes d’opérations les moins nombreuses.

    Qu’est-ce que cela signifie pour les plages de chevauchement? Cela signifie qu’il existe un certain nombre C qui est dans les deux gammes, c.-à-d.

     x1 <= C <= x2 

    et

     y1 <= C <= y2 

    Maintenant, si on peut supposer que les plages sont bien formées (de sorte que x1 <= x2 et y1 <= y2), alors il suffit de tester

     x1 <= y2 && y1 <= x2 

    Étant donné deux plages [x1, x2], [y1, y2]

     def is_overlapping(x1,x2,y1,y2): return max(x1,y1) <= min(x2,y2) 

    Cela peut facilement déformer un cerveau humain normal. J’ai donc trouvé une approche visuelle plus facile à comprendre:

    Folle chevauchement

    le Explication

    Si deux plages sont “trop ​​grosses” pour tenir dans une fente qui est exactement la sum de la largeur des deux, alors elles se chevauchent.

    Pour les plages [a1, a2] et [b1, b2] cela 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! } 

    Super réponse de Simon , mais pour moi, c’était plus facile de penser au cas inverse.

    Quand 2 plages ne se chevauchent-elles pas? Ils ne se chevauchent pas lorsque l’un d’eux commence après que l’autre se termine:

     dont_overlap = x2 < y1 || x1 > y2 

    Maintenant, il est facile d’exprimer quand ils se chevauchent:

     overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2) 

    La soustraction du minimum des extrémités des plages du maximum du début semble faire l’affaire. Si le résultat est inférieur ou égal à zéro, nous avons un chevauchement. Cela le visualise bien:

    entrer la description de l'image ici

    Je suppose que la question portait sur le code le plus rapide et non le plus court. La version la plus rapide doit éviter les twigs, nous pouvons donc écrire quelque chose comme ceci:

    pour les cas simples:

     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); }; 
     return x2 >= y1 && x1 <= y2; 

    Si vous avez affaire à, étant donné deux plages [x1:x2] et [y1:y2] , les plages d’ordre naturel / anti-naturel en même temps où:

    • ordre naturel: x1 <= x2 && y1 <= y2 ou
    • ordre anti-naturel: x1 >= x2 && y1 >= y2

    alors vous pouvez vouloir l'utiliser pour vérifier:

    ils se chevauchent <=> (y2 - x1) * (x2 - y1) >= 0

    où seules quatre opérations sont concernées:

    • deux soustractions
    • une multiplication
    • une comparaison

    Vous avez déjà la représentation la plus efficace – c’est le ssortingct minimum qui doit être vérifié à moins que vous ne sachiez avec certitude que x1

    Vous devriez probablement noter que certains compilateurs vont réellement optimiser ceci pour vous – en retournant dès que l’une de ces 4 expressions retourne vrai. Si on retourne true, le résultat final le sera aussi, donc les autres vérifications peuvent simplement être ignorées.

    Si quelqu’un cherche une ligne unique qui calcule le chevauchement réel:

     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 quelques opérations de moins, mais quelques variables supplémentaires:

     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 

    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 exécutez des vérificateurs de haute performance sur des milliards d'entiers largement espacés, nos versions devraient fonctionner de la même manière. Ce que je veux dire, c'est la micro-optimisation.