Jaki jest najbardziej efektywny sposób przetestowania dwóch zakresów liczb całkowitych pod kątem nakładania się?

Biorąc pod uwagę dwa całkowite zakresy liczb całkowitych [x1: x2] i [y1: y2], gdzie x1 ≤ x2 i y1 ≤ y2, jaki jest najskuteczniejszy sposób sprawdzenia, czy oba zakresy się pokrywają?

Prosta implementacja wygląda następująco:

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);
}

Ale oczekuję, że istnieją bardziej wydajne sposoby na obliczenie tego.

Która metoda byłaby najbardziej wydajna pod względem najmniejszej liczby operacji.

Co to znaczy, że zakresy się pokrywają? Oznacza to, że istnieje pewna liczba C, która znajduje się w obu zakresach, tj

x1 <= C <= x2

i

y1 <= C <= y2

Teraz, jeśli możemy założyć, że zakresy są dobrze uformowane (tak, że x1 <= x2 i y1 <= y2), wystarczy przetestować

x1 <= y2 && y1 <= x2

Biorąc pod uwagę dwa zakresy [x1, x2], [y1, y2]

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

Może to łatwo wypaczyć normalny ludzki mózg, więc znalazłem wizualne podejście, które jest łatwiejsze do zrozumienia:

le Wyjaśnienie

Jeśli dwa zakresy są „zbyt grube”, aby zmieścić się w szczelinie, która jest dokładnie sumą szerokości obu, wówczas się pokrywają.

Dla zakresów [a1, a2]i [b1, b2]to byłoby:

/**
 * 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!
}

Świetna odpowiedź od Simona , ale dla mnie łatwiej było pomyśleć o odwrotnej sprawie.

Kiedy 2 zakresy się nie pokrywają? Nie nakładają się, gdy jeden z nich zaczyna się po zakończeniu drugiego:

dont_overlap = x2 < y1 || x1 > y2

Teraz łatwo wyrazić, kiedy się pokrywają:

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

Wydaje się, że odjęcie minimum końca przedziałów od maksimum początku jest wystarczające. Jeśli wynik jest mniejszy lub równy zeru, nakładamy się. To dobrze to wizualizuje:

Przypuszczam, że pytanie dotyczyło najszybszego, a nie najkrótszego kodu. Najszybsza wersja musi unikać gałęzi, więc możemy napisać coś takiego:

dla prostego przypadku:

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));
};

lub w tym przypadku:

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;

Jeśli miałeś do czynienia z dwoma zakresami [x1:x2]i [y1:y2]naturalnymi / antynaturalnymi zakresami zamówień jednocześnie:

• naturalny porządek: x1 <= x2 && y1 <= y2lub
• porządek antynaturalny: x1 >= x2 && y1 >= y2

możesz użyć tego do sprawdzenia:

nakładają się na siebie <=> (y2 - x1) * (x2 - y1) >= 0

przy zaangażowaniu tylko czterech operacji:

• dwa odejmowania
• jedno pomnożenie
• jedno porównanie

Jeśli ktoś szuka jednej linijki, która oblicza faktyczne nakładanie się:

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

Jeśli chcesz kilka operacji mniej, ale kilka innych zmiennych:

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

Pomyśl odwrotnie : jak sprawić, by 2 zakresy się nie nakładały ? Biorąc pod uwagę [x1, x2], [y1, y2]powinien być na zewnątrz [x1, x2] , tj. y1 < y2 < x1 or x2 < y1 < y2Co jest równoważne y2 < x1 or x2 < y1.

Dlatego warunek, aby 2 zakresy zachodziły na siebie:, not(y2 < x1 or x2 < y1)co jest równoważne y2 >= x1 and x2 >= y1(to samo z zaakceptowaną odpowiedzią Simona).

Masz już najbardziej wydajną reprezentację - to absolutne minimum, które należy sprawdzić, chyba że wiesz na pewno, że x1 <x2 itp., A następnie skorzystaj z rozwiązań dostarczonych przez innych.

Powinieneś prawdopodobnie zauważyć, że niektóre kompilatory faktycznie zoptymalizują to dla Ciebie - zwracając, gdy tylko jedno z tych 4 wyrażeń zwróci wartość true. Jeśli jedna zwróci wartość true, wynik będzie taki sam - a pozostałe kontrole można po prostu pominąć.

Moja sprawa jest inna. Chcę sprawdzić, czy dwa zakresy czasu się pokrywają. czas nie powinien nakładać się na siebie. oto implementacja Go.

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

Przypadki testowe

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")
    }

widać porównanie XOR w porównaniu granic

Oto moja wersja:

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;

Jeśli nie korzystasz z wysokowydajnego sprawdzania zasięgu na miliardach liczb całkowitych o dużej odległości, nasze wersje powinny działać podobnie. Chodzi mi o to, że jest to mikrooptymalizacja.