Գլոբալները գանձ-սրեր են տվյալների պահպանման համար: Նվազ զանգվածներ. Մաս 3

Նախորդ մասերում (1, 2) մենք խոսեցինք գլոբալների մասին որպես ծառերի, այս մեկում մենք կդիտարկենք գլոբալներին որպես նոսր զանգվածներ:

նոսր զանգված զանգվածի տեսակ է, որտեղ արժեքների մեծ մասն ընդունում է նույն արժեքը:

Գործնականում նոսր զանգվածները հաճախ այնքան հսկայական են, որ իմաստ չունի հիշողությունը զբաղեցնել նույնական տարրերով: Հետևաբար, իմաստ ունի նոսր զանգվածներ իրականացնել այնպես, որ հիշողությունը չվատնվի նույնական արժեքներ պահելու վրա:
Որոշ ծրագրավորման լեզուներում նոսր զանգվածները ներառված են հենց լեզվի մեջ, օրինակ Ջ, MATLAB. Ծրագրավորման այլ լեզուներն ունեն հատուկ գրադարաններ, որոնք թույլ են տալիս իրականացնել դրանք: C++-ի համար - Այգեն եւ այլն:

Գլոբալները լավ թեկնածուներ են նոսր զանգվածներ իրականացնելու համար, քանի որ.

1. Նրանք պահպանում են միայն որոշակի հանգույցների արժեքները և չեն պահում չսահմանվածների արժեքները.
2. Հանգույցի արժեքին մուտք գործելու ինտերֆեյսը չափազանց նման է այն բանին, թե քանի ծրագրավորման լեզու է իրականացնում մուտք դեպի բազմաչափ զանգվածի տարր:

   Set ^a(1, 2, 3)=5
   Write ^a(1, 2, 3)

3. Գլոբալը բավականին ցածր մակարդակի կառույց է տվյալների պահպանման համար, հետևաբար այն ունի արագության ակնառու բնութագրեր (վայրկյանում հարյուր հազարավորից մինչև տասնյակ միլիոնավոր գործարքներ, կախված սարքաշարից, տես ստորև): 1)

Քանի որ գլոբալը կայուն կառույց է, իմաստ ունի դրանց վրա ստեղծել նոսր զանգվածներ, երբ նախապես հայտնի է, որ RAM-ի քանակը չի բավարարի։

Հազվագյուտ զանգվածի ներդրման հատկություններից մեկն այն է, որ վերադարձնի որոշ լռելյայն արժեք, եթե մուտք է արվում դեպի չսահմանված բջիջ:

Սա կարող է իրականացվել գործառույթի միջոցով $GET COS-ում։ Այս օրինակը դիտարկում է եռաչափ զանգված:

SET a = $GET(^a(x,y,z), defValue)

Ի՞նչ առաջադրանքներ են պահանջում նոսր զանգվածներ և ինչպե՞ս կարող են գլոբալները օգնել:

Հարակից (կապակցման) մատրիցա

Նման մատրիցներ օգտագործվում է գրաֆիկները ներկայացնելու համար.

Ակնհայտ է, որ որքան մեծ է գրաֆիկը, այնքան ավելի շատ զրոներ կլինեն մատրիցայում: Եթե, օրինակ, վերցնենք սոցիալական ցանցի գրաֆիկը և այն ներկայացնենք նմանատիպ մատրիցայի տեսքով, ապա այն գրեթե ամբողջությամբ բաղկացած կլինի զրոներից, այսինքն. կլինի նոսր զանգված:

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
....

Այս օրինակում մենք խնայում ենք գլոբալ ^m կապի մատրիցա, ինչպես նաև յուրաքանչյուր հանգույցի եզրերի քանակը (ով ում հետ ընկերներ է և ընկերների թիվը):

Եթե ​​գծապատկերում տարրերի թիվը 29 միլիոնից ոչ ավելի է (այս թիվը ընդունվում է որպես 8*-ի արտադրյալ տողի առավելագույն չափը), այսինքն՝ նման մատրիցները պահելու նույնիսկ ավելի խնայող միջոցը բիթային տողերն են, քանի որ դրանց իրականացումը հատուկ կերպով օպտիմիզացնում է մեծ բացերը։

Բիթային տողերով մանիպուլյացիաները կատարվում են ֆունկցիայի միջոցով $BIT.

; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)

Պետական ​​մեքենայի անցումային աղյուսակ

Քանի որ վերջավոր ավտոմատի անցումային գրաֆիկը սովորական գրաֆիկ է, ուրեմն վերջավոր ավտոմատի անցումային աղյուսակը նույն հարևանության մատրիցն է, որը քննարկվել է վերևում։

Բջջային ավտոմատներ

Ամենահայտնի բջջային ավտոմատն է խաղ «Կյանք», որն իր կանոնների պատճառով (երբ բջիջը շատ հարևաններ ունի, այն մահանում է) նոսր զանգված է։

Սթիվեն Վոլֆրամը կարծում է, որ բջջային ավտոմատներն են գիտության նոր ոլորտ. 2002 թվականին նա հրատարակեց 1280 էջանոց գիրք՝ «Գիտության նոր տեսակ», որտեղ նա լայնորեն պնդում է, որ բջջային ավտոմատների առաջընթացը մեկուսացված չէ, այլ հարատև է և մեծ ազդեցություն ունի գիտության բոլոր ոլորտների համար:

Ապացուցված է, որ համակարգչի վրա գործարկվող ցանկացած ալգորիթմ կարող է իրականացվել բջջային ավտոմատի միջոցով: Բջջային ավտոմատներն օգտագործվում են դինամիկ միջավայրեր և համակարգեր մոդելավորելու, ալգորիթմական խնդիրներ լուծելու և այլ նպատակներով:

Եթե ​​մենք ունենք հսկայական դաշտ, և մենք պետք է գրանցենք բջջային ավտոմատի բոլոր միջանկյալ վիճակները, ապա իմաստ ունի օգտագործել գլոբալները:

Քարտեզագրություն

Առաջին բանը, որ գալիս է իմ մտքին, երբ խոսքը վերաբերում է նոսր զանգվածների օգտագործմանը, քարտեզագրման առաջադրանքներն են:

Որպես կանոն, քարտեզների վրա շատ դատարկ տեղ կա։ Եթե ​​քարտեզը ներկայացված է մեծ պիքսելներով, ապա Երկրի պիքսելների 71%-ը կզբաղեցնի օվկիանոսը։ Նվազ զանգված. Եվ եթե կիրառեք միայն մարդկային ձեռքի գործեր, ապա դատարկ տարածքը կկազմի ավելի քան 95%:

Իհարկե, ոչ ոք չի պահում քարտեզները ռաստերային զանգվածների տեսքով.
Բայց որո՞նք են վեկտորային քարտեզները: Սա մի տեսակ շրջանակ է և կետերից բաղկացած բազմագծեր և բազմանկյուններ:
Հիմնականում կետերի և դրանց միջև կապերի տվյալների բազան:

Ամենահավակնոտ քարտեզագրման առաքելություններից մեկը Gaia աստղադիտակի առաքելությունն է՝ մեր գալակտիկայի քարտեզագրման համար: Պատկերավոր ասած, մեր գալակտիկան, ինչպես ողջ տիեզերքը, շարունակական նոսր զանգված է. դատարկության հսկայական տարածություններ, որոնցում կան հազվագյուտ փոքր կետեր՝ աստղեր: Դատարկ տարածքը 99,999999…….%. Մեր գալակտիկայի քարտեզը պահելու համար ընտրվել է գլոբալ տվյալների բազա՝ «Caché»:

Ես չգիտեմ այս նախագծում գլոբալների ճշգրիտ կառուցվածքը, կարող եմ ենթադրել, որ դա նման է.

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 գալակտիկական կոորդինատները լայնություն, երկայնություն և հեռավորությունը Արևից:

Գլոբալների ճկուն կառուցվածքը թույլ է տալիս պահպանել աստղերի և մոլորակների ցանկացած անհրաժեշտ բնութագրիչ, քանի որ գլոբալների հիմքերը սխեմայով չեն:

Մեր տիեզերքի քարտեզը պահելու համար Caché-ն ընտրվել է ոչ միայն իր ճկունության, այլ նաև տվյալների հոսքը շատ արագ պահելու ունակության համար՝ միաժամանակ ստեղծելով ինդեքսային գլոբալներ արագ որոնումների համար:

Եթե ​​վերադառնանք Երկիր, ապա քարտեզագրական նախագծեր ստեղծվեցին գլոբալների վրա OpenStreetMap XAPI և OpenStreetMap-ի մի պատառաքաղ - FOOM.

Վերջերս վրա hackathon Cache իրականացվել են աշխարհատարածական ինդեքսներ Geospatial. Սպասում ենք հոդվածի հեղինակներից՝ իրականացման մանրամասներով։

OpenStreetMap XAPI-ում տարածական ինդեքսների ներդրում գլոբալ վրա

Նկարները վերցված են այս ներկայացումը.

Ողջ երկրագունդը բաժանված է քառակուսիների, այնուհետև ենթահրապարակների, իսկ ենթահրապարակները ենթահրապարակների և այլն: Ընդհանուր առմամբ, մենք ստանում ենք հիերարխիկ կառուցվածք, որը պահելու համար ստեղծվում են գլոբալները:

Ցանկացած պահի մենք կարող ենք գրեթե ակնթարթորեն պահանջել ցանկալի քառակուսին կամ մաքրել այն, և բոլոր ենթահրապարակները նույնպես կվերադարձվեն կամ կմաքրվեն:

Նմանատիպ սխեման գլոբալների վրա կարող է իրականացվել մի քանի ձևով.

Option 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ВторойТочки
...

Option 2:

Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...

Երկու դեպքում էլ դժվար չէ օգտագործել COS/M՝ ցանկացած մակարդակի քառակուսու վրա գտնվող կետեր պահանջելու համար: Առաջին տարբերակում ինչ-որ չափով ավելի հեշտ կլինի մաքրել տարածքի քառակուսի կտորները ցանկացած մակարդակում, բայց դա հազվադեպ է անհրաժեշտ:

Ստորին մակարդակի քառակուսիներից մեկի օրինակ.

Եվ ահա մի քանի գլոբալներ XAPI նախագծից՝ ինդեքսի ներկայացում գլոբալների վրա.

համաշխարհային ^ ճանապարհ օգտագործվում է կետերը պահելու համար polylines (ճանապարհներ, փոքր գետեր և այլն) և բազմանկյուններ (փակ տարածքներ. շենքեր, անտառներ և այլն):

Գլոբալների վրա նոսր զանգվածների օգտագործման կոպիտ դասակարգում:

1. Մենք պահպանում ենք որոշակի օբյեկտների կոորդինատները և դրանց վիճակները (քարտեզագրում, բջջային ավտոմատներ)
2. Մենք պահում ենք նոսր մատրիցներ:

2-րդ դեպքի համար հատուկ կոորդինատ պահանջելիս, որտեղ տարրին արժեք չի հատկացվում, մենք պետք է ստանանք լռելյայն նոսր զանգվածի տարրի արժեքը։

Բոնուսներ, որոնք մենք ստանում ենք գլոբալներում բազմաչափ մատրիցներ պահելիս

Արագ հեռացրեք և/կամ ընտրեք տարածքի կտորներ, որոնք բազմապատիկ են տողերի, հարթությունների, խորանարդների և այլնի: Այն դեպքերում, երբ օգտագործվում են ամբողջ թվերի ինդեքսները, կարող է օգտակար լինել տողերի, հարթությունների, խորանարդների և այլնի բազմապատիկ տարածության կտորները արագ հեռացնելու և/կամ բեռնելու հնարավորությունը:

թիմը Սպանել մենք կարող ենք ջնջել կամ մեկ տարր կամ տող, կամ նույնիսկ մի ամբողջ հարթություն: Գլոբալների հատկությունների շնորհիվ դա տեղի է ունենում շատ արագ՝ հազարավոր անգամ ավելի արագ, քան տարր առ տարր հեռացնելը:

Նկարը ցույց է տալիս եռաչափ զանգված գլոբալում ^a և տարբեր տեսակի ջնջումներ:

Հայտնի ինդեքսների միջոցով տարածության կտորներ ընտրելու համար կարող եք օգտագործել հրամանը Ընկղմել.

Ընտրելով մատրիցային սյունակ 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

Եզրակացություն.

Column(0)=1
Column(2)=1

Column փոփոխականի հետ կապված հետաքրքիրն այն է, որ մենք ունենք նաև նոսր զանգված, որը նույնպես պետք է հասանելի լինի $GET, քանի որ լռելյայն արժեքները դրանում չեն պահվում։

Տարածքի կտորներ ընտրելը կարող է կատարվել նաև փոքր ծրագրի միջոցով՝ օգտագործելով ֆունկցիան $Order. Սա հատկապես հարմար է այն տարածքների համար, որոնց ինդեքսները քվանտացված չեն (քարտեզագրություն):

Ամփոփում

Ներկա ժամանակները նոր հավակնոտ խնդիրներ են դնում։ Գրաֆիկները կարող են կազմված լինել միլիարդավոր գագաթներից, քարտեզները՝ միլիարդավոր կետերից, և ոմանք կարող են նույնիսկ ցանկանալ գործարկել իրենց սեփական տիեզերքը բջջային ավտոմատների վրա (1, 2).

Երբ նոսր զանգվածներից տվյալների ծավալն այլևս չի կարող տեղավորվել RAM-ի մեջ, բայց դուք պետք է աշխատեք դրանց հետ, ապա արժե դիտարկել գլոբալների և COS-ի վրա նմանատիպ նախագծեր իրականացնելու հնարավորությունը:

Շնորհակալություն ուշադրության համար! Սպասում ենք ձեր հարցերին և ցանկություններին մեկնաբանություններում։

Հրաժարում պատասխանատվությունից: Այս հոդվածը և դրա վերաբերյալ իմ մեկնաբանությունները իմ կարծիքն են և որևէ առնչություն չունեն InterSystems Corporation-ի պաշտոնական դիրքորոշման հետ:

Source: www.habr.com