Kosz (geometria obliczeniowa)
W geometrii obliczeniowej kosz jest strukturą danych , która umożliwia wydajne zapytania o regiony. Za każdym razem, gdy punkt danych trafia do kosza, częstotliwość tego kosza jest zwiększana o jeden.
na płaszczyźnie 2D znajdują się prostokąty wyrównane względem osi , struktura może odpowiedzieć na pytanie: „Biorąc pod uwagę prostokąt zapytania, jakie prostokąty go przecinają?” W przykładzie na górnym rysunku A, B, C, D, E i F to istniejące prostokąty, więc zapytanie z prostokątem Q powinno zwrócić C, D, E i F , jeśli zdefiniujemy wszystkie prostokąty jako przedziały zamknięte .
Struktura danych dzieli region płaszczyzny 2D na pojemniki o jednakowej wielkości . Obwiednia koszy obejmuje wszystkie prostokąty kandydujące do zapytania. Wszystkie pojemniki są ułożone w szyk 2D. Wszyscy kandydaci są również reprezentowani jako tablice 2D. Rozmiar tablicy kandydata to liczba koszy, które przecina.
Na przykład na górnym rysunku kandydat B ma 6 elementów ułożonych w szyku 3 rzędy na 2 kolumny, ponieważ w takim układzie przecina 6 pojemników. Każdy pojemnik zawiera nagłówek listy pojedynczo połączonej . Jeśli kandydat przecina kosz, jest powiązany łańcuchem z połączoną listą kosza. Każdy element w tablicy kandydata jest węzłem łączącym na liście połączonej odpowiedniego pojemnika.
Operacje
Zapytanie
Z prostokąta zapytania Q możemy dowiedzieć się, który kosz przecina się w lewym dolnym rogu, po prostu odejmując lewy dolny róg obwiedni kosza od lewego dolnego rogu Q i dzieląc wynik przez szerokość i wysokość kosza odpowiednio. Następnie możemy iterować kosze Q i badać wszystkich kandydatów na połączonych listach tych koszy. Dla każdego kandydata sprawdzimy, czy rzeczywiście przecina Q . Jeśli tak i nie było to wcześniej zgłaszane, to zgłaszamy. Możemy przyjąć konwencję, że zgłaszamy kandydata tylko wtedy, gdy go znajdziemy. Można to łatwo zrobić, przycinając kandydata do prostokąta zapytania i porównując jego lewy dolny róg z bieżącą lokalizacją. Jeśli jest to dopasowanie, zgłaszamy, w przeciwnym razie pomijamy.
Wstawianie i usuwanie
Wstawianie jest liniowe w stosunku do liczby koszy, które przecina kandydat, ponieważ wstawianie kandydata do 1 pojemnika jest czasem stałym. Usunięcie jest droższe, ponieważ musimy przeszukać pojedynczo połączoną listę każdego kosza, z którym przecina się kandydat.
W środowisku wielowątkowym operacje wstawiania, usuwania i zapytania wzajemnie się wykluczają. Jednak zamiast blokowania całej struktury danych, można zablokować podzakres pojemników. Należy przeprowadzić szczegółową analizę wydajności, aby uzasadnić narzut.
Wydajność i strojenie
Analiza jest podobna do tabeli skrótów . Najgorszy scenariusz jest taki, że wszyscy kandydaci są skoncentrowani w jednym pojemniku. Wtedy zapytanie to O( n ), usuwanie to O( n ), a wstawka to O(1), gdzie n to liczba kandydatów. Jeśli kandydaci są równomiernie rozmieszczeni, tak że każdy kosz ma stałą liczbę kandydatów, zapytanie to O( k ), gdzie k to liczba koszy, które przecina prostokąt zapytania. Wstawianie i usuwanie to O( m ), gdzie m to liczba koszy, które przecina wstawiający kandydat. W praktyce usuwanie jest znacznie wolniejsze niż wstawianie.
Podobnie jak w przypadku tablicy mieszającej, wydajność kosza zależy w dużej mierze od rozkładu zarówno lokalizacji, jak i rozmiaru kandydatów i zapytań. Ogólnie rzecz biorąc, im mniejszy prostokąt zapytania, tym bardziej wydajne zapytanie. Rozmiar pojemnika powinien być taki, aby zawierał jak najmniej kandydatów, ale wystarczająco duży, aby kandydaci nie zajmowali zbyt wielu pojemników. Jeśli kandydat obejmuje wiele koszy, zapytanie musi wielokrotnie pomijać tego kandydata po zgłoszeniu go w pierwszym koszu przecięcia. Na przykład na rysunku E jest odwiedzane 4 razy w zapytaniu o Q , więc musi zostać pominięte 3 razy.
Aby jeszcze bardziej przyspieszyć zapytanie, podziały można zastąpić przesunięciami w prawo . Wymaga to, aby liczba pojemników wzdłuż kierunku osi była wykładnikiem 2.
W porównaniu z innymi strukturami danych zapytań o zakres
W stosunku do drzewa k -d struktura bin umożliwia wydajne wstawianie i usuwanie bez złożoności ponownego równoważenia. Może to być bardzo przydatne w algorytmach, które muszą stopniowo dodawać kształty do struktury danych wyszukiwania.
Zobacz też
- k -d drzewo to kolejna wydajna struktura danych zapytania o zakres
- Podział przestrzeni
- Kwantyzacja (przetwarzanie sygnału)