skuteczny algorytm do testowania _, który_ ustawia konkretną liczbę należy do

Question

Jeśli mam duży zestaw ciągłych zakresów (np. [0..5], [10..20], [7..13], [- 1. 37)) i może rozmieścić te zestawy w dowolnej strukturze danych, którą lubię, jaki jest najbardziej skuteczny sposób testowania , który to zestaw ustawia konkretny numer test_number?

Myślałem o przechowywaniu zestawów w zbalansowanym drzewie binarnym na podstawie małej liczby zestawu (a każdy węzeł miałby wszystkie zestawy, które mają taką samą najniższą liczbę z ich zestawu). Umożliwiłoby to wydajne przycinanie liczby zestawów w zależności od tego, czy test_numer, który testujesz względem zestawów, jest mniejszy niż najniższy numer zestawu, a następnie czyszczenie tego węzła i wszystkich węzłów po prawej stronie tego węzła (co mają małą liczbę w ich zakresie, która jest większa niż liczba testowa). Myślę, że przycinałoby to średnio 25% zbiorów, ale wtedy musiałbym liniowo spojrzeć na wszystkie pozostałe węzły w drzewie binarnym, aby określić, czy test_number należał do tych zestawów. (Mogłabym dalej zoptymalizować sortując listy zestawów w dowolnym węźle według najwyższego numeru w zestawie, co pozwoliłoby mi na wyszukiwanie binarne w ramach określonej listy, aby określić, który zestaw, jeśli taki występuje, zawiera numer_testowy. zestawów, z którymi będę miał do czynienia, nie ma zachodzących na siebie granic.)

Myślę, że problem ten został rozwiązany w przetwarzaniu grafiki, ponieważ odkrył sposoby efektywnego testowania, które wielokąty w całym swoim modelu przyczyniają się do do określonego piksela, ale nie znam terminologii tego typu algorytmu.

Answer 1

Twoja intuicja odnośnie znaczenia problemu z grafiką jest prawidłowa. Rozważ zbudowanie i wysłanie zapytania do segment tree. Jest szczególnie dobrze dostosowany do zapytania liczenia, które chcesz. Zobacz także jego description in Computational Geometry.

Answer 2

Myślę, że zorganizowałbym je w taki sam sposób, jak Mediawiki indeksuje strony - jako bucket sort. Nie wiem, że jest to najskuteczniejszy algorytm, ale powinien być szybki i całkiem łatwy do zaimplementowania (nawet udało mi się go, a SQL w tym!).

Zasadniczo, algorytm sortowania jest

For Each SetOfNumbers 
    For Each NumberInSet 
     Put SetOfNumbers into Bin(NumberInSet) 

Następnie do kwerendy, można po prostu policzyć liczbę elementów w pojemniku (MyNumber)

Podejście to będzie działać dobrze, gdy SetOfNumbers rzadko się zmienia, chociaż jeśli zmieniają się regularnie, aktualizacja Bins nie jest zbyt trudna. Jego główną wadą jest to, że handluje przestrzenią i początkowym czasem sortowania w przypadku bardzo szybkich zapytań.

Zauważ, że w algorytmie rozszerzyłem zakresy do SetsOfNumbers - wyliczając każdą liczbę w danym zakresie.

Answer 3

Myślę, że budowanie struktury drzewa przyspieszy znacznie (pod warunkiem, że masz wystarczającą liczbę zestawów i liczb, aby sprawdzić, czy jest wart początkowego kosztu). Zamiast drzewa binarnego powinno to być drzewo trójskładnikowe. Każdy węzeł powinien mieć lewy, środkowy i prawy węzeł, gdzie lewy węzeł zawiera zestaw, który jest ściśle mniejszy niż zestaw węzłów, prawo jest ściśle większe, a środek nakłada się.

   Set1 
      /| \ 
      / | \ 
      / | \ 
     Set2 Set3 Set4 

Jest to szybki i łatwy sposób sprawdzić, czy nie pokrywają się w zestawach, ponieważ masz tylko porównanie wartości minimalne i maksymalne ich zamówienie. W prostym przypadku powyżej, Set2 [max] < Set1 [min], Set4 [min]> Set1 [max], Set1 i Set3 mają pewne nakładanie.Przyspieszy to wyszukiwanie, ponieważ jeśli szukany numer znajduje się w zestawie nr 1, nie będzie go w zestawie 2 ani w zestawie 4, i nie trzeba go sprawdzać.

Chcę tylko podkreślić, że używanie takiego schematu oszczędza czas tylko na naiwnej implementacji sprawdzania każdego zestawu, jeśli masz więcej numerów do sprawdzenia niż zestawów.