W poprzednich częściach (, ) mówiliśmy o wektorach globalnych jako drzewach, a w tej omówimy wektory globalne jako rozrzedzone macierze.
to rodzaj macierzy, w której większość wartości ma tę samą wartość.
W praktyce często spotyka się tak ogromne rozrzedzone macierze, że nie ma sensu zajmować pamięci identycznymi elementami. Dlatego ma sens realizować rozrzedzone macierze w sposób, który nie marnuje pamięci na przechowywanie tych samych wartości.
W niektórych językach programowania rozrzedzone macierze są integralną częścią języka, , . W innych językach programowania są specjalne biblioteki, które umożliwiają ich realizację. Dla C++ — itd.
Wektory globalne są dobrymi kandydatami do realizacji rozrzedzonych macierzy, ponieważ:
- Przechowują wartości tylko określonych węzłów i nie przechowują wartości nieokreślonych;
- Interfejs dostępu do wartości węzła jest niezwykle podobny do sposobu, w jaki w wielu językach programowania realizowany jest dostęp do elementu macierzy wielowymiarowej.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global to dość niskopoziomowa struktura do przechowywania danych, dlatego ma bardzo dobre parametry szybkości (od setek tysięcy do dziesiątek milionów transakcji na sekundę w zależności od sprzętu, zob. )
Ponieważ global to struktura persistentna, więc ma sens realizować rozrzedzone macierze na nich, gdy wiadomo z góry, że dostępna pamięć RAM będzie niewystarczająca.
Jedną z cech realizacji rozrzedzonych macierzy jest zwracanie pewnej wartości domyślnej, jeśli dostęp odbywa się do nieokreślonej komórki.
Można to zrealizować za pomocą funkcji w COS. W tym przykładzie rozważono macierz 3-wymiarową.
USTAW a = $GET(^a(x,y,z), defValue)W jakich zadaniach wymagane są rozrzedzone macierze i jak mogą pomóc wektory globalne?
Macierz sąsiedztwa (połączeniowa)
służą do reprezentacji grafów:
Jasne jest, że im większy graf, tym więcej zer znajdzie się w macierzy. Na przykład, jeśli weźmiemy graf sieci społecznej i przedstawimy go w postaci takiej macierzy, to prawie w całości będzie się składał z zer, tzn. będzie rozrzedzoną macierzą.
Ustaw ^m(id1, id2) = 1
Ustaw ^m(id1, id3) = 1
Ustaw ^m(id1, id4) = 1
Ustaw ^m(id1) = 3
Ustaw ^m(id2, id4) = 1
Ustaw ^m(id2, id5) = 1
Ustaw ^m(id2) = 2
....
W tym przykładzie zapisujemy w globalnej zmiennej ^m macierz sąsiedztwa, a także liczbę krawędzi dla każdego węzła (kto jest z kim w przyjaźni i liczba przyjaciół).
Jeśli liczba elementów w grafie nie przekracza 29 milionów (ta liczba jest brana jako iloczyn 8 * ), istnieje jeszcze bardziej oszczędny sposób przechowywania takich macierzy — ciągi bitowe, ponieważ ich realizacja w specjalny sposób optymalizuje duże przerwy.
Operacje na ciągach bitowych są realizowane przez funkcję .
; ustawienie bitu
SET $BIT(rowID, positionID) = 1
; pobranie bitu
Write $BIT(rowID, positionID)
Tabela przejść automatu skończonego
Ponieważ graf przejść automatu skończonego to zwykły graf, tabela przejść automatu skończonego to ta sama macierz sąsiedztwa, o której wspomniano powyżej.
Automaty komórkowe
Najbardziej znanym automatem komórkowym jest , która z powodu swoich reguł (gdy komórka ma zbyt wielu sąsiadów — umiera) stanowi rzadki zbiór.
Steven Wolfram uważa, że automaty komórkowe to . W 2002 roku publikuje 1280-stronicową książkę „Nowy rodzaj nauki”, w której szeroko argumentuje, że osiągnięcia w dziedzinie automatów komórkowych nie są zjawiskami izolowanymi, ale stosunkowo trwałymi i mają ogromne znaczenie dla wszystkich dziedzin nauki.
Udowodniono, że każdy algorytm, który może być wykonany na komputerze, można zrealizować przy pomocy automatu komórkowego. Automaty komórkowe są wykorzystywane do modelowania dynamicznych środowisk i systemów, do rozwiązywania problemów algorytmicznych i dla innych celów.
Jeśli mamy ogromne pole i musimy zapisywać wszystkie pośrednie stany automatu komórkowego, to całkiem sensowne jest użycie globalnych zmiennych.
Kartografia
Pierwsze, co przychodzi mi na myśl, gdy mowa o zastosowaniach rzadkich zbiorów, to zadania kartograficzne.
Zazwyczaj na mapach jest bardzo wiele pustych przestrzeni. Jeśli mapę przedstawić w postaci dużych pikseli, to 71% pikseli Ziemi będzie zajęte przez oceany. Rzadki zbiór. A jeśli nanosić tylko ślady działalności człowieka, to pustej przestrzeni będzie ponad 95%.
Oczywiście nikt nie przechowuje map w postaci rastrowych zbiorów, używa się reprezentacji wektorowej.
Czym są mapy wektorowe? To pewnego rodzaju ramka składająca się z punktów, polilinii i wielokątów.
Faktycznie jest to baza danych punktów oraz relacji między nimi.
Jednym z najbardziej ambitnych zadań kartografii jest misja kartowania naszej galaktyki teleskopem Gaia. Obrazowo mówiąc, nasza galaktyka, podobnie jak cały wszechświat, to rozrzedzona struktura: ogromne przestrzenie pustki, w których znajdują się rzadkie małe punkty – gwiazdy. Miejsca pustego jest 99,999999…….%. Do przechowywania mapy naszej galaktyki wybrano bazę danych globalnych – Caché.
Nie znam dokładnej struktury globalnych w tym projekcie, mogę przypuszczać, że to coś podobnego do:
Set ^galaxy(b, l, d) = 1; Numer gwiazdy w katalogu, jeśli jest
Set ^galaxy(b, l, d, "name") = "Słońce"
Set ^galaxy(b, l, d, "type") = "normal" ; opcje: blackhole, quasar, red_dwarf itd.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Merkury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Gdzie b, l, d – to i odległość do Słońca.
Elastyczna struktura globalnych pozwala zachować wszelkie potrzebne cechy gwiazd i planet, ponieważ bazy na globalnych są bezschemowe.
Caché wybrano do przechowywania mapy naszego wszechświata nie tylko ze względu na elastyczność, ale również zdolność bardzo szybkiego zapisywania strumienia danych, jednocześnie tworząc indeksowe globalne dla szybkiego przeszukiwania.
Jeśli wrócimy na Ziemię, to na globalnych stworzono projekty kartograficzne i fork OpenStreetMap – .
Niedawno na zrealizowano indeksy geoprzesztrzenne . Oczekujemy od autorów artykułu szczegółów realizacji.
Realizacja indeksów przestrzennych na globalnych w OpenStreetMap XAPI
Obrazy pochodzą z .
Cała Ziemia dzielona jest na kwadraty, następnie na mniejsze kwadraty, a te na kolejne mniejsze kwadraty i tak dalej. Ostatecznie uzyskujemy hierarchiczną strukturę dla której stworzono globalne.
W każdej chwili możemy praktycznie natychmiast zażądać potrzebnego kwadratu lub go oczyścić, przy tym wszystkie podkwadraty także zostaną zwrócone lub oczyszczone.
Podobną koncepcję na globalnych można zrealizować na kilka sposobów.
Opcja 1:
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 1) = idPierwszegoPunktu
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 2) = idDrugiegoPunktu
...Opcja 2:
Ustaw ^m('abacdabcdabacdabcda', 1) = idPierwszegoPunktu
Ustaw ^m('abacdabcdabacdabcda', 2) = idDrugiegoPunktu
...W obu przypadkach nie ma problemu z wymaganiem punktów znajdujących się w kwadracie dowolnego poziomu na COS/M. Nieco łatwiej będzie czyścić kwadratowe kawałki przestrzeni dowolnego poziomu w pierwszej wersji, ale to rzadko jest potrzebne.
Przykład jednego z kwadracików dolnego poziomu:
A oto kilka globalnych z projektu XAPI: przedstawienie indeksu na globalach:
Globalny ^way używany do przechowywania punktów (dróg, małych rzek itp.) i poligonów (zamknięte obszary: budynki, lasy itp.).
Grubą klasyfikacja użycia rzadkich tablic w globalach.
- Przechowujemy współrzędne pewnych obiektów i ich stany (mapowanie, automaty komórkowe)
- Przechowujemy rzadkie macierze.
Dla przypadku 2) przy żądaniu określonej współrzędnej, gdzie elementowi nie przypisano wartości, musimy uzyskać wartość elementu rzadkiej tablicy domyślnie.
Zyski, które uzyskujemy przy przechowywaniu wielowymiarowych macierzy w globalach
Szybkie usuwanie i/lub próbkowanie kawałków przestrzeni, wielokrotnych wierszy, płaszczyzn, sześcianów itd. W przypadkach, gdy używane są indeksy całkowite, może być przydatna możliwość szybkiego usuwania i/lub próbkowania kawałków przestrzeni, wielokrotnych wierszy, płaszczyzn, sześcianów itd.
Komendą możemy usunąć zarówno pojedynczy element, jak i wiersz, a nawet całą płaszczyznę. Dzięki właściwościom globali, dzieje się to bardzo szybko — tysiące razy szybciej niż usuwanie element po elemencie.
Na rysunku przedstawiono trójwymiarową tablicę w globalu ^a i różne rodzaje usunięć.
Aby wybrać kawałki przestrzeni według znanych indeksów, można użyć polecenia .
Wybór kolumny macierzy do zmiennej Column:
; Zdefiniujemy trójwymiarową rzadką tablicę 3x3x3
Ustaw ^a(0,0,0)=1,^a(2,2,0)=1,^a(2,0,1)=1,^a(0,2,1)=1,^a(2,2,2)=1,^a(2,1,2)=1
Merge Column = ^a(2,2)
; Wyświetlimy zmienną Column
Zwrite Column
Wynik:
Column(0)=1
Column(2)=1
Co ciekawe, w zmiennej Column również mamy rzadką tablicę, do której należy odwoływać się również przez , ponieważ wartości domyślne w niej nie są przechowywane.
Wybór kawałków przestrzeni może być również realizowany przez mały program z użyciem funkcji . Jest to szczególnie wygodne w przestrzeniach, których indeksy nie są kwantowane (kartografia).
Podsumowanie
Obecne czasy stawiają nowe ambitne zadania. Grafy mogą składać się z miliardów węzłów, mapy z miliardów punktów, a ktoś może nawet chcieć uruchomić swój własny wszechświat na automatach komórkowych (, ).
Gdy objętość danych rzadkich macierzy już nie może być pomieszczona w pamięci operacyjnej, a praca z nimi jest konieczna, warto rozważyć możliwość realizacji takich projektów na globalach i COS.
Dziękujemy za uwagę! Czekamy na wasze pytania i sugestie w komentarzach.
Zrzeczenie się odpowiedzialności: Ten artykuł i moje komentarze do niego są moją opinią i nie mają związku z oficjalnym stanowiskiem korporacji InterSystems.
Źródło: habr.com
