Znajdź skrzyżowanie z numerem linii

Question

Jaki jest najlepszy sposób na sprawdzenie, czy dwa zakresy liczb przecinają się?

moim przedziale liczba jest 3023-7430, teraz chcę sprawdzić, które z poniższych zakresów numerycznych przecinają się ze sobą: < 3000, 3000-6000, 6000-8000, 8000-10000,> 10000. Odpowiedź powinna być 3000-6000 i 6000-8000.

Jaki jest miły, wydajny matematyczny sposób na zrobienie tego w dowolnym języku programowania?

Answer 1

tylko domyślać pseudokod:

Set<Range> determineIntersectedRanges(Range range, Set<Range> setofRangesToTest) 
{ 
    Set<Range> results; 
    foreach (rangeToTest in setofRangesToTest) 
    do 
    if (rangeToTest.end <range.start) continue; // skip this one, its below our range 
    if (rangeToTest.start >range.end) continue; // skip this one, its above our range 
    results.add(rangeToTest); 
    done 
    return results; 
} 

Answer 2

chciałbym zrobić klasę Zakres i nadać mu metodę boolean przecina (zakres). Następnie można zrobić

foreach(Range r : rangeset) { if (range.intersects(r)) res.add(r) } 

Samo skrzyżowanie jest coś takiego jak

this.start <= other.end && this.end >= other.start 

Answer 3

Ten silnie zależy od zakresów. Zasięg może być duży lub mały, skupiony lub nie klastrowany. Jeśli masz duże, zaklajstrowane zakresy (pomyśl o "wszystkich dodatnich 32-bitowych liczbach całkowitych, które można podzielić przez 2), proste podejście z zakresem (niższym, górnym) nie powiedzie się:

Zgaduję, że mogę powiedzieć co następuje : jeśli masz małe zakresy (klastrowanie lub nie klastrowanie nie ma tu znaczenia), rozważmy bitvektory.Te małe stworki szybko się palą w odniesieniu do testowania związku, przecięć i członkostwa, nawet jeśli iteracja nad wszystkimi elementami może zająć trochę czasu, w zależności od Ponadto, ponieważ używają pojedynczego bitu dla każdego elementu, są one dość małe, chyba że rzucicie na nie olbrzymie zakresy:

jeśli macie mniej, większe zasięgi, wtedy wystarczą zakresy klasy, jak opisują je inni Ta klasa ma atrybut es dolny i górny oraz przecięcie (a, b) jest zasadniczo b.upper < a.lower lub aupper> b.lower. Unia i skrzyżowanie mogą być realizowane w stałym czasie dla pojedynczych zakresów i dla zakresów współdziałania, czas rośnie wraz z liczbą podzakresów (więc nie chcesz zbyt wielu małych zakresów)

Jeśli masz ogromne miejsce Twoje liczby mogą być, a zakresy są rozmieszczone w paskudnej fasionie, powinieneś rzucić okiem na schematy decyzji binarnych (BDD). Te zręczne diagramy mają dwa węzły końcowe, True i False oraz węzły decyzyjne dla każdego wejścia bit. Węzeł decyzyjny ma trochę patrzenia i dwa następujące węzły grafów - jeden dla "bit to jeden" i jeden dla "bit to zero". Biorąc pod uwagę te warunki, możesz kodować duże zakresy w maleńkiej przestrzeni. Wszystkie dodatnie liczby całkowite dla dowolnie dużych liczb mogą być zakodowane w 3 węzłach na wykresie - w zasadzie pojedynczy węzeł decyzyjny dla najmniej znaczącego bitu, który przechodzi do Fałszywy na 1 i na Prawy na 0.

Skrzyżowanie i Unia są całkiem eleganckie algorytmy rekursywne, na przykład, przecięcie w zasadzie bierze dwa odpowiadające węzły w każdym BDD, przemierza 1-ostrze aż pojawi się jakiś wynik i sprawdza: jeśli jednym z wyników jest False-Terminal, utwórz 1-gałąź dla Fałszywego terminal w wyniku BDD. Jeśli oba są True-Terminal, utwórz 1-gałąź do True-terminalu w wyniku BDD. Jeśli jest coś innego, utwórz 1-gałąź do tego czegoś - inaczej w wyniku BDD. Następnie, niektóre minimalizacje rozpoczynają się (jeśli 0- i 1-odgałęzienie węzła idą do tego samego po BDD/terminalu, usuń go i przyciągnij nadchodzące przejścia do celu) i jesteś złoty.Poszliśmy nawet dalej, pracowaliśmy nad symulacją dodawania zestawów liczb całkowitych na dyskach BDD w celu zwiększenia prognozowania wartości w celu optymalizacji warunków.

Powyższe rozważania implikują, że operacje są ograniczone przez liczbę bitów w zakresie numerów, czyli log_2 (MAX_NUMBER). Pomyśl o tym, możesz przecinać dowolne zestawy 64-bitowych liczb całkowitych w prawie stałym czasie.

Więcej informacji można znaleźć na przykład w dokumencie Wikipedia i dokumentach z odnośnikami.

Co więcej, jeśli fałszywe alarmy są możliwe do zaakceptowania i potrzebujesz tylko kontroli istnienia, możesz spojrzeć na filtry Blooma. Filtry Bloom wykorzystują wektor skrótów w celu sprawdzenia, czy element jest zawarty w reprezentowanym zestawie. Przecięcie i Unia to stały czas. Głównym problemem jest to, że uzyskujesz rosnącą liczbę fałszywych trafień, jeśli za dużo zapełnisz filtr kwitnienia. Informacja, na przykład, w Wikipedia.

Hach, reprezentacja zestawu to zabawne pole. :)

Answer 4

W python

class nrange(object): 
    def __init__(self, lower = None, upper = None): 
     self.lower = lower 
     self.upper = upper 
    def intersection(self, aRange): 
     if self.upper < aRange.lower or aRange.upper < self.lower: 
      return None 
     else: 
      return nrange(max(self.lower,aRange.lower), \ 
          min(self.upper,aRange.upper)) 

Answer 5

Jeśli używasz Java Commons Lang Range ma metodę overlapsRange (zakres Range).