Алдыңғы бөлімдерде (, ) біз жаһандықтарды ағаштар ретінде айттық, бұл жерде біз жаһандықтарды сирек массивтер ретінде қарастырамыз.
мәндердің көпшілігі бірдей мәнді қабылдайтын массив түрі болып табылады.
Іс жүзінде сирек массивтер жиі соншалықты үлкен, сондықтан жадты бірдей элементтермен толтырудың қажеті жоқ. Сондықтан, жад бірдей мәндерді сақтауға жұмсалмайтындай етіп сирек массивтерді енгізу мағынасы бар.
Кейбір бағдарламалау тілдерінде сирек массивтер тілдің өзіне кіреді, , . Басқа бағдарламалау тілдерінде оларды жүзеге асыруға мүмкіндік беретін арнайы кітапханалар бар. C++ үшін - және басқалар.
Ғаламшарлар сирек массивтерді енгізу үшін жақсы үміткерлер болып табылады, себебі:
- Олар тек белгілі бір түйіндердің мәндерін сақтайды және анықталмағандардың мәндерін сақтамайды;
- Түйіннің мәніне қол жеткізу интерфейсі көп өлшемді массив элементіне қол жеткізуді қанша бағдарламалау тілдері жүзеге асыратынына өте ұқсас.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Ғаламдық - бұл деректерді сақтауға арналған өте төмен деңгейлі құрылым, сондықтан оның керемет жылдамдық сипаттамалары бар (аппараттық құралға байланысты секундына жүздеген мыңнан ондаған миллион транзакцияларға дейін, төменде қараңыз). )
Жаһандық тұрақты құрылым болғандықтан, жедел жадының көлемі жеткіліксіз болатыны алдын ала белгілі болған кезде оларда сирек массивтер жасау мағынасы бар.
Сирек жиымды іске асыру қасиеттерінің бірі анықталмаған ұяшыққа қатынас жасалған болса, кейбір әдепкі мәнді қайтару болып табылады.
Бұл функцияның көмегімен жүзеге асырылуы мүмкін 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 * көбейтіндісі ретінде алынады ), яғни мұндай матрицаларды сақтаудың одан да үнемді тәсілі биттік жолдар болып табылады, өйткені олардың орындалуы үлкен бос орындарды ерекше түрде оңтайландырады.
Биттік жолдармен манипуляциялар функция арқылы орындалады .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Мемлекеттік машинаның ауысу кестесі
Ақырлы автоматтың ауысу графигі кәдімгі график болғандықтан, ақырлы автоматтың ауысу кестесі жоғарыда қарастырылған көршілестік матрицасы болып табылады.
Ұялы автоматтар
Ең танымал ұялы автомат болып табылады , ол өз ережелеріне байланысты (ұяшықта көршілері көп болса, ол өледі) сирек массив болып табылады.
Стивен Вольфрам ұялы автоматтар деп санайды . 2002 жылы ол 1280 беттік «Ғылымның жаңа түрі» кітабын басып шығарды, онда ол ұялы автоматтардағы жетістіктер оқшауланбағанын, бірақ тұрақты және ғылымның барлық салаларына үлкен әсер ететінін кеңінен дәлелдейді.
Компьютерде орындалатын кез келген алгоритмді ұялы автомат арқылы жүзеге асыруға болатыны дәлелденді. Ұялы автоматтар динамикалық орталар мен жүйелерді модельдеу, алгоритмдік есептерді шешу үшін және басқа мақсаттарда қолданылады.
Егер бізде үлкен өріс болса және біз ұялы автоматтың барлық аралық күйлерін жазуымыз керек болса, онда глобальді пайдалану мағынасы бар.
Картография
Сирек массивтерді пайдалану туралы сөз болғанда менің ойыма бірінші келетін нәрсе - карталарды құру.
Әдетте, карталарда бос орындар көп. Егер карта үлкен пикселдер түрінде ұсынылса, онда Жер пикселдерінің 71% мұхит алады. Сирек массив. Ал егер сіз тек адам қолының туындыларын қолдансаңыз, онда бос кеңістік 95% -дан астам болады.
Әрине, растрлық массивтер түрінде карталарды ешкім сақтамайды, векторлық бейнелеу қолданылады;
Бірақ векторлық карталар дегеніміз не? Бұл нүктелерден тұратын жақтаудың және полисызықтар мен көпбұрыштардың бір түрі.
Негізінде нүктелер мен олардың арасындағы байланыстардың мәліметтер базасы.
Ең өршіл картографиялық миссиялардың бірі - біздің галактиканы картаға түсіретін Гаиа телескопының миссиясы. Бейнелеп айтқанда, біздің галактика, бүкіл ғалам сияқты, үздіксіз сирек массив: сирек кездесетін кішкентай нүктелер - жұлдыздар бар үлкен бос кеңістіктер. Бос орын 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 шанышқысы - .
Жақында геокеңістіктік индекстер енгізілді . Біз авторлардан іске асыру мәліметтері бар мақаланы күтеміз.
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 жобасынан бірнеше жаһандық: жаһандық индексті ұсыну:
жаһандық ^ жол нүктелерді сақтау үшін қолданылады (жолдар, шағын өзендер және т.б.) және көпбұрыштар (жабық аумақтар: ғимараттар, ормандар және т.б.).
Глобалдарда сирек массивтерді қолданудың өрескел жіктелуі.
- Біз белгілі бір объектілердің координаттарын және олардың күйлерін сақтаймыз (карталау, ұялы автоматтар)
- Біз сирек матрицаларды сақтаймыз.
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 айнымалысының қызықты жері бізде сирек массив бар, оған да кіруге болады , өйткені әдепкі мәндер онда сақталмайды.
Кеңістік бөліктерін таңдауды функцияны пайдаланып шағын бағдарлама арқылы да жасауға болады . Бұл әсіресе индекстері квантталмаған кеңістіктерде (картография) ыңғайлы.
қорытынды
Қазіргі уақыт жаңа өршіл міндеттер қойып отыр. Графиктер миллиардтаған шыңдардан, карталар миллиардтаған нүктелерден тұруы мүмкін, ал кейбіреулері тіпті ұялы автоматтарда өз ғаламдарын басқарғысы келуі мүмкін (, ).
Сирек массивтердегі деректер көлемі бұдан былай ЖЖҚ-ға сыймай қалса, бірақ олармен жұмыс істеу керек болса, онда ғаламдық және COS бойынша ұқсас жобаларды жүзеге асыру мүмкіндігін қарастырған жөн.
Назарларыңызға рахмет! Түсініктемелерде сұрақтарыңыз бен тілектеріңізді күтеміз.
Жауапкершіліктен бас тарту: Бұл мақала және оған менің пікірлерім менің пікірім және InterSystems корпорациясының ресми ұстанымына қатысы жоқ.
Ақпарат көзі: www.habr.com