W poprzednich częściach (, ) mówiliśmy o obiektach globalnych jako o drzewach, w tym przypadku będziemy patrzeć na obiekty globalne jako na rzadkie tablice.
to rodzaj tablicy, w której większość wartości przyjmuje tę samą wartość.
W praktyce rzadkie tablice są często tak duże, że nie ma sensu zajmować pamięci identycznymi elementami. Dlatego sensowne jest implementowanie rzadkich tablic w taki sposób, aby pamięć nie była marnowana na przechowywanie identycznych wartości.
W niektórych językach programowania rzadkie tablice są zawarte w samym języku, , . Inne języki programowania posiadają specjalne biblioteki, które pozwalają na ich implementację. Dla C++ - et al.
Globale są dobrymi kandydatami do implementacji rzadkich tablic, ponieważ:
- Przechowują wartości tylko niektórych węzłów i nie przechowują wartości niezdefiniowanych;
- Interfejs dostępu do wartości węzła jest niezwykle podobny do tego, jak wiele języków programowania implementuje dostęp do wielowymiarowego elementu tablicy.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global to dość niskopoziomowa struktura do przechowywania danych, dlatego charakteryzuje się wyjątkową szybkością (od setek tysięcy do dziesiątków milionów transakcji na sekundę, w zależności od sprzętu, patrz poniżej). )
Ponieważ global jest strukturą trwałą, sensowne jest tworzenie na nich rzadkich tablic, gdy wiadomo z góry, że ilość pamięci RAM nie będzie wystarczająca.
Jedną z właściwości implementacji tablic rzadkich jest zwrócenie wartości domyślnej w przypadku uzyskania dostępu do niezdefiniowanej komórki.
Można to zaimplementować za pomocą funkcji w COSie. W tym przykładzie rozważono tablicę trójwymiarową.
SET a = $GET(^a(x,y,z), defValue)Jakie zadania wymagają rzadkich tablic i jak globale mogą pomóc?
Macierz sąsiedztwa (połączenia).
używany do przedstawiania wykresów:
Oczywiście im większy wykres, tym więcej zer będzie w macierzy. Jeśli na przykład weźmiemy wykres sieci społecznościowej i przedstawimy go w postaci podobnej macierzy, to będzie on prawie w całości składał się z zer, tj. będzie rzadką tablicą.
Set ^m(id1, id2) = 1
Set ^m(id1, id3) = 1
Set ^m(id1, id4) = 1
Set ^m(id1) = 3
Set ^m(id2, id4) = 1
Set ^m(id2, id5) = 1
Set ^m(id2) = 2
....
W tym przykładzie oszczędzamy globalnie ^m macierz łączności, a także liczbę krawędzi w każdym węźle (kto z kim się przyjaźni i liczba znajomych).
Jeżeli liczba elementów na wykresie nie jest większa niż 29 milionów (liczbę tę przyjmuje się jako iloczyn 8 * ), czyli jeszcze bardziej ekonomicznym sposobem przechowywania takich macierzy są ciągi bitów, ponieważ ich implementacja w specjalny sposób optymalizuje duże luki.
Manipulacje ciągami bitowymi są wykonywane przez funkcję .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabela przejść maszyny stanów
Ponieważ wykres przejść automatu skończonego jest wykresem zwyczajnym, wówczas tablica przejść automatu skończonego jest tą samą macierzą sąsiedztwa omówioną powyżej.
Automaty komórkowe
Najbardziej znanym automatem komórkowym jest , która ze względu na swoje zasady (kiedy komórka ma wielu sąsiadów, umiera) jest tablicą rzadką.
Stephen Wolfram uważa, że automaty komórkowe tak . W 2002 roku opublikował 1280-stronicową książkę A New Kind of Science, w której ogólnie argumentuje, że postęp w automatach komórkowych nie jest odosobniony, ale jest trwały i ma ogromne implikacje dla wszystkich dziedzin nauki.
Udowodniono, że dowolny algorytm wykonywalny na komputerze można zaimplementować za pomocą automatu komórkowego. Automaty komórkowe służą do modelowania dynamicznych środowisk i systemów, rozwiązywania problemów algorytmicznych i do innych celów.
Jeśli mamy ogromne pole i musimy rejestrować wszystkie stany pośrednie automatu komórkowego, wtedy sensowne jest użycie globali.
Kartografia
Pierwszą rzeczą, która przychodzi mi na myśl, jeśli chodzi o używanie rzadkich tablic, są zadania mapowania.
Z reguły na mapach jest dużo pustego miejsca. Jeśli mapa jest przedstawiona jako duże piksele, wówczas 71% pikseli Ziemi będzie zajmowane przez ocean. Rzadka tablica. A jeśli zastosujesz tylko dzieła ludzkich rąk, pusta przestrzeń będzie większa niż 95%.
Oczywiście nikt nie przechowuje map w postaci tablic rastrowych; używana jest reprezentacja wektorowa.
Ale czym są mapy wektorowe? Jest to rodzaj ramki oraz polilinii i wielokątów składających się z punktów.
Zasadniczo baza danych punktów i połączeń między nimi.
Jedną z najbardziej ambitnych misji mapowych jest misja Teleskopu Gaia, której zadaniem jest mapowanie naszej galaktyki. Mówiąc obrazowo, nasza galaktyka, podobnie jak cały wszechświat, jest ciągłym, rzadkim układem: ogromnymi przestrzeniami pustki, w których znajdują się rzadkie małe punkty - gwiazdy. Pusta przestrzeń to 99,999999….%. Do przechowywania mapy naszej galaktyki wybrano globalną bazę danych - Caché.
Nie znam dokładnej struktury globali w tym projekcie, mogę założyć, że jest to coś podobnego do:
Set ^galaxy(b, l, d) = 1; Номер звезды по каталогу, если есть
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal" ; варианты blackhole, quazar, red_dwarf и т.д.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Gdzie b, l, d są i odległość do Słońca.
Elastyczna struktura globali pozwala zapisać wszelkie niezbędne cechy gwiazd i planet, ponieważ bazy na globalach są pozbawione schematów.
Do przechowywania mapy naszego wszechświata wybrano Caché nie tylko ze względu na jego elastyczność, ale także możliwość bardzo szybkiego przechowywania strumienia danych, przy jednoczesnym tworzeniu globalnych indeksów do szybkich wyszukiwań.
Jeśli wrócimy na Ziemię, to na globalach powstały projekty kartograficzne i rozwidlenie OpenStreetMap - .
Ostatnio na zaimplementowano indeksy geoprzestrzenne . Czekamy na artykuł autorów ze szczegółami wdrożenia.
Implementacja indeksów przestrzennych na skalę globalną w OpenStreetMap XAPI
Zdjęcia zrobione z .
Cały glob jest podzielony na kwadraty, następnie na podkwadraty, a podkwadraty na podkwadraty i tak dalej. Ogólnie rzecz biorąc, otrzymujemy hierarchiczną strukturę przechowywania utworzonych globalów.
W dowolnym momencie możemy niemal natychmiast poprosić o żądane pole lub je wyczyścić, a wszystkie podkwadraty również zostaną zwrócone lub wyczyszczone.
Podobny schemat na globalach można wdrożyć 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) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...Opcja 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...W obu przypadkach nie jest trudno użyć COS/M do zażądania punktów znajdujących się w kwadracie dowolnego poziomu. W pierwszej opcji nieco łatwiej będzie wyczyścić kwadratowe kawałki przestrzeni na dowolnym poziomie, ale rzadko jest to konieczne.
Przykład jednego z kwadratów niższego poziomu:
A oto kilka globali z projektu XAPI: reprezentacja indeksu na globalach:
światowy ^sposób służy do przechowywania punktów (drogi, małe rzeki itp.) i wielokąty (tereny zamknięte: budynki, lasy itp.).
Zgrubna klasyfikacja użycia rzadkich tablic w obiektach globalnych.
- Przechowujemy współrzędne niektórych obiektów i ich stany (mapowanie, automaty komórkowe)
- Przechowujemy rzadkie macierze.
W przypadku 2), żądając określonej współrzędnej, gdy element nie ma przypisanej wartości, musimy uzyskać wartość domyślnego elementu tablicy rzadkiej.
Premie jakie otrzymujemy przy przechowywaniu macierzy wielowymiarowych w globalach
Szybko usuwaj i/lub zaznaczaj fragmenty przestrzeni będące wielokrotnościami rzędów, płaszczyzn, sześcianów itp. W przypadkach, gdy używane są indeksy całkowite, użyteczna może być możliwość szybkiego usuwania i/lub pobierania fragmentów przestrzeni będących wielokrotnościami wierszy, płaszczyzn, kostek itp.
zespół możemy usunąć pojedynczy element lub rząd, 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.
Rysunek przedstawia trójwymiarową tablicę w układzie globalnym ^a i różne rodzaje usunięć.
Aby wybrać fragmenty przestrzeni przy użyciu znanych indeksów, możesz użyć polecenia .
Wybór kolumny macierzy do zmiennej Column:
; Зададим трёхмерный разреженный массив 3x3x3
Set ^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)
; Выведем переменную Column
Zwrite Column
Wnioski:
Column(0)=1
Column(2)=1
Interesujące w zmiennej Column jest to, że mamy również rzadką tablicę, do której również trzeba uzyskać dostęp , ponieważ wartości domyślne nie są w nim przechowywane.
Wybór fragmentów przestrzeni można również wykonać za pomocą małego programu korzystającego z tej funkcji . Jest to szczególnie wygodne w przypadku przestrzeni, których indeksy nie są skwantowane (kartografia).
wniosek
Obecne czasy stawiają przed nami nowe ambitne zadania. Wykresy mogą składać się z miliardów wierzchołków, mapy z miliardów punktów, a niektórzy mogą nawet chcieć uruchomić własny wszechświat na automatach komórkowych (, ).
Kiedy ilość danych z rzadkich tablic nie mieści się już w pamięci RAM, ale trzeba z nimi pracować, wówczas warto rozważyć możliwość realizacji podobnych projektów na globalach i COS.
Dziękuję za uwagę! Czekamy na Twoje pytania i życzenia w komentarzach.
Odpowiedzialność: Niniejszy artykuł i moje komentarze do niego są moją opinią i nie mają związku z oficjalnym stanowiskiem InterSystems Corporation.
Źródło: www.habr.com