សកលគឺជាដាវកំណប់សម្រាប់រក្សាទុកទិន្នន័យ។ អារេ តូច។ ផ្នែកទី 3

នៅក្នុងផ្នែកមុន (1, 2) យើង​បាន​និយាយ​អំពី​សកល​ជា​ដើមឈើ ក្នុង​មួយ​នេះ​យើង​នឹង​មើល​ទៅ​ពិភពលោក​ជា​អារេ​តូច។

Sparse Array គឺជាប្រភេទអារេដែលតម្លៃភាគច្រើនយកតម្លៃដូចគ្នា។

នៅក្នុងការអនុវត្ត អារេ sparse ច្រើនតែមានទំហំធំ ដែលមិនមានចំនុចណាមួយក្នុងការកាន់កាប់អង្គចងចាំជាមួយនឹងធាតុដូចគ្នាបេះបិទនោះទេ។ ដូច្នេះ វាសមហេតុផលក្នុងការអនុវត្តអារេ sparse តាមរបៀបដែលអង្គចងចាំមិនត្រូវបានខ្ជះខ្ជាយលើការរក្សាទុកតម្លៃដូចគ្នាបេះបិទ។
នៅក្នុងភាសាសរសេរកម្មវិធីមួយចំនួន អារេ sparse ត្រូវបានរួមបញ្ចូលនៅក្នុងភាសាខ្លួនវា ឧទាហរណ៍នៅក្នុង J, MATLAB. ភាសាសរសេរកម្មវិធីផ្សេងទៀតមានបណ្ណាល័យពិសេសដែលអនុញ្ញាតឱ្យអ្នកអនុវត្តពួកវា។ សម្រាប់ C++ - អេឡែន និងអ្នកដទៃ។

Globals គឺជាបេក្ខជនដ៏ល្អសម្រាប់អនុវត្ត sparse arrays ដោយសារតែ៖

1. ពួកវារក្សាទុកតម្លៃនៃថ្នាំងជាក់លាក់តែប៉ុណ្ណោះ ហើយមិនរក្សាទុកតម្លៃនៃអ្វីដែលមិនបានកំណត់;
2. ចំណុចប្រទាក់សម្រាប់ការចូលប្រើតម្លៃរបស់ថ្នាំងគឺស្រដៀងគ្នាខ្លាំងណាស់ទៅនឹងរបៀបដែលភាសាសរសេរកម្មវិធីជាច្រើនអនុវត្តការចូលប្រើធាតុអារេពហុវិមាត្រ។

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

3. សកលគឺជារចនាសម្ព័ន្ធកម្រិតទាបសមរម្យសម្រាប់ការរក្សាទុកទិន្នន័យ ដូច្នេះវាមានលក្ខណៈល្បឿនដ៏អស្ចារ្យ (ពីរាប់រយរាប់ពាន់ទៅរាប់សិបលានប្រតិបត្តិការក្នុងមួយវិនាទី អាស្រ័យលើផ្នែករឹង សូមមើលខាងក្រោម)។ 1)

ដោយសារសកលគឺជារចនាសម្ព័ន្ធជាប់លាប់ វាសមហេតុផលក្នុងការបង្កើត sparse arrays លើពួកវា នៅពេលដែលគេដឹងជាមុនថាចំនួន RAM នឹងមិនគ្រប់គ្រាន់ទេ។

លក្ខណៈសម្បត្តិមួយនៃការអនុវត្តអារេ sparse គឺដើម្បីត្រឡប់តម្លៃលំនាំដើមមួយចំនួន ប្រសិនបើការចូលប្រើត្រូវបានធ្វើឡើងទៅកាន់ក្រឡាដែលមិនបានកំណត់។

នេះអាចត្រូវបានអនុវត្តដោយប្រើមុខងារ $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)

តារាងផ្លាស់ប្តូរម៉ាស៊ីនរដ្ឋ

ដោយសារក្រាហ្វការផ្លាស់ប្តូរនៃ automaton កំណត់គឺជាក្រាហ្វធម្មតា នោះតារាងផ្លាស់ប្តូរនៃ automaton កំណត់គឺជាម៉ាទ្រីសជាប់ដូចគ្នាដែលបានពិភាក្សាខាងលើ។

ស្វ័យប្រវត្តិកម្មកោសិកា

ស្វ័យប្រវត្តិកម្មកោសិកាដ៏ល្បីល្បាញបំផុតគឺ ហ្គេម "ជីវិត"ដែល​ដោយ​សារ​តែ​ច្បាប់​របស់​វា (ពេល​ក្រឡា​មួយ​មាន​អ្នក​ជិត​ខាង​ច្រើន វា​ងាប់) គឺ​ជា​អារេ​តូច។

Stephen Wolfram ជឿថា កោសិកាស្វ័យប្រវត្តិគឺ វិស័យវិទ្យាសាស្ត្រថ្មី។. ក្នុងឆ្នាំ 2002 គាត់បានបោះពុម្ភសៀវភៅ 1280 ទំព័រ ដែលជាប្រភេទវិទ្យាសាស្ត្រថ្មី ដែលគាត់បានប្រកែកយ៉ាងទូលំទូលាយថា ភាពជឿនលឿននៃកោសិកា automata មិននៅដាច់ពីគេទេ ប៉ុន្តែមានភាពស្ថិតស្ថេរ និងមានឥទ្ធិពលខ្លាំងសម្រាប់គ្រប់ផ្នែកនៃវិទ្យាសាស្ត្រ។

វាត្រូវបានបញ្ជាក់ថា រាល់ក្បួនដោះស្រាយដែលអាចប្រតិបត្តិបាននៅលើកុំព្យូទ័រអាចត្រូវបានអនុវត្តដោយប្រើ cellular automaton ។ Cellular automata ត្រូវបានប្រើដើម្បីធ្វើគំរូបរិស្ថាន និងប្រព័ន្ធថាមវន្ត ដើម្បីដោះស្រាយបញ្ហាក្បួនដោះស្រាយ និងសម្រាប់គោលបំណងផ្សេងទៀត។

ប្រសិនបើយើងមានវាលដ៏ធំមួយ ហើយយើងត្រូវកត់ត្រាស្ថានភាពមធ្យមទាំងអស់នៃ automaton កោសិកា នោះវាសមហេតុផលក្នុងការប្រើសកល។

គំនូសតាង

រឿងដំបូងដែលចូលមកក្នុងគំនិតរបស់ខ្ញុំនៅពេលនិយាយអំពីការប្រើ sparse arrays គឺការគូសផែនទីភារកិច្ច។

តាមក្បួនវាមានកន្លែងទំនេរច្រើននៅលើផែនទី។ ប្រសិនបើផែនទីត្រូវបានតំណាងជាភីកសែលធំ នោះ 71% នៃភីកសែលរបស់ផែនដីនឹងត្រូវបានកាន់កាប់ដោយមហាសមុទ្រ។ អារេខ្ទាស់។ ហើយ​ប្រសិន​បើ​អ្នក​អនុវត្ត​តែ​ដៃ​មនុស្ស នោះ​ចន្លោះ​ទទេ​នឹង​មាន​ច្រើន​ជាង ៩៥%។

ជាការពិតណាស់ គ្មាននរណាម្នាក់រក្សាទុកផែនទីក្នុងទម្រង់ជា raster arrays ទេ តំណាងវ៉ិចទ័រត្រូវបានប្រើ។
ប៉ុន្តែតើផែនទីវ៉ិចទ័រជាអ្វី? នេះគឺជាប្រភេទនៃស៊ុម និងពហុកោណ និងពហុកោណដែលមានចំណុច។
ជាមូលដ្ឋានទិន្នន័យនៃចំណុច និងការតភ្ជាប់រវាងពួកគេ។

បេសកកម្មគូសផែនទីដ៏មានមហិច្ឆតាបំផុតមួយ គឺបេសកកម្មកែវយឺត Gaia ដើម្បីគូសផែនទីកាឡាក់ស៊ីរបស់យើង។ និយាយតាមន័យធៀប កាឡាក់ស៊ីរបស់យើង ដូចជាចក្រវាឡទាំងមូល គឺជាអារេ sparse បន្ត៖ ចន្លោះដ៏ធំនៃភាពទទេ ដែលក្នុងនោះមានចំនុចតូចៗដ៏កម្រ - ផ្កាយ។ ចន្លោះទទេគឺ 99,999999…….%. ដើម្បីរក្សាទុកផែនទីនៃកាឡាក់ស៊ីរបស់យើង មូលដ្ឋានទិន្នន័យសកលត្រូវបានជ្រើសរើស - ឃ្លាំងសម្ងាត់។

ខ្ញុំមិនដឹងរចនាសម្ព័ន្ធពិតប្រាកដនៃសកលលោកនៅក្នុងគម្រោងនេះទេ ខ្ញុំអាចសន្មត់ថាវាមានលក្ខណៈស្រដៀងនឹង៖

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

ថ្មីៗនេះ hackathon ឃ្លាំងសម្ងាត់ សន្ទស្សន៍ភូមិសាស្ត្រត្រូវបានអនុវត្ត ភូមិសាស្ត្រ. យើងកំពុងរង់ចាំអត្ថបទពីអ្នកនិពន្ធដែលមានព័ត៌មានលម្អិតអំពីការអនុវត្ត។

ការអនុវត្តលិបិក្រមទំហំនៅលើសកលលោកនៅក្នុង 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៖ តំណាងនៃសន្ទស្សន៍លើសកលលោក៖

សកល ^ ផ្លូវ ប្រើដើម្បីរក្សាទុកពិន្ទុ ប៉ូលីលីន (ផ្លូវ ទន្លេតូច ។ល។) និងពហុកោណ (តំបន់បិទជិត : អគារ ព្រៃឈើ ។ល។

ការចាត់ថ្នាក់រដុបនៃការប្រើប្រាស់ sparse arrays នៅលើសកលលោក។

1. យើងរក្សាទុកកូអរដោណេនៃវត្ថុជាក់លាក់ និងស្ថានភាពរបស់វា (ការធ្វើផែនទី ស្វ័យប្រវត្តិកម្មកោសិកា)
2. យើងរក្សាទុកម៉ាទ្រីសតូច។

សម្រាប់ករណីទី 2) នៅពេលស្នើសុំកូអរដោនេជាក់លាក់មួយ ដែលធាតុមិនត្រូវបានផ្តល់តម្លៃ យើងត្រូវទទួលបានតម្លៃនៃធាតុអារេ sparse លំនាំដើម។

ប្រាក់រង្វាន់ដែលយើងទទួលបាននៅពេលរក្សាទុកម៉ាទ្រីសពហុវិមាត្រជាសកល

យកចេញយ៉ាងឆាប់រហ័ស និង/ឬជ្រើសរើសបំណែកនៃចន្លោះដែលមានច្រើនជួរ យន្តហោះ គូប។ល។ សម្រាប់ករណីដែលលិបិក្រមចំនួនគត់ត្រូវបានប្រើប្រាស់ សមត្ថភាពក្នុងការយកចេញយ៉ាងឆាប់រហ័ស និង/ឬទៅយកបំណែកនៃចន្លោះដែលមានពហុជួរ យន្តហោះ គូប។ល។ អាចមានប្រយោជន៍។

ក្រុម សម្លាប់ យើងអាចលុបធាតុតែមួយ ឬមួយជួរ ឬសូម្បីតែយន្តហោះទាំងមូល។ សូមអរគុណចំពោះលក្ខណៈសម្បត្តិរបស់សកល វាកើតឡើងយ៉ាងឆាប់រហ័ស - រាប់ពាន់ដងលឿនជាងការដកចេញពីធាតុដោយធាតុ។

តួលេខនេះបង្ហាញពីអារេបីវិមាត្រជាសកល ^a និងប្រភេទផ្សេងគ្នានៃការលុប។

ដើម្បីជ្រើសរើសបំណែកនៃទំហំដោយប្រើលិបិក្រមដែលគេស្គាល់ អ្នកអាចប្រើពាក្យបញ្ជា បញ្ចូលចូលគ្នា.

ការជ្រើសរើសជួរឈរម៉ាទ្រីសទៅក្នុងអថេរជួរឈរ៖

; Зададим трёхмерный разреженный массив 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

អ្វី​ដែល​គួរ​ឱ្យ​ចាប់​អារម្មណ៍​អំពី​អថេរ​ជួរ​ឈរ​គឺ​ថា យើង​ក៏​មាន​អារេ​ខ្វែង​ដែរ ដែល​ត្រូវ​តែ​ចូល​ដំណើរការ​តាម​រយៈ $GETចាប់តាំងពីតម្លៃលំនាំដើមមិនត្រូវបានរក្សាទុកនៅក្នុងវា។

ការជ្រើសរើសបំណែកនៃទំហំក៏អាចធ្វើបានតាមរយៈកម្មវិធីតូចមួយដោយប្រើមុខងារ $ បញ្ជាទិញ. នេះងាយស្រួលជាពិសេសនៅលើចន្លោះដែលសន្ទស្សន៍មិនត្រូវបានគណនាជាបរិមាណ (គំនូសតាង) ។

សេចក្តីសន្និដ្ឋាន

សម័យកាលបច្ចុប្បន្នបង្កើតនូវការងារដែលមានមហិច្ឆតាថ្មី។ ក្រាហ្វអាចបង្កើតបានរាប់ពាន់លាននៃចំនុចកំពូល ផែនទីដែលបង្កើតបានរាប់ពាន់លានចំណុច ហើយអ្នកខ្លះប្រហែលជាចង់ដំណើរការសកលលោកផ្ទាល់របស់ពួកគេនៅលើ automata កោសិកា (1, 2).

នៅពេលដែលបរិមាណនៃទិន្នន័យពីអារេតូចមិនអាចសមនឹង RAM ទៀតទេ ប៉ុន្តែអ្នកត្រូវធ្វើការជាមួយពួកវា នោះវាមានតម្លៃពិចារណាពីលទ្ធភាពនៃការអនុវត្តគម្រោងស្រដៀងគ្នានៅលើសកលលោក និង COS ។

សូម​អរគុណ​ចំពោះ​ការ​យកចិត្ត​ទុកដាក់​របស់​លោកអ្នក! យើងកំពុងរង់ចាំសំណួរ និងបំណងប្រាថ្នារបស់អ្នកនៅក្នុងមតិយោបល់។

ការមិនទទួលខុសត្រូវ: អត្ថបទនេះ និងយោបល់របស់ខ្ញុំចំពោះវាជាគំនិតរបស់ខ្ញុំ ហើយមិនមានទំនាក់ទំនងជាមួយនឹងមុខតំណែងផ្លូវការរបស់ InterSystems Corporation ទេ។

ប្រភព: www.habr.com