Di beşên berê de (, ) me behsa globalan wek daran kir, di vê yekê de em ê gerdûnan wekî rêzikên kêm binerin.
celebek rêzik e ku tê de piraniya nirxan heman nirxê digirin.
Di pratîkê de, rêzikên hûrgelî bi gelemperî ew qas mezin in ku ti wateya dagirkirina bîranînê bi hêmanên wekhev re tune. Ji ber vê yekê, maqûl e ku meriv rêzikên sparse bi vî rengî bicîh bîne ku bîranîn li ser hilanîna nirxên wekhev winda nebe.
Di hin zimanên bernamesaziyê de, rêzikên sparse di nav zimanê xwe de hene, , . Zimanên din ên bernamekirinê pirtûkxaneyên taybetî hene ku destûrê didin we ku hûn wan bicîh bikin. Ji bo C++ - û din
Gerdûnî berendamên baş in ji bo bicihanîna rêzikên kêm ji ber ku:
- Ew nirxên tenê hin girêkan hilînin û nirxên nenas hilnagirin;
- Navbera gihîştina nirxa girêkek pir dişibihe çend zimanên bernamesaziyê ku gihîştina hêmanek rêzek piralî pêk tînin.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global ji bo hilanîna daneyan avahiyek pir kêm-asta ye, ji ber vê yekê ew xwedan taybetmendiyên leza berbiçav e (ji sed hezaran heya bi deh mîlyon danûstendinan di çirkeyê de, li gorî hardware ve girêdayî ye, li jêr binêre). )
Ji ber ku gerdûnî avahiyek domdar e, maqûl e ku meriv li ser wan rêzikên hûrgelî biafirîne gava ku ji pêş de tê zanîn ku mîqdara RAM dê têrê neke.
Yek ji taybetmendiyên pêkanînên rêzikên sparse ev e ku heke gihîştinek ji şaneyek nediyar re were çêkirin hin nirxek xwerû vedigerîne.
Ev dikare bi karanîna fonksiyonê were bicîh kirin li COS. Ev mînak rêzek 3-alî dihesibîne.
SET a = $GET(^a(x,y,z), defValue)Kîjan peywir hewceyê rêzikên hûrgelî ne û gerdûn çawa dikarin alîkariyê bikin?
Matrixa cîrantiyê (girêdayî).
ji bo temsîlkirina grafikan tê bikaranîn:
Eşkere ye, her ku grafiyek mezin be, dê di matrixê de zero jî hebin. Ger, bo nimûne, em grafikek tora civakî bigirin û wê di forma matrixek wekhev de pêşkêş bikin, wê hingê ew ê hema hema bi tevahî ji sifiran pêk were, yanî. dê bibe array sparse.
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
....
Di vê nimûneyê de, em gerdûnî xilas dikin ^m matrixa pêwendiyê, û her weha hejmara keviyên li her girêkekê (kî bi kê re heval e û hejmara hevalan).
Ger hejmara hêmanên di grafîkê de ji 29 mîlyonî zêdetir nebe (ev hejmar wekî hilberîna 8 * tê girtin. ), ango rêyek hê aborîtir ji bo hilanîna matricên weha rêzikên bit e, ji ber ku pêkanîna wan bi rengek taybetî valahiyên mezin xweş dike.
Manîpulasyonên bi rêzikên bit ji hêla fonksiyonê ve têne kirin .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabloya veguherîna makîneya dewletê
Ji ber ku grafiya veguhêz a otomatek bêdawî grafiyek asayî ye, wê hingê tabloya veguheztinê ya otomatê ya dawî heman matrixa cîrantiyê ye ku li jor hatî nîqaş kirin.
otomatên hucreyî
Herî navdar otomatê de cellular e , ku, ji ber qaîdeyên xwe (dema ku şaneyek gelek cîranên wê hebin, ew dimire) rêzek kêm e.
Stephen Wolfram bawer dike ku otomatên hucreyî ne . Di 2002 de, wî pirtûkek 1280-rûpelî weşand, Cûreyek Zanistî ya Nû, ku tê de ew bi berfirehî amaje dike ku pêşkeftinên di otomatên hucreyî de ne veqetandî ne, lê domdar in û bandorên mezin li ser hemî warên zanistî hene.
Hatiye îsbat kirin ku her algorîtmayek ku li ser komputerê tête bicîh kirin dikare bi karanîna otomatek hucreyî were bicîh kirin. Otomatên hucreyî ji bo modela jîngeh û pergalên dînamîkî, ji bo çareserkirina pirsgirêkên algorîtmîkî û ji bo armancên din têne bikar anîn.
Ger zeviyek me ya mezin hebe û pêdivî ye ku em hemî dewletên navîn ên otomatek hucreyî tomar bikin, wê hingê maqûl e ku meriv gerdûnan bikar bîne.
Cartography
Yekem tiştê ku tê hişê min dema ku ew tê ser karanîna rêzikên sparse peywirên nexşeyê ye.
Wekî qaîdeyek, li ser nexşeyan gelek cîhê vala heye. Ger nexşe wek pixelên mezin bê nîşandan, wê demê 71% ji pîxelên Cîhanê dê ji hêla okyanûsê ve were dagir kirin. Array sparse. Û heke hûn tenê karên destên mirovan bicîh bînin, wê hingê cîhê vala dê ji 95% zêdetir be.
Bê guman, kes nexşeyan di forma rêzikên raster de hilîne, nûneriya vektorê tê bikar anîn.
Lê nexşeyên vektor çi ne? Ev celebek çarçove û pirhêl û pirgoşeyan e ku ji xalan pêk tê.
Bi bingehîn databasek xal û girêdanên di navbera wan de.
Yek ji mîsyonên nexşeyê yên herî ambicioz mîsyona Teleskopa Gaia ye ku nexşeya galaksiya me dike. Bi awayekî fîgurî, galaksiya me, mîna tevahiya gerdûnê, rêzek hûrgelek domdar e: cihên vala yên mezin ên ku tê de xalên piçûk ên kêm - stêrk hene. Cihê vala 99,999999…….. Ji bo hilanîna nexşeya galaksiya me, databasek gerdûnî hate hilbijartin - Caché.
Ez di vê projeyê de avahiya tam a gerdûnan nizanim, ez dikarim texmîn bikim ku ew tiştek dişibihe:
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 li ku ne û dûrî Rojê.
Struktura maqûl a gerdûnan dihêle hûn taybetmendiyên stêrk û gerstêrkan ên pêwîst hilînin, ji ber ku bingehên li ser gerdûnan bê plan in.
Ji bo hilanîna nexşeya gerdûna me, Caché ne tenê ji ber nermbûna wê, lê di heman demê de ji ber şiyana wê ya hilanîna herikîna daneyan pir zû hate hilbijartin, di heman demê de ji bo lêgerînên bilez gerdûnên indexê diafirîne.
Ger em vegerin Erdê, wê hingê projeyên kartografî li ser gerdûnan hatin afirandin û pişkek OpenStreetMap - .
Demên dawî de li ser endeksên erdnîgarî hatin bicihanîn . Em li benda gotarek ji nivîskarên bi hûrguliyên pêkanînê ne.
Di OpenStreetMap XAPI-ê de bicîhkirina navnîşên cîhê li ser gerdûnî
Wêneyên ku ji .
Tevahiya dinya bi çargoşeyan, dû re li jêr çargoşeyan, û li jêr çargoşeyan li jêr çargoşeyan û hwd. Bi gelemperî, em ji bo hilanîna ku gerdûnî têne afirandin avahiyek hiyerarşîk digirin.
Di her kêliyê de, em dikarin hema tavilê daxwaza çargoşeya xwestinê bikin an wê paqij bikin, û hemî jêr-çargoşe jî dê werin vegerandin an paqij kirin.
Planek weha li ser gerdûnan dikare bi çend awayan were bicîh kirin.
1 Hilbijêre:
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 Hilbijêre:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Di her du rewşan de, ne dijwar e ku meriv COS/M bikar bîne da ku xalên ku li çarçoveyek her astê cih digirin daxwaz bikin. Paqijkirina perçeyên çargoşe yên cîhê di her astê de di vebijarka yekem de dê hinekî hêsantir be, lê ev kêm kêm hewce ye.
Mînakek yek ji çargoşeyên asta jêrîn:
Û li vir çend gerdûnên ji projeya XAPI hene: Nûnertiya nîşanek li ser gerdûnan:
cîhane ^ rê ji bo depokirina xalan tê bikaranîn (rê, çemên piçûk, hwd.) û polîgon (herêmên girtî: avahî, daristan, hwd.).
Tesnîfkirina hişk a karanîna rêzikên kêm li ser gerdûnan.
- Em koordînatên hin tiştan û rewşên wan diparêzin (nexşe, otomatên hucreyî)
- Em matrîsên sparse hilînin.
Ji bo doza 2) dema ku daxwaza koordînatek taybetî ya ku hêmanek nirxek jê re nayê veqetandin, divê em nirxa hêmana rêza sparse ya xwerû bistînin.
Bonusên ku em distînin dema ku matricên piralî di gerdûnan de hilînin
Bi lez û bez perçeyên cîhê ku pirjimar rêz, balafir, kub, hwd ne hildibijêrin û/an hilbijêrin. Ji bo rewşên ku îndeksên yekjimar têne bikar anîn, dibe ku şiyana zû rakirin û/an girtina perçeyên cîhê ku pirjimar rêz in, balafir, kubar û hwd.
kom em dikarin an hêmanek yek an rêzek, an jî balafirek tevahî jêbirin. Bi xêra taybetmendiyên gerdûnan, ev pir zû diqewime - bi hezaran carî ji rakirina hêman-bi-hêman zûtir dibe.
Di jimare de rêzek sê-alî ya gerdûnî nîşan dide ^a û cûreyên jêbirinê.
Ji bo ku hûn perçeyên cîhê bi karanîna navnîşên naskirî hilbijêrin, hûn dikarin fermanê bikar bînin .
Hilbijartina stûnek matrixê di guhêrbara Stûnê de:
; Зададим трёхмерный разреженный массив 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
Encam:
Column(0)=1
Column(2)=1
Tiştê ku di derbarê guhêrbara Stûnê de balkêş e ev e ku di heman demê de me arrayek kêm jî heye, ku pêdivî ye ku ew jî bi riya , ji ber ku nirxên xwerû tê de nayên hilanîn.
Hilbijartina perçeyên cîhê jî dikare bi bernameyek piçûk bi karanîna fonksiyonê were kirin . Ev bi taybetî li cîhên ku îndeksên wan quantîzekirî ne (kartografî) rehet e.
encamê
Demên heyî karên nû yên ambargoyê derdixe pêş. Grafîk dikarin ji mîlyaran vertîkan, nexşeyên ku ji mîlyaran xalan pêk tên, û hin kes jî dikarin bixwazin gerdûna xwe li ser otomatên şaneyê bimeşînin (, ).
Gava ku qebareya daneya ji rêzikên zirav nema dikare di RAM-ê de biqewime, lê hûn hewce ne ku bi wan re bixebitin, wê hingê hêja ye ku meriv li ser îhtîmala pêkanîna projeyên mîna li ser gerdûnî û COS-ê bifikirin.
Spas ji bo baldariya we! Em li benda pirs û daxwazên we di şîroveyan de ne.
Disclaimer: Ev gotar û şîroveyên min ên li ser wê nerîna min e û ti têkiliya wê bi helwesta fermî ya InterSystems Corporation re tune.
Source: www.habr.com