გლობალები არის საგანძური ხმლები მონაცემების შესანახად. მწირი მასივები. ნაწილი 3

წინა ნაწილებში (1, 2) ჩვენ ვისაუბრეთ გლობალებზე, როგორც ხეებზე, ამ ერთში ჩვენ შევხედავთ გლობალურებს, როგორც მწირ მასივებს.

იშვიათი მასივი არის მასივის ტიპი, რომელშიც მნიშვნელობების უმეტესობა ერთსა და იმავე მნიშვნელობას იღებს.

პრაქტიკაში, მწირი მასივები ხშირად იმდენად დიდია, რომ აზრი არ აქვს მეხსიერების იდენტური ელემენტებით დაკავებას. ამიტომ, აზრი აქვს მწირი მასივების დანერგვას ისე, რომ მეხსიერება არ დაიხარჯოს იდენტური მნიშვნელობების შესანახად.
ზოგიერთ პროგრამირების ენაში, მწირი მასივები შედის თავად ენაში, მაგალითად ჯ, MATLAB. სხვა პროგრამირების ენებს აქვთ სპეციალური ბიბლიოთეკები, რომლებიც საშუალებას გაძლევთ განახორციელოთ ისინი. C++-ისთვის - ეგენი ა.შ.

გლობალები კარგი კანდიდატები არიან მწირი მასივების დასანერგად, რადგან:

1. ისინი ინახავს მხოლოდ გარკვეული კვანძების მნიშვნელობებს და არ ინახავს განუსაზღვრელ მნიშვნელობებს;
2. კვანძის მნიშვნელობის წვდომის ინტერფეისი ძალიან ჰგავს იმ პროგრამირების ენას, რომელიც ახორციელებს წვდომას მრავალგანზომილებიან მასივის ელემენტზე.

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

3. Global არის საკმაოდ დაბალი დონის სტრუქტურა მონაცემთა შესანახად, ამიტომ მას აქვს სიჩქარის გამორჩეული მახასიათებლები (ასობით ათასიდან ათეულ მილიონამდე ტრანზაქცია წამში, ტექნიკის მიხედვით, იხილეთ ქვემოთ). 1)

ვინაიდან გლობალური მუდმივი სტრუქტურაა, აზრი აქვს მათზე მწირი მასივების შექმნას, როდესაც წინასწარ არის ცნობილი, რომ RAM-ის რაოდენობა საკმარისი არ იქნება.

იშვიათი მასივის განხორციელების ერთ-ერთი თვისებაა გარკვეული ნაგულისხმევი მნიშვნელობის დაბრუნება, თუ წვდომა განხორციელდება განუსაზღვრელ უჯრედზე.

ეს შეიძლება განხორციელდეს ფუნქციის გამოყენებით $GET COS-ში. ეს მაგალითი განიხილავს 3-განზომილებიან მასივს.

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%-ზე მეტი.

რა თქმა უნდა, არავინ ინახავს რუქებს რასტრული მასივების სახით; გამოიყენება ვექტორული წარმოდგენა.
მაგრამ რა არის ვექტორული რუქები? ეს არის ერთგვარი ჩარჩო და პოლიხაზები და პოლიგონები, რომლებიც შედგება წერტილებისგან.
არსებითად პუნქტებისა და მათ შორის კავშირების მონაცემთა ბაზა.

რუკების ერთ-ერთი ყველაზე ამბიციური მისიაა გაიას ტელესკოპის მისია ჩვენი გალაქტიკის რუკაზე. ფიგურალურად რომ ვთქვათ, ჩვენი გალაქტიკა, ისევე როგორც მთელი სამყარო, არის უწყვეტი მწირი მასივი: სიცარიელის უზარმაზარი სივრცეები, რომლებშიც იშვიათია პატარა წერტილები - ვარსკვლავები. ცარიელი ადგილია 99,999999…….%. ჩვენი გალაქტიკის რუკის შესანახად არჩეული იქნა გლობალური მონაცემთა ბაზა - Cache.

მე არ ვიცი გლობალების ზუსტი სტრუქტურა ამ პროექტში, შემიძლია ვივარაუდო, რომ ეს არის რაღაც მსგავსი:

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 გალაქტიკური კოორდინატები გრძედი, განედი და მანძილი მზემდე.

გლობალების მოქნილი სტრუქტურა საშუალებას გაძლევთ შეინახოთ ვარსკვლავებისა და პლანეტების ნებისმიერი საჭირო მახასიათებელი, რადგან გლობალებზე საფუძვლები სქემების გარეშეა.

ჩვენი სამყაროს რუქის შესანახად, Cache შეირჩა არა მხოლოდ მისი მოქნილობისთვის, არამედ მონაცემთა ნაკადის ძალიან სწრაფად შესანახად და ამავე დროს სწრაფი ძიების ინდექსების გლობალური შექმნისთვის.

თუ დედამიწას დავუბრუნდებით, მაშინ გლობალებზე შეიქმნა კარტოგრაფიული პროექტები OpenStreetMap XAPI და OpenStreetMap-ის ჩანგალი - FOOM.

ცოტა ხნის წინ ჰაკათონი ქეში განხორციელდა გეოსივრცითი ინდექსები Geospatial. ველოდებით სტატიას ავტორებისგან განხორციელების დეტალებით.

სივრცითი ინდექსების დანერგვა გლობალზე OpenStreetMap XAPI-ში

სურათები გადაღებულია ამ პრეზენტაციას.

მთელი გლობუსი იყოფა კვადრატებად, შემდეგ ქვეკვადრატებად და ქვეკვადრატებად ქვეკვადრატებად და ა.შ. ზოგადად, ჩვენ ვიღებთ იერარქიულ სტრუქტურას, რომლის შესანახადაც იქმნება გლობალები.

ნებისმიერ მომენტში, ჩვენ შეგვიძლია თითქმის მყისიერად მოვითხოვოთ სასურველი კვადრატი ან გავასუფთავოთ იგი, ასევე ყველა ქვეკვადრატი დაბრუნდება ან გასუფთავდება.

მსგავსი სქემა გლობალებზე შეიძლება განხორციელდეს რამდენიმე გზით.

ვარიანტი 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ВторойТочки
...

ვარიანტი 2:

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

ორივე შემთხვევაში ძნელი არ არის COS/M გამოყენება ნებისმიერი დონის კვადრატში მდებარე ქულების მოსათხოვად. პირველ ვარიანტში რამდენადმე ადვილი იქნება სივრცის კვადრატული ნაწილების გაწმენდა ნებისმიერ დონეზე, მაგრამ ეს იშვიათად არის საჭირო.

ერთ-ერთი ქვედა დონის კვადრატის მაგალითი:

და აქ არის რამდენიმე გლობალი XAPI პროექტიდან: ინდექსის წარმოდგენა გლობალებზე:

გლობალური ^ გზა გამოიყენება ქულების შესანახად პოლიხაზები (გზები, პატარა მდინარეები და ა.შ.) და პოლიგონები (დახურული ადგილები: შენობები, ტყეები და ა.შ.).

გლობალებზე იშვიათი მასივების გამოყენების უხეში კლასიფიკაცია.

1. ჩვენ ვინახავთ გარკვეული ობიექტების კოორდინატებს და მათ მდგომარეობას (რუკა, ფიჭური ავტომატები)
2. ჩვენ ვინახავთ მწირ მატრიცებს.

შემთხვევისთვის 2) კონკრეტული კოორდინატის მოთხოვნისას, სადაც ელემენტს მნიშვნელობა არ აქვს მინიჭებული, უნდა მივიღოთ ნაგულისხმევი იშვიათი მასივის ელემენტის მნიშვნელობა.

ბონუსები, რომლებსაც ვიღებთ მრავალგანზომილებიანი მატრიცების გლობალებში შენახვისას

სწრაფად ამოიღეთ და/ან შეარჩიეთ სივრცის ნაჭრები, რომლებიც მრავლადაა რიგები, სიბრტყეები, კუბები და ა.შ. იმ შემთხვევებისთვის, როდესაც გამოიყენება მთელი რიცხვების ინდექსები, შეიძლება სასარგებლო იყოს სივრცის ნაწილების სწრაფად ამოღების ან/და მოზიდვის შესაძლებლობა, რომლებიც მრავლადაა რიგები, სიბრტყეები, კუბები და ა.შ.

გუნდი Kill ჩვენ შეგვიძლია წავშალოთ ერთი ელემენტი ან მწკრივი, ან თუნდაც მთელი სიბრტყე. გლობალების თვისებების წყალობით, ეს ხდება ძალიან სწრაფად - ათასობით ჯერ უფრო სწრაფად, ვიდრე ელემენტი ელემენტის ამოღება.

ფიგურაში ნაჩვენებია სამგანზომილებიანი მასივი გლობალურში ^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-ის ოფიციალურ პოზიციასთან.

წყარო: www.habr.com