Əvvəlki hissələrdə, ) biz qloballardan ağaclar kimi danışdıq, bunda qlobalları seyrək massivlər kimi nəzərdən keçirəcəyik.
dəyərlərin çoxunun eyni dəyəri aldığı bir massiv növüdür.
Praktikada tez-tez o qədər böyük seyrək massivlər var ki, yaddaşı eyni elementlərlə tutmağın mənası yoxdur. Buna görə də, seyrək massivləri elə həyata keçirmək məntiqlidir ki, yaddaş eyni dəyərlərin saxlanmasına sərf olunmasın.
Bəzi proqramlaşdırma dillərində seyrək massivlər dilin özünün bir hissəsidir, , . Digər proqramlaşdırma dillərində onları həyata keçirməyə imkan verən xüsusi kitabxanalar var. C++ üçün - və s.
Qloballar seyrək massivləri tətbiq etmək üçün yaxşı namizədlərdir, çünki:
- Onlar yalnız müəyyən edilmiş qovşaqların dəyərlərini saxlayır və qeyri-müəyyən olanların dəyərlərini saxlamırlar;
- Bir qovşağın dəyərinə daxil olmaq üçün interfeys, çoxölçülü massivin elementinə girişi neçə proqramlaşdırma dilinin həyata keçirdiyinə çox oxşardır.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Qlobal məlumatların saxlanması üçün kifayət qədər aşağı səviyyəli bir quruluşdur, buna görə də onlar əla sürət xüsusiyyətlərinə malikdirlər (aparatdan asılı olaraq saniyədə yüz minlərlə əməliyyatdan on milyonlarla əməliyyata qədər, aşağıya baxın). )
Qlobal davamlı bir quruluş olduğundan, RAM miqdarının kifayət etməyəcəyi əvvəlcədən məlum olduqda, onların üzərində seyrək massivlər etmək məna kəsb edir.
Seyrək massiv tətbiqlərinin xassələrindən biri, giriş qeyri-müəyyən xanaya olarsa, bəzi standart dəyəri qaytarmaqdır.
Bu funksiyadan istifadə etməklə edilə bilər COS-da. Bu nümunədə 3 ölçülü massiv nəzərdən keçirilir.
SET a = $GET(^a(x,y,z), defValue)Hansı vəzifələr seyrək massivlər tələb edir və qloballar necə kömək edə bilər?
Qonşuluq (əlaqəlilik) matrisi
qrafikləri təmsil etmək üçün istifadə olunur:
Aydındır ki, qrafik nə qədər böyük olsa, matrisdə bir o qədər çox sıfır olacaq. Məsələn, sosial şəbəkənin qrafikini götürsək və onu oxşar matris şəklində təqdim etsək, demək olar ki, hamısı sıfırlardan ibarət olacaq, yəni. seyrək massiv olacaq.
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
....
Bu nümunədə biz qlobal qənaət edirik ^m əlaqə matrisi, eləcə də hər bir qovşaqdakı kənarların sayı (kim kiminlə dostdur və dostların sayı).
Qrafikdəki elementlərin sayı 29 milyondan çox deyilsə (bu ədəd 8*-in hasili kimi qəbul edilir) ), yəni bu cür matrisləri saxlamağın daha qənaətcil yolu bit sətirləridir, çünki böyük boşluqlar onların həyata keçirilməsində xüsusi bir şəkildə optimallaşdırılır.
Bit sətirləri ilə manipulyasiyalar funksiya tərəfindən həyata keçirilir .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Dövlət Maşın Atlama Cədvəli
Dövlət maşınının keçid qrafiki adi bir qrafik olduğundan, dövlət maşınının keçid cədvəli yuxarıda müzakirə edilən eyni bitişiklik matrisidir.
Hüceyrə avtomatları
Ən məşhur mobil avtomat , bu, qaydalarına görə (bir hüceyrənin çoxlu qonşuları olduqda, ölür) seyrək massivdir.
Stephen Wolfram, mobil avtomatların olduğuna inanır . 2002-ci ildə o, 1280 səhifəlik bir kitab olan Yeni Bir Elm növü nəşr etdi və burada geniş şəkildə iddia edir ki, hüceyrə avtomatlarında irəliləyişlər təcrid olunmur, lakin çox sabitdir və elmin bütün sahələri üçün böyük əhəmiyyət kəsb edir.
Sübut edilmişdir ki, kompüterdə həyata keçirilə bilən istənilən alqoritm mobil avtomatdan istifadə etməklə həyata keçirilə bilər. Hüceyrə avtomatlarından dinamik mühitləri və sistemləri modelləşdirmək, alqoritmik məsələləri həll etmək və digər məqsədlər üçün istifadə olunur.
Əgər böyük bir sahəmiz varsa və hüceyrə avtomatının bütün aralıq vəziyyətlərini qeyd etməliyiksə, qloballardan istifadə etmək olduqca məqbuldur.
Kartoqrafiya
Seyrək massivlərdən istifadə dedikdə ağlıma ilk gələn şey xəritəçəkmə tapşırıqlarıdır.
Bir qayda olaraq, kartlarda çoxlu boş yer var. Xəritə böyük piksellərlə təmsil olunarsa, o zaman Yer kürəsinin piksellərinin 71%-ni okean tutacaq. Seyrək massiv. Və yalnız insan əllərinin əsərlərini tətbiq etsəniz, boş yerin 95% -dən çoxu olacaq.
Əlbəttə ki, heç kim xəritələri rastr massivləri kimi saxlamır, vektor təsvirindən istifadə olunur.
Bəs vektor xəritələri nədir? Bu, bir növ çərçivə və nöqtələrdən ibarət çoxbucaqlılar və çoxbucaqlıdır.
Əslində nöqtələr və onların arasındakı əlaqə məlumat bazası.
Ən iddialı xəritəçəkmə missiyalarından biri Gaia teleskopunun qalaktikamıza xəritəçəkmə missiyasıdır. Obrazlı desək, qalaktikamız, bütün kainat kimi, davamlı seyrək massivdir: nadir kiçik nöqtələrin - ulduzların olduğu böyük boşluqlar. Boş yer 99,999999…….%. Qalaktikamızın xəritəsini saxlamaq üçün qloballar üzrə verilənlər bazası - Caché seçildi.
Mən bu layihədə qlobalların dəqiq strukturunu bilmirəm, onun oxşar bir şey olduğunu güman edə bilərəm:
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
...
b, l, d haradadır və günəşdən uzaqlıq.
Qlobalların çevik strukturu ulduzların və planetlərin istənilən xüsusiyyətlərini saxlamağa imkan verir, çünki qlobalların əsasları sxemsizdir.
Kainatımızın xəritəsini saxlamaq üçün Caché təkcə çevikliyinə görə deyil, həm də sürətli axtarışlar üçün qlobal indekslər yaradaraq məlumat axını çox tez saxlamaq qabiliyyətinə görə seçilib.
Əgər biz Yerə qayıdırıqsa, o zaman qloballar üzərində kartoqrafik layihələr yaradılıb və OpenStreetMap çəngəl - .
Bu yaxınlarda geoməkan indeksləri həyata keçirilmişdir . Müəlliflərdən icra detalları ilə məqalələr gözləyirik.
OpenStreetMap XAPI-də qlobal məkanda məkan indekslərinin həyata keçirilməsi
Şəkillər götürülmüşdür .
Bütün yer kürəsi kvadratlara, sonra alt-kvadratlara, alt kvadratlar isə alt-kvadratlara bölünür və s. Ümumiyyətlə, hansı qlobalların yaradıldığını saxlamaq üçün iyerarxik bir quruluş əldə edirik.
İstənilən vaxt, demək olar ki, dərhal istədiyiniz kvadratı tələb edə və ya onu təmizləyə bilərik, eyni zamanda bütün alt kvadratlar da qaytarılacaq və ya təmizlənəcək.
Qloballarda belə bir sxem bir neçə yolla həyata keçirilə bilər.
Variantları 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ВторойТочки
...Variantları 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Hər iki halda COS/M-də istənilən səviyyəli kvadratda yerləşən nöqtələri tələb etmək çətin deyil. Birinci seçimdə istənilən səviyyənin kvadrat hissələrini təmizləmək bir qədər asan olacaq, lakin bu nadir hallarda lazımdır.
Aşağı səviyyəli kvadratlardan birinin nümunəsi:
Və burada XAPI layihəsindən bəzi qloballar: qloballar üzrə indeks təmsili:
qlobal ^ yol xal saxlamaq üçün istifadə olunur (yollar, dayaz çaylar və s.) və çoxbucaqlılar (qapalı ərazilər: binalar, meşələr və s.).
Qloballarda seyrək massivlərin istifadəsinin təxmini təsnifatı.
- Biz müəyyən obyektlərin koordinatlarını və onların vəziyyətlərini (xəritələmə, mobil avtomatlar) saxlayırıq.
- Biz seyrək matrisləri saxlayırıq.
2-ci hal üçün) elementə dəyər təyin olunmayan xüsusi koordinat tələb edərkən, biz defolt olaraq seyrək massivin elementinin qiymətini almalıyıq.
Qloballarda çoxölçülü matrisləri saxlayarkən əldə etdiyimiz bonuslar
Sürətli silinmə və/yaxud boşluq hissələrinin, sətirlərin, təyyarələrin, kubların və s. Tam indekslərin istifadə edildiyi hallar üçün sətirlərin, müstəvilərin, kubların və s. çoxluğu olan boşluq hissələrini cəld silmək və/yaxud seçmək faydalı ola bilər.
komanda biz həm tək elementi, həm də xətti, hətta bütün müstəvini silə bilərik. Qlobalların xassələri sayəsində bu, çox sürətlidir - element-elementlərin silinməsindən minlərlə dəfə sürətli.
Şəkil qlobal miqyasda üçölçülü massivi göstərir ^a və müxtəlif silmə növləri.
Məlum indekslər üzrə boşluq hissələrini seçmək üçün əmrdən istifadə edə bilərsiniz .
Sütun dəyişəninə matris sütununun seçilməsi:
; Зададим трёхмерный разреженный массив 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
Nəticə:
Column(0)=1
Column(2)=1
Sütun dəyişənində maraqlı olan, bizdə seyrək massiv də var, ona da daxil olmaq lazımdır. , çünki standart dəyərlər orada saxlanmır.
Məkan hissələrinin seçilməsi də funksiyadan istifadə edərək kiçik bir proqram vasitəsilə həyata keçirilə bilər . Bu, indeksləri kvantlaşdırılmayan (kartoqrafiya) fəzalarda xüsusilə əlverişlidir.
Nəticə
İndiki dövr qarşıya yeni iddialı vəzifələr qoyur. Qrafiklərin milyardlarla təpəsi, xəritələrin milyardlarla nöqtəsi ola bilər və kimsə hətta öz kainatını mobil avtomatlarda idarə etmək istəyə bilər (, ).
Seyrək massivlərin məlumatlarının miqdarı artıq RAM-a sığmayanda və onlarla işləmək lazım olduqda, qlobal və COS-da bu cür layihələrin həyata keçirilməsi imkanlarını nəzərdən keçirməyə dəyər.
Diqqətinizə görə təşəkkürlər! Suallarınızı və istəklərinizi şərhlərdə gözləyirik.
Məsuliyyətdən imtina: Bu məqalə və mənim şərhlərim mənim fikrimdir və InterSystems Corporation-ın rəsmi mövqeyini təmsil etmir.
Mənbə: www.habr.com