Quelle est la façon la plus efficace de tester le chevauchement de deux plages entières?

Étant donné deux plages entières inclusives [x1: x2] et [y1: y2], où x1 ≤ x2 et y1 ≤ y2, quelle est la façon la plus efficace de tester s'il y a 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 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

Mais je m'attends à ce qu'il existe des moyens plus efficaces de calculer cela.

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

Que signifie le chevauchement des plages? Cela signifie qu'il existe un certain nombre C qui est dans les deux gammes, à savoir

x1 <= C <= x2

et

y1 <= C <= y2

Maintenant, si nous sommes autorisés à supposer que les plages sont bien formées (de sorte que x1 <= x2 et y1 <= y2), 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:

le Explication

Si deux plages sont «trop grasses» pour tenir dans une fente qui est exactement la somme de la largeur des deux, elles se chevauchent.

Pour les 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!
}

Excellente réponse de Simon , mais pour moi, il était plus facile de penser au cas inverse.

Quand 2 plages ne se chevauchent-elles pas? Ils ne se chevauchent pas lorsque l'un commence après la fin de l'autre:

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)

Soustraire le 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:

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 branches, nous pouvons donc écrire quelque chose comme ceci:

pour 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, dans 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 aviez affaire à deux gammes [x1:x2]et à des gammes d'ordre [y1:y2]naturel / anti-naturel en même temps où:

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

alors vous pouvez utiliser ceci pour vérifier:

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

où seulement quatre opérations sont impliquées:

• deux soustractions
• une multiplication
• une comparaison

Si quelqu'un recherche une doublure 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 de plus:

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

Pensez à l' inverse : comment faire en sorte que les 2 plages ne se chevauchent pas ? Étant donné [x1, x2], alors [y1, y2]devrait être à l' extérieur [x1, x2] , y1 < y2 < x1 or x2 < y1 < y2ce qui est équivalent à y2 < x1 or x2 < y1.

Par conséquent, la condition pour que les 2 plages se chevauchent:, not(y2 < x1 or x2 < y1)ce qui équivaut à y2 >= x1 and x2 >= y1(identique à la réponse acceptée par Simon).

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

Vous devriez probablement noter que certains compilateurs optimiseront réellement cela pour vous - en retournant dès que l'une de ces 4 expressions retournera vrai. Si l'un retourne vrai, le résultat final le sera aussi - de sorte que les autres vérifications peuvent simplement être ignorées.

Mon cas est différent. je veux vérifier que deux plages de temps se chevauchent. il ne doit pas y avoir de chevauchement de temps unitaire. voici l'implémentation de Go.

    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 voir qu'il y a un motif XOR dans la comparaison des limites

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;

À moins que vous exécutiez un vérificateur de plage hautes performances sur des milliards d'entiers largement espacés, nos versions devraient fonctionner de la même manière. Mon point est, c'est la micro-optimisation.