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

252

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.

WilliamKF
źródło
Może być ciekawie powiązany z niektórymi - stackoverflow.com/q/17138760/104380
vsync

Odpowiedzi:

454

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
Simon Nickerson
źródło
1
Uważam, że tak powinno być x1 <= y2 && y1 >= x2, nie?
David Beck
8
@DavidBeck: nie, jeśli y1> x2, to zakresy na pewno się nie pokrywają (np. Rozważ [1: 2] i [3: 4]: y1 = 3 i x2 = 2, więc y1> x2, ale nie ma nakładania się) .
Simon Nickerson
8
to byłaby lepsza odpowiedź, gdybyś wyjaśnił nieco bardziej rozumowanie
shoosh
2
@Vineet Deoraj - Jak myślisz, dlaczego to nie działa? x1 = 1, y1 = 1, x2 = 1, y2 = 1, więc x1 <= y2 && y1 <= x2 jest prawdą, więc zachodzi na siebie nakładanie się.
dcp,
2
Wyjaśnienie jest tutaj: stackoverflow.com/questions/325933/…
Alex
138

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

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)
KFL
źródło
4
@ uyuyuy99 - tylko nie tak wydajne, ponieważ gdy ta kontrola jest wykonywana wiele razy na sekundę, wywoływanie funkcji jest czymś, czego chciałbyś uniknąć i zrobić tyle samo matematyki, trzymaj ją na poziomie podstawowym
vsync
7
@vsync Nowoczesne przeglądarki wbudują i zoptymalizują funkcje takie jak Math.max, nie powinno to mieć zauważalnego wpływu na wydajność.
Ashton Six
1
@AshtonWar - ciekawe. czy masz artykuł wyjaśniający, co jest wstawiane, a co nie?
vsync
@vsync Nie, ale jestem pewien, że możesz sam znaleźć informacje
Ashton Six,
6
Ponadto należy pamiętać, że min(x2,y2) - max(x1,y1)zapewnia to nakładanie się w razie potrzeby.
user1556435,
59

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

nakładać się na szaleństwo

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!
}
FloatingRock
źródło
3
Na zdjęciach jest więcej przypadków niż pokazano. Np. Co jeśli w2 zaczyna się przed w1, a kończy po w1?
WilliamKF,
7
@WilliamKF logika jest prawdziwa
FloatingRock
2
Zgadzam się, ale myślę, że może to pomóc w uzyskaniu trzeciego obrazu.
WilliamKF,
3
@WilliamKF, to potrzebujesz dużo więcej zdjęć, istnieje 16 różnych kombinacji, w których można umieścić 2 zakresy ...
Peter
3
Zachowaj ostrożność, jeśli używasz tej metody, ponieważ suma a2 - a1 + b2 - b1może się przepełnić. Aby to naprawić, przestaw formułę na max(a2, b2) - a2 - b2 < min(a1, b1) - a1 - b1, co upraszcza max(a1, b1) < min(a2, b2), oszczędzając trochę arytmetyki i unikając ewentualnych przelewów (oto odpowiedź AX-Labs poniżej). W szczególnym przypadku, w którym wiesz b2-b1=a2-a1, kolejną przydatną zmianą formuły FloatingRock jest max(a2, b2) - min(a1, b1) - (b2 - b1) < a2-a1, która staje się abs(b1-a1) < a2 - a1.
Paolo Bonzini
44

Ś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)
damluar
źródło
1
Dla mnie łatwiejszym do zrozumienia wyrażeniem jest: x2 <y1 || y2 <x1 // gdzie używam „mniej niż” zamiast „większy niż”.
Park JongBum
26

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:

wprowadź opis zdjęcia tutaj

AX Labs
źródło
2
Dotyczy to wszystkich przypadków
użytkownik3290180,
10

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);
};
Ruslik
źródło
7
Uwierz w swój kompilator. W wyrażeniu x1 <= y2 && y1 <= x2 nie ma też żadnych rozgałęzień , przy założeniu, że kompilator i architektura procesora są odpowiednio kompetentne (nawet w 2010 r.). W rzeczywistości na x86 wygenerowany kod jest zasadniczo identyczny dla prostego wyrażenia vs. kod w tej odpowiedzi.
Søren Løvborg
4
return x2 >= y1 && x1 <= y2;
BlueRaja - Danny Pflughoeft
źródło
to nie jest poprawne. Ponieważ x1 <= y1 && x2 >= y2 || x1 >= y1 && x2 <= y2powinien również zwrócić true.
Rahat Zaman
4

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
Yankuan Zhang
źródło
1

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
Victor.dMdB
źródło
1

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).

Książę
źródło
Wygląda tak samo, jak odpowiedział @damluar (2 marca 16 o 17:36)
Nakilon
0

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ąć.

Mark H.
źródło
2
Wszystkie kompilatory będą. Wszystkie (według mojej wiedzy) obecnie używane języki ze składnią w stylu C (C, C ++, C #, Java itp.) Wykorzystują zwarte operatory logiczne i jest to część różnych standardów rządzących tymi językami. Jeśli wynik lewej wartości jest wystarczający do ustalenia wyniku operacji, wartość po prawej stronie nie jest obliczana.
Jonathan Grynspan
1
Mark H - kompilator pominie drugą klauzulę, jeśli może: więc jeśli masz funkcję, która mówi: foo (int c) {int i = 0; if (c <3 || ++ i == argc) printf („Inside \ n”); printf („i to% d \ n”, i); Foo (2) wypisze: wewnątrz i ma wartość 0, a Foo (4) wypisze: i ma wartość 1 (testowane na gcc 4.4.3, ale polegałem również na tym zachowaniu w przypadku brzydkiego kodu w icc)
J Teller
0

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

Ajeet47
źródło
-10

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.

Haywood Jablomey
źródło
Myślę, że przejrzałeś tutaj specyfikację. Zakłada się, że od x1 do x2 rośnie / maleje (tak czy inaczej, jest posortowane) - nie ma potrzeby pętli, wystarczy sprawdzić elementy głowy i ogona. Wolę jednak rozwiązanie min / max - po prostu dlatego, że łatwiej jest odczytać, gdy wrócisz do kodu później.
Mark H
12
-1: to nie jest mikrooptymalizacja; to wybiera odpowiedni algorytm. Algorytmem jest O (n), gdy istnieje prosty wybór O (1).
Simon Nickerson
Dzieje się tak, gdy „przedwczesna optymalizacja jest korzeniem wszelkiego zła” staje się nietykalną zasadą religijną dla nieudolnych zamiast na wpół poważnej uwagi na temat sporadycznych zachowań.
rghome