Oldingi qismlarda (, ) biz globallar haqida daraxtlar sifatida gaplashdik, bunda biz globallarni siyrak massivlar sifatida ko'rib chiqamiz.
ko'pchilik qiymatlari bir xil qiymatga ega bo'lgan massiv turidir.
Amalda, siyrak massivlar ko'pincha shunchalik kattaki, xotirani bir xil elementlar bilan egallashdan ma'no yo'q. Shuning uchun, siyrak massivlarni xotira bir xil qiymatlarni saqlashga sarflamaydigan tarzda amalga oshirish mantiqiy.
Ba'zi dasturlash tillarida siyrak massivlar tilning o'ziga kiritilgan, , . Boshqa dasturlash tillarida ularni amalga oshirish imkonini beruvchi maxsus kutubxonalar mavjud. C++ uchun - va boshq.
Globallar siyrak massivlarni amalga oshirish uchun yaxshi nomzodlardir, chunki:
- Ular faqat ma'lum tugunlarning qiymatlarini saqlaydi va aniqlanmaganlarning qiymatlarini saqlamaydi;
- Tugun qiymatiga kirish interfeysi ko'p o'lchovli massiv elementiga kirishni qancha dasturlash tillari amalga oshirishiga juda o'xshaydi.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global - bu ma'lumotlarni saqlash uchun juda past darajadagi tuzilma, shuning uchun u ajoyib tezlik xususiyatlariga ega (apparatga qarab sekundiga yuz minglab o'n millionlab tranzaksiyalar, pastga qarang). )
Global doimiy tuzilma bo'lganligi sababli, RAM miqdori etarli bo'lmasligi oldindan ma'lum bo'lganda, ularda siyrak massivlarni yaratish mantiqan to'g'ri keladi.
Siyrak massiv ilovalarining xususiyatlaridan biri, agar aniqlanmagan yacheykaga kirish amalga oshirilgan bo'lsa, ba'zi bir standart qiymatni qaytarishdir.
Bu funksiya yordamida amalga oshirilishi mumkin COS da. Ushbu misol 3 o'lchovli massivni ko'rib chiqadi.
SET a = $GET(^a(x,y,z), defValue)Qanday vazifalar siyrak massivlarni talab qiladi va globallar qanday yordam berishi mumkin?
Qo'shnilik (bog'lanish) matritsasi
grafiklarni ifodalash uchun ishlatiladi:
Shubhasiz, grafik qanchalik katta bo'lsa, matritsada shuncha ko'p nollar bo'ladi. Agar, masalan, biz ijtimoiy tarmoq grafigini olib, uni shunga o'xshash matritsa shaklida taqdim qilsak, u deyarli butunlay nollardan iborat bo'ladi, ya'ni. siyrak massiv bo'ladi.
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
....
Ushbu misolda biz global miqyosda tejaymiz ^m ulanish matritsasi, shuningdek, har bir tugundagi qirralarning soni (kim kim bilan do'st va do'stlar soni).
Grafikdagi elementlar soni 29 milliondan oshmasa (bu raqam 8 * ko'paytmasi sifatida olinadi) ), ya'ni bunday matritsalarni saqlashning yanada tejamkor usuli bit satrlaridir, chunki ularni amalga oshirish katta bo'shliqlarni maxsus tarzda optimallashtiradi.
Bit satrlari bilan manipulyatsiyalar funksiya tomonidan amalga oshiriladi .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Davlat mashinasi o'tish jadvali
Cheklangan avtomatning o'tish grafigi oddiy grafik bo'lgani uchun, u holda chekli avtomatning o'tish jadvali yuqorida muhokama qilingan bir xil qo'shnilik matritsasidir.
Uyali avtomatlar
Eng mashhur uyali avtomat , bu o'z qoidalariga ko'ra (hujayraning qo'shnilari ko'p bo'lsa, u o'ladi) siyrak massivdir.
Stiven Volfram uyali avtomatlar ekanligiga ishonadi . 2002 yilda u 1280 betlik "Yangi fan turi" kitobini nashr etdi, unda u uyali avtomatlardagi yutuqlar alohida emas, balki barqaror va fanning barcha sohalari uchun katta ta'sir ko'rsatishini keng ta'kidlaydi.
Kompyuterda bajariladigan har qanday algoritmni uyali avtomat yordamida amalga oshirish mumkinligi isbotlangan. Uyali avtomatlar dinamik muhit va tizimlarni modellashtirish, algoritmik muammolarni hal qilish va boshqa maqsadlarda qo'llaniladi.
Agar bizda ulkan maydon bo'lsa va biz uyali avtomatning barcha oraliq holatini qayd etishimiz kerak bo'lsa, u holda globallardan foydalanish mantiqan.
Kartografiya
Siyrak massivlardan foydalanish haqida gap ketganda xayolimga keladigan birinchi narsa bu vazifalarni xaritalashdir.
Qoidaga ko'ra, xaritalarda juda ko'p bo'sh joy mavjud. Agar xarita katta piksellar bilan ifodalangan bo'lsa, u holda Yer piksellarining 71 foizini okean egallaydi. Noyob massiv. Va agar siz faqat inson qo'li asarlarini qo'llasangiz, unda bo'sh joy 95% dan ortiq bo'ladi.
Albatta, hech kim xaritalarni rastr massivlari ko'rinishida saqlamaydi, vektor tasviridan foydalaniladi.
Ammo vektor xaritalari nima? Bu nuqtalardan tashkil topgan ramka va poliliniyalar va ko'pburchaklarning bir turi.
Aslida nuqtalar va ular orasidagi bog'lanishlar ma'lumotlar bazasi.
Xaritalash bo'yicha eng katta missiyalardan biri bu Gaia teleskopi bizning galaktikamizni xaritalashdir. Majoziy ma'noda aytganda, bizning galaktikamiz, butun koinot kabi, doimiy siyrak massiv: noyob kichik nuqtalar - yulduzlar mavjud bo'lgan ulkan bo'shliqlar. Boʻsh joy 99,999999…….%. Galaktikamiz xaritasini saqlash uchun global ma'lumotlar bazasi tanlandi - Caché.
Men ushbu loyihada globallarning aniq tuzilishini bilmayman, men buni shunga o'xshash narsa deb taxmin qilishim mumkin:
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
...
Bu erda b, l, d va Quyoshgacha bo'lgan masofa.
Globallarning moslashuvchan tuzilishi yulduzlar va sayyoralarning har qanday kerakli xususiyatlarini saqlashga imkon beradi, chunki global asoslar sxemasizdir.
Bizning koinot xaritasini saqlash uchun Caché nafaqat moslashuvchanligi, balki ma'lumotlar oqimini juda tez saqlash va bir vaqtning o'zida tezkor qidiruvlar uchun global indekslarni yaratish qobiliyati uchun tanlangan.
Agar biz Yerga qaytsak, global miqyosda kartografik loyihalar yaratilgan va OpenStreetMap vilkasi - .
Yaqinda geofazoviy indekslar amalga oshirildi . Biz mualliflardan amalga oshirish tafsilotlari bilan maqola kutmoqdamiz.
OpenStreetMap XAPI-da fazoviy indekslarni global miqyosda amalga oshirish
dan olingan suratlar .
Butun globus kvadratlarga, keyin pastki kvadratlarga va kichik kvadratlarga bo'linadi va hokazo. Umuman olganda, biz qaysi globallar yaratilganligini saqlash uchun ierarxik tuzilmani olamiz.
Istalgan vaqtda biz deyarli bir zumda kerakli kvadratni so'rashimiz yoki uni tozalashimiz mumkin va barcha pastki kvadratlar ham qaytariladi yoki tozalanadi.
Globallar bo'yicha shunga o'xshash sxema bir necha usul bilan amalga oshirilishi mumkin.
1 variant:
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ВторойТочки
...2 variant:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Ikkala holatda ham istalgan darajadagi kvadratda joylashgan nuqtalarni so'rash uchun COS/M dan foydalanish qiyin emas. Birinchi variantda har qanday darajadagi kvadrat bo'laklarni tozalash biroz osonroq bo'ladi, ammo bu kamdan-kam hollarda kerak.
Pastki darajadagi kvadratlardan biriga misol:
Va bu erda XAPI loyihasidan bir nechta globallar: globallar bo'yicha indeks taqdimoti:
global ^ yo'l nuqtalarni saqlash uchun ishlatiladi (yo'llar, kichik daryolar va boshqalar) va ko'pburchaklar (yopiq joylar: binolar, o'rmonlar va boshqalar).
Globallarda siyrak massivlardan foydalanishning taxminiy tasnifi.
- Biz ba'zi ob'ektlarning koordinatalarini va ularning holatini saqlaymiz (xaritalash, uyali avtomatlar)
- Biz siyrak matritsalarni saqlaymiz.
2-holat uchun) elementga qiymat tayinlanmagan aniq koordinatani so'rashda biz standart siyrak massiv elementining qiymatini olishimiz kerak.
Global miqyosda ko'p o'lchovli matritsalarni saqlashda oladigan bonuslar
Qatorlar, tekisliklar, kublar va hokazolarning ko'p bo'lgan bo'sh joy qismlarini tezda olib tashlang va/yoki tanlang. Butun sonli indekslar qo'llaniladigan hollarda qatorlar, tekisliklar, kublar va hokazolarning ko'p bo'lgan bo'sh joy qismlarini tezda olib tashlash va/yoki olish imkoniyati foydali bo'lishi mumkin.
jamoa biz bitta elementni yoki qatorni yoki hatto butun tekislikni o'chirib tashlashimiz mumkin. Globallarning xususiyatlari tufayli bu juda tez sodir bo'ladi - elementni elementni olib tashlashdan minglab marta tezroq.
Rasmda global miqyosda uch o'lchovli massiv ko'rsatilgan ^a va turli xil o'chirish turlari.
Ma'lum indekslar yordamida bo'sh joy bo'laklarini tanlash uchun siz buyruqdan foydalanishingiz mumkin .
Ustun o'zgaruvchisiga matritsa ustunini tanlash:
; Зададим трёхмерный разреженный массив 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
xulosa:
Column(0)=1
Column(2)=1
Column o'zgaruvchisining qiziq tomoni shundaki, bizda siyrak massiv ham bor, unga kirish orqali ham kirish mumkin. , chunki standart qiymatlar unda saqlanmaydi.
Bo'sh joy bo'laklarini tanlash funksiyadan foydalangan holda kichik dastur orqali ham amalga oshirilishi mumkin . Bu, ayniqsa, indekslari kvantlashtirilmagan (kartografiya) bo'shliqlar uchun qulaydir.
xulosa
Hozirgi zamon oldimizga yangi ulkan vazifalarni qo'ymoqda. Grafiklar milliardlab cho'qqilardan, xaritalar milliardlab nuqtalardan iborat bo'lishi mumkin va ba'zilari hatto uyali avtomatlarda o'z koinotlarini boshqarishni xohlashlari mumkin (, ).
Agar siyrak massivlardagi ma'lumotlar hajmi endi operativ xotiraga sig'masa, lekin siz ular bilan ishlashingiz kerak bo'lsa, global va COS-da shunga o'xshash loyihalarni amalga oshirish imkoniyatini ko'rib chiqishga arziydi.
E'tiboringiz uchun rahmat! Izohlarda savollar va tilaklaringizni kutamiz.
Masʼuliyatdan voz kechish: Ushbu maqola va mening sharhlarim mening fikrim va InterSystems korporatsiyasining rasmiy pozitsiyasiga aloqasi yo'q.
Manba: www.habr.com