Isika rehetra dia mamaha olana " " imbetsaka isan'andro. Tsy nahy mazava ho azy. Mamaha azy io isika eny am-piasana na rehefa mijery Internet na rehefa mandamina ny entanay eo ambony latabatra. lalana fohy indrindra Toa somary… be loatra? Andeha hojerentsika. Alao sary an-tsaina, nanapa-kevitra ny hihaona amin'ny namana ianao, eny… ndao atao hoe any amin'ny cafe. Voalohany indrindra, mila mitady lalana (na lalana) mankany amin'ny cafe ianao, ka manomboka mitady fitateram-bahoaka misy (raha mandeha an-tongotra ianao) na lalana sy arabe (raha mitondra fiara). Mitady lalana avy any amin'ny toerana misy anao ankehitriny mankany amin'ny kafe ianao fa tsy lalana "izay" - ny fohy na haingana indrindra. Ity misy ohatra iray hafa, izay tsy dia mazava loatra toy ny teo aloha. Rehefa miasa ianao dia manapa-kevitra ny hanao "fohy" amin'ny sisin-dalana satria eny ... "fohy" izany ary "haingana kokoa" ny mandeha amin'io lalana io. Ahoana anefa no nahafantaranao fa haingana kokoa io "fohy fohy" io? Miorina amin'ny traikefanao manokana dia namaha olana "lalana fohy indrindra" ianao ary nifidy lalana iray, izay mandalo amin'ny sisin-dalana. Amin'ireo ohatra roa ireo, ny lalana "fohy indrindra" dia voafaritra na amin'ny halavirana na ny fotoana ilaina hifindrana amin'ny toerana iray mankany amin'ny iray hafa. Ny ohatra fitsangatsanganana dia fampiharana ara-boajanahary amin'ny ary indrindra indrindra ny olana "lalana fohy indrindra". Ahoana anefa ny amin’ilay ohatra amin’ny fandaminana zavatra eo ambony latabatra? Amin'ity tranga ity, ny "fohy" dia afaka maneho isa na fahasarotana amin'ny hetsika tsy maintsy ataonao mba hahazoana, ohatra, taratasy iray: misokatra birao, misokatra lahatahiry, maka ravin-taratasy vs maka ravin-taratasy avy hatrany amin'ny birao. . teolojian'ny grafika Ireo ohatra rehetra voalaza etsy ambony ireo dia maneho olana amin'ny fitadiavana lalana fohy indrindra eo anelanelan'ny vertex roa amin'ny grafika (lalana na lalana eo anelanelan'ny toerana roa, hetsika maromaro na fahasarotana amin'ny fahazoana ravin-taratasy avy amin'ny toerana iray na hafa). Ity kilasy olana amin'ny lalana fohy indrindra ity dia antsoina hoe ary ny algorithm fototra hamahana ireo olana ireo dia ny , izay manana fahasarotana fikajiana . SSSP (Single Source Shortest Path) algorithm Dijkstra O(n^2) Saingy, indraindray isika dia mila mahita ny lalana fohy indrindra eo anelanelan'ny vertex rehetra. Diniho ity ohatra manaraka ity: mamorona sarintany ho anao ianao fihetsiketsehana tsy tapaka eo anelanelan'ny , ary . Amin'ity tranga ity dia hiafara amin'ny lalana 6 ianao: , , , , sy (mety ho hafa ny lalana mivadika noho ny lalana tokana ohatra) . trano ny asa ny teatra work ⭢ home home ⭢ work work ⭢ theatre theatre ⭢ work home ⭢ theatre theatre ⭢ home Ny fampidirana toerana bebe kokoa amin'ny sari-tany dia hiteraka fitomboana lehibe amin'ny fitambarana - araka ny formula of dia azo kajy toy ny: permutation n combinatorics A(k, n) = n! / (n - m)! // where n - is a number of elements, // k - is a number of elements in permutation (in our case k = 2) Izay manome lalana 12 ho an'ny toerana 4 ary lalana 90 ho an'ny toerana 10 (izay mahavariana). Marihina… tsy misy fiheverana ireo teboka manelanelana eo amin'ny toerana izany, izany hoe, raha handeha hiasa any an-trano ianao dia mila miampita arabe 4, mandehandeha manamorona ny renirano ary miampita tetezana. Raha alaina sary an-tsaina, ny lalana sasany dia mety manana teboka mpanelanelana iraisana… eny… vokatr'izany dia hanana grafika tena lehibe isika, miaraka amin'ny vertex be dia be, izay ahitana ny vertex tsirairay na toerana iray na teboka manelanelana manan-danja. Ny kilasin'ny olana, izay ilaintsika hahitana ny lalana fohy indrindra eo anelanelan'ny vertexes rehetra ao amin'ny grafika, dia antsoina hoe ary ny algorithm fototra amin'ny famahana ireo olana ireo dia ny , izay manana fahasarotana amin'ny kajy. APSP (All Pairs Shortest Paths) algorithm Floyd-Warshall O(n^3) Ary ity no algorithm izay hampiharintsika anio 🙂 Floyd-Warshall algorithm Ny algorithm Floyd-Warshall dia mahita ny lalana fohy indrindra eo anelanelan'ny vertexes tsirairay ao anaty grafika. Ny algorithm dia navoakan'i Robert Floyd tao amin'ny [1] (jereo ny fizarana "References" raha mila fanazavana fanampiny). Tamin'io taona io ihany, Peter Ingerman ao amin'ny [2] dia nanoritsoritra ny fampiharana maoderina ny algorithm amin'ny endrika telo nested loops: for algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i, j] = min(W[i, j], W[i, k] + W[k, j]) end for end for end for end algorithm // where W - is a weight matrix of N x N size, // min() - is a function which returns lesser of it's arguments Raha toa ka tsy nanana fiovana hiasa amin'ny grafika aseho amin'ny endrika matrix ianao dia mety ho sarotra ny hahatakatra ny ataon'ny algorithm etsy ambony. Noho izany, mba hahazoana antoka fa eo amin'ny pejy iray ihany isika, andeha hojerentsika ny fomba azo aseho amin'ny endrika matrix sy ny antony maha-soa ny fanehoana toy izany hamahana ny olan'ny lalana fohy indrindra. Ity sary etsy ambany ity dia mampiseho grafika misy vertex 5. Eo amin'ny ankavia, aseho amin'ny endrika hita maso ny kisary, izay vita amin'ny faribolana sy zana-tsipìka, ka ny faribolana tsirairay dia maneho vertex ary ny zana-tsipìka maneho sisiny misy lalana. Ny isa ao anaty faribolana dia mifanandrify amin'ny laharan'ny vertex ary ny isa eo ambonin'ny sisiny dia mifanitsy amin'ny lanjan'ny sisiny. Eo amin'ny ankavanana, dia aseho amin'ny endrika matrix lanja ilay grafika mitovy. Weight matrix dia endriky ny izay misy "lanja" ny sela matrix tsirairay - elanelana eo anelanelan'ny vertex (row) sy vertex (tsanganana). Weight matrix dia tsy ahitana fampahalalana momba ny "lalana" eo anelanelan'ny vertex (lisitra avy amin'ny vertex izay hidiranao avy amin'ny ka hatramin'ny ) - lanja (halavirana) eo anelanelan'ireo vertex ireo fotsiny. mivantana sy lanja matrix adjacency i j i j Ao amin'ny matrix lanja dia hitantsika fa mitovy ny lanjan'ny sela amin'ny lanja eo anelanelan'ny vertex . Izany no antony, raha mandinika lalana avy amin'ny vertex (andalana ) isika, dia ho hitantsika fa … misy lalana iray ihany – manomboka amin'ny ka hatramin'ny . Saingy, amin'ny fanehoana an-tsary dia afaka mahita mazava tsara ny lalana manomboka amin'ny vertex mankany vertex sy (hatramin'ny vertex ). Ny anton'izany dia tsotra - amin'ny toe-javatra voalohany, ny matrix lanja dia misy elanelana eo amin'ny vertex mifanakaiky ihany. Na izany aza, ity fampahalalana ity fotsiny dia ampy ny ambiny. mifanakaiky 0 0 0 1 0 2 3 1 hahitana Andeha hojerentsika ny fomba fiasa. Tandremo ny cellule . Ny sandany dia manondro, misy lalana avy amin'ny vertex mankany vertex miaraka amin'ny lanja mitovy amin'ny (amin'ny teny fohy dia azontsika soratana amin'ny hoe: ). Miaraka amin'izany fahalalana izany, dia afaka mijery ny sela rehetra amin'ny laharana isika (izay misy ny lanja rehetra amin'ny lalana rehetra manomboka amin'ny vertex ) ary miverina amin'ny laharana ity fampahalalana ity, mampitombo ny lanja amin'ny (ny lanjan'ny ). W[0, 1] 0 1 1 0 ⭢ 1: 1 1 1 0 1 W[0, 1] Amin'ny fampiasana ireo dingana mitovy ireo dia afaka mahita lalana avy amin'ny vertex mankany amin'ny vertex hafa isika. Mandritra ny fikarohana dia mety hisy lalana mihoatra ny iray mankany amin'ny vertex iray ary ny tena zava-dehibe dia mety tsy hitovy ny lanjan'ireo lalana ireo. Ny ohatra iray amin'ny toe-javatra toy izany dia aseho eo amin'ny sary etsy ambany, izay ahitana ny fikarohana avy amin'ny vertex ka hatramin'ny vertex dia nahitana lalana iray hafa mankany amin'ny vertex amin'ny lanja kely kokoa. 0 0 2 3 Manana lalana roa isika: lalana tany am-boalohany – ary lalana vaovao vao hitanay – (tadidio fa tsy misy lalana ny matrice lanja, ka tsy fantatsika hoe iza vertexes dia tafiditra ao amin'ny lalana tany am-boalohany). Izao no fotoana handraisana fanapahan-kevitra hitazona ny iray fohy indrindra ary hanoratra ao anaty sela . 0 ⭢ 3: 4 0 ⭢ 2 ⭢ 3: 3 3 W[0, 3] Toa vao nahita ny lalanay fohy indrindra izahay! Ny dingana izay vao hitanay dia ny fototry ny algorithm Floyd-Warshall. Jereo indray mandeha ny pseudocode an'ny algorithm: algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i, j] = min(W[i, j], W[i, k] + W[k, j]) end for end for end for end algorithm Ny tsingerina ivelany indrindra dia miverimberina amin'ny vertex rehetra ao anaty grafika ary isaky ny famerimberenana, ny variable dia maneho ny vertex . Ny tsingerina anatiny amin'ny koa dia miverimberina amin'ny vertex rehetra ao amin'ny grafika ary amin'ny famerimberenana tsirairay, maneho vertex . Ary farany, ny tsingerina anatiny indrindra dia miverimberina amin'ny vertex rehetra ao amin'ny grafika ary isaky ny famerimberenana, dia maneho ny vertex Amin'ny fitambarany dia manome antsika izao manaraka izao: isaky ny famerimberenana dia mikaroka lalana avy amin'ny vertex rehetra mankany amin'ny vertex rehetra amin'ny vertex isika. Ao anatin'ny tsingerina iray dia mampitaha ny lalana (soloin'i ) miaraka amin'ny lalana (aseho amin'ny fitambaran'ny sy ) ary manoratra ny fohy indrindra. ny iray miverina . for k k izay tadiavintsika lalana for i i izay tadiavintsika ny lalana avy amin'ny for j j tadiavintsika. k i j k i ⭢ j W[i, j] i ⭢ k ⭢ j W[I, k] W[k, j] W[i, j] Ankehitriny, rehefa azontsika ny mekanika dia izao no fotoana hampiharana ny algorithm. Fampiharana fototra Ny kaody loharano sy ny grafika andrana dia hita ao amin'ny ao amin'ny GitHub. Ny kisary andrana dia hita ao amin'ny lahatahiry . Ny mari-pamantarana rehetra amin'ity lahatsoratra ity dia ampiharina amin'ny rakitra . tahiry Data/Sparse-Graphs.zip APSP01.cs Alohan'ny hidirana amin'ny fampiharana dia mila manazava fotoana ara-teknika vitsivitsy isika: Ny fampiharana rehetra dia miasa miaraka amin'ny matrix lanja aseho amin'ny endrika tsipika. Ny fampiharana rehetra dia mampiasa aritmetika integer. Ny tsy fisian'ny lalana eo anelanelan'ny vertex dia asehon'ny lanja tsy tapaka manokana: . NO_EDGE = (int.MaxValue / 2) - 1 Andeha hojerentsika izao ny antony mahatonga izany. Rehefa miresaka momba ny matrix isika dia mamaritra ny sela amin'ny teny hoe "lahatra" sy "tsanganana". Noho izany dia toa voajanahary ny maka sary an-tsaina ny matrix amin'ny endrika "efamira" na "mahitsizoro" (sary 4a). Momba ny #1. Na izany aza, tsy voatery midika izany fa tsy maintsy misolo tena ny matrix amin'ny endrika array (sary 4b) isika mba hifikitra amin'ny eritreritsika. Raha tokony ho izany, dia afaka maneho matrix amin'ny endrika laharan-tsipika (sary 4c) izay kajy ny tondron'ny sela tsirairay amin'ny fampiasana ity formula manaraka ity: i = row * row_size + col; // where row - cell row index, // col - cell column index, // row_size - number of cells in a row. Ny laharan'ny tsipika lanja dia amin'ny fanatanterahana mahomby ny algorithm Floyd-Warshall. Ny anton'izany dia tsy tsotra sy amin'ny antsipiriany dia mendrika lahatsoratra manokana… na lahatsoratra vitsivitsy. Na izany aza, amin'izao fotoana izao, zava-dehibe ny manonona fa ny fanehoana toy izany dia manatsara , izay raha ny marina dia misy fiantraikany lehibe amin'ny fahombiazan'ny algorithm. fepetra takiana ny toerana misy ny angona Eto, mangataka aminao aho mba hino ahy ary ao an-tsainao fotsiny ity fampahalalana ity ho fepetra, na izany aza, manoro hevitra anao aho mba handany fotoana kely sy handalina ny fanontaniana, ary raha ny marina – aza mino ny olona amin'ny Internet. . - Fanamarihan'ny mpanoratra Raha mijery akaiky ny pseudocode algorithm ianao dia tsy hahita fanamarinana mifandraika amin'ny fisian'ny lalana eo anelanelan'ny vertex roa. Fa kosa, ny pseudocode dia mampiasa function. Tsotra ny antony – tany am-boalohany, raha tsy misy lalana manelanelana ny vertexes, dia apetraka amin'ny ny sandan'ny sela ary amin'ny fiteny rehetra, afa-tsy ny JavaScript, ny soatoavina rehetra dia latsaky ny . Raha misy integer dia mety halaim-panahy ny mampiasa ho sanda "tsy misy lalana". Na izany aza dia hitarika amin'ny fihoaran'ny integer izany raha toa ka mitovy amin'ny ny soatoavin'ny lalana sy . Izany no antony hampiasantsika sanda iray izay latsaky ny antsasaky ny . Momba ny #2. min() infinity infinity int.MaxValue int.MaxValue i ⭢ k k ⭢ j int.MaxValue Hey! Fa maninona no tsy afaka manamarina fotsiny raha misy lalana alohan'ny hanaovana kajy. Ohatra amin'ny fampitahana ny lalana roa amin'ny 0 (raha maka aotra ho sanda "tsy misy lalana"). - Mpamaky misaina Azo atao tokoa izany saingy indrisy fa hitarika ho amin'ny fanasaziana goavana izany. Raha fintinina, ny CPU dia mitazona antontan'isa momba ny valin'ny fanombanana sampana ex. rehefa manombana ho na ny sasany amin'ireo fanambarana . Mampiasa an'io antontan'isa io izy mba hanatanterahana ny kaody "sampana vinavinaina ara-statistika" alohan'ny tena izy tombanana ny fanambarana (antsoina hoe ) ary noho izany dia manatanteraka kaody mahomby kokoa. Na izany aza, rehefa tsy marina ny vinavinan'ny CPU dia miteraka fahavoazana lehibe izany raha oharina amin'ny vinavina marina sy ny famonoana tsy misy fepetra satria ny CPU dia tsy maintsy mijanona sy manao kajy ny sampana marina. true false if if famonoana fanombantombanana Satria isaky ny famerimberenana dia manavao ampahany manan-danja amin'ny matrix lanja isika, dia lasa tsy misy ilàna azy ny antontan'isa sampana CPU satria tsy misy lamina kaody, ny sampana rehetra dia mifototra amin'ny data. Noho izany, ny fisavana toy izany dia hiteraka be dia be. k fahadisoam-panantenana Eto koa aho dia mangataka aminao mba hino ahy (amin'izao fotoana izao) ary avy eo mandany fotoana handinihana ilay lohahevitra. Eh, toa vitantsika ny ampahany amin'ny teorika - andao hampihatra ny algorithm (ambarantsika ho ity fampiharana ity): Baseline public void Baseline(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } } } } Ny kaody etsy ambony dia saika dika mitovy amin'ilay pseudocode voalaza teo aloha miaraka amin'ny singa tokana - fa tsy dia ampiasainay manavao sela raha ilaina ihany. Math.Min() if Hey! Andraso aloha fa tsy ianao ve no nanoratra teny be dia be hoe maninona raha tsy tsara eto ary andalana vitsivitsy aty aoriana dia izahay mihitsy no mampiditra raha? - Mpamaky misaina Tsotra ny antony. Amin'ny fotoana anoratana ny JIT dia mamoaka fehezan-dalàna saika mitovy amin'ny fampiharana sy . Azonao atao ny manamarina izany amin'ny antsipiriany ao amin'ny fa ireto misy sombin-tsarimihetsika lehibe: if Math.Min sharplab.io // // == Assembly code of implementation of innermost loop for of j using if. // 53: movsxd r14, r14d // // compare matrix[i * sz + j] and distance (Condition) // 56: cmp [rdx+r14*4+0x10], ebx 5b: jle short 64 // // if matrix[i * sz + j] greater than distance write distance to matrix // 5d: movsxd rbp, ebp 60: mov [rdx+rbp*4+0x10], ebx 64: // end of loop // // == Assembly code of implementation of innermost loop for of j using Math.Min. // 4f: movsxd rbp, ebp 52: mov r14d, [rdx+rbp*4+0x10] // // compare matrix[i * sz + j] and distance (Condition) // 57: cmp r14d, ebx. // // if matrix[i * sz + j] less than distance write value to matrix // 5a: jle short 5e // // otherwise write distance to matrix // 5c: jmp short 61 5e: mov ebx, r14d 61: mov [rdx+rbp*4+0x10], ebx 65: // end of loop Mety ho hitanao, na inona na inona mampiasa na dia mbola misy ny fanamarinana fepetra. Na izany aza, tsy misy ny fanoratana tsy ilaina. if Math.Min if Ankehitriny rehefa vita ny fampiharana, tonga ny fotoana hampandehanana ny kaody ary hijerena ny hafainganam-pandehany?! Azonao atao ny manamarina ny fahamarinan'ny kaody amin'ny alàlan'ny fanaovana fitiliana ao anaty . tahiry Mampiasa (version 0.12.1) aho amin'ny code benchmark. Ny grafika rehetra ampiasaina amin'ny mari-pamantarana dia misy vertex 300, 600, 1200, 2400 ary 4800. Ny isan'ny sisiny amin'ny grafika dia manodidina ny 80% amin'ny ambony indrindra azo atao izay ho an'ny grafofaonina acyclic dia azo atao toy izao: Benchmark.NET tarihina, grafofa acyclic var max = v * (v - 1)) / 2; // where v - is a number of vertexes in a graph. Andao hirotsaha! Ireto ny vokatry ny benchmark mandeha amin'ny PC-ko (Windows 10.0.19042, Intel Core i7-7700 CPU 3.60Ghz (Kaby Lake) / 8 lojika processeur / 4 cores): FOMBA Size fanahy fahadisoana StdDev fototra 300 27.525 ms 0.1937 ms 0.1617 ms fototra 600 217.897 ms 1.6415 ms 1.5355 ms fototra 1200 1,763.335 ms 7.4561 ms 6.2262 ms fototra 2400 14,533.335 ms 63.3518 ms 52.9016 ms fototra 4800 119,768.219 ms 181.5514 ms 160.9406 ms Avy amin'ny valiny hitantsika, mitombo be ny fotoana kajy raha oharina amin'ny haben'ny grafika - ho an'ny grafika misy vertex 300 dia 27 milliseconds, ho an'ny grafika 2400 vertex - 14.5 segondra ary ho an'ny grafika 4800 - 119 segondra izay ! efa ho 2 mn Raha mijery ny kaody algorithm dia mety ho sarotra ny mieritreritra, misy zavatra azontsika atao mba hanafainganana ny kajy… satria eny… misy tadivavarana TELO, tadivavarana TELO fotsiny. Na izany aza, tahaka ny mitranga matetika - miafina amin'ny antsipiriany ny fahafaha-manao 🙂 Fantaro ny angon-drakitrao - kisary kely Algorithm Floyd-Warshall dia algorithm fototra hamahana ny olan'ny lalana fohy indrindra amin'ny tsiroaroa, indrindra raha ny momba ny grafika na (satria ny algorithm dia mikaroka lalana eo anelanelan'ny vertexes rehetra). matevina feno Na izany aza, amin'ny andrana ataonay dia mampiasa grafika izahay, izay manana fananana mahafinaritra - raha misy lalana avy amin'ny vertex mankany vertex , dia tsy misy lalana avy amin'ny vertex mankany vertex . Aminay, midika izany fa be dia be ny vertexes tsy mifanakaiky izay azontsika tsidihana raha tsy misy lalana avy amin'ny ka hatramin'ny (isika dia manondro an'io fampiharana io ho ). acyclic mivantana 1 2 2 1 i k SpartialOptimisation public void SpartialOptimisation(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == NO_EDGE) { continue; } for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } } } } Ireto ny valin'ny fampiharana teo aloha ( ) sy ankehitriny ( ) amin'ny andiana grafika mitovy (ny valiny haingana indrindra dia asongadina amin'ny ): Baseline SpartialOptimisation bold FOMBA Size fanahy fahadisoana StdDev Taham fototra 300 27.525 ms 0.1937 ms 0.1617 ms 1.00 SpartialOptimization 300 12.399 ms 0,0943 ms 0,0882 ms 0.45 fototra 600 217.897 ms 1.6415 ms 1.5355 ms 1.00 SpartialOptimization 600 99.122 ms 0.8230 ms 0,7698 ms 0.45 fototra 1200 1,763.335 ms 7.4561 ms 6.2262 ms 1.00 SpartialOptimization 1200 766.675 ms 6.1147 ms 5.7197 ms 0.43 fototra 2400 14,533.335 ms 63.3518 ms 52.9016 ms 1.00 SpartialOptimization 2400 6,507.878 ms 28.2317 ms 26.4079 ms 0.45 fototra 4800 119,768.219 ms 181.5514 ms 160.9406 ms 1.00 SpartialOptimization 4800 55,590.374 ms 414.6051 ms 387.8218 ms 0.46 Tena mahavariana! Nahena antsasany ny fotoana kajy! Mazava ho azy, ny denser ny grafika, dia ho kely kokoa ny hafainganam-pandeha. Na izany aza, ity dia iray amin'ireo optimisations izay azo ampiasaina raha fantatrao mialoha hoe inona no karazana angona kasainao hiarahana miasa. Afaka manao bebe kokoa ve isika? 🙂 Fantaro ny fitaovanao - parallèle Ny PC-ko dia manana processeur misy processeur logical 8 ( ) na core 4 miaraka amin'ny teknolojia . Ny fananana fototra mihoatra ny iray dia toy ny fananana “tanana mitsitsy” bebe kokoa izay azontsika ampiasaina. Noho izany, andeha hojerentsika izay ampahany amin'ny asa azo zaraina tsara amin'ny mpiasa marobe ary avy eo, ampifanaraho izany. Inter Core i7-7700 CPU 3.60GHz (Kaby Lake) HW Hyper-Threading Loops no kandidà miharihary indrindra amin'ny fampitoviana satria amin'ny ankamaroan'ny tranga dia mahaleo tena ny famerimberenana ary azo tanterahina miaraka. Ao amin'ny algorithm, manana tadivavarana telo isika izay tokony hodinihina sy hijerena raha misy fiankinan-doha manakana antsika tsy hampifanaraka azy ireo. Andeha isika hanomboka loop. Amin'ny tadivavarana tsirairay dia manisa lalana avy amin'ny vertex tsirairay mankany amin'ny vertex tsirairay amin'ny vertex . Ny lalana vaovao sy nohavaozina dia voatahiry ao anaty matrix lanja. Raha mijery ny fanamafisam-peo mety ho hitanao - azo tanterahina amin'ny filaharana rehetra: 0, 1, 2, 3 na 3, 1, 2, 0 tsy misy fiantraikany amin'ny vokatra. Na izany aza, mbola tsy maintsy tanterahina amin'ny filaharana izy ireo, raha tsy izany dia tsy afaka mampiasa lalana vaovao na nohavaozina ny sasany amin'ireo fampitaovana satria tsy hosoratana amin'ny matrix lanja. Ny tsy fitovian-kevitra toy izany dia tena hanorotoro ny vokatra. Mila mitady hatrany àry isika. for of k k Ny kandida manaraka dia loop. Ao amin'ny tadivavarana tsirairay dia mamaky lalana iray avy amin'ny vertex mankany vertex (cell: ), lalana iray avy amin'ny vertex mankany vertex (cell: ]) ary avy eo manamarina raha fantatra ny lalana avy amin'ny mankany amin'ny (elatra: ) dia fohy kokoa noho lalana (ny fitambaran'ny: + ). Raha mijery akaiky kokoa ny lamina fidirana ianao dia mety ho tsikaritrareo - isaky ny famerimberenana dia mamaky angon-drakitra avy amin'ny row ary nohavaozina row izay midika hoe - mahaleo tena ny iterations ary azo tanterahina tsy amin'ny filaharana rehetra fa amin'ny parallèle ihany koa! for of i i k W[i, k] k j W[k, j i j W[i, j] i ⭢ k ⭢ j W[i, k] W[k, j] k i i Toa mampanantena izany, koa andao hampihatra izany (famaritanay ho ity fampiharana ity). SpartialParallelOptimisations loop koa dia azo ampitahaina. Na izany aza, ny parallelisation ny tsingerina anatiny indrindra amin'ity tranga ity dia tena tsy mahomby. Azonao atao ny manamarina izany amin'ny alàlan'ny fanovana tsotra vitsivitsy amin'ny . for of j kaody loharano - Fanamarihan'ny mpanoratra public void SpartialParallelOptimisations(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { Parallel.For(0, sz, i => { if (matrix[i * sz + k] == NO_EDGE) { return; } for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } }); } } Ireto ny valin'ny fampiharana , ary amin'ny andiana grafika iray ihany (ny parallelisation dia atao amin'ny fampiasana kilasy ): Baseline SpartialOptimisation SpartialParallelOptimisations Parallel FOMBA Size fanahy fahadisoana StdDev Taham fototra 300 27.525 ms 0.1937 ms 0.1617 ms 1.00 SpartialOptimization 300 12.399 ms 0,0943 ms 0,0882 ms 0.45 SpartialParallelOptimisations 300 6.252 ms 0,0211 ms 0,0187 ms 0.23 fototra 600 217.897 ms 1.6415 ms 1.5355 ms 1.00 SpartialOptimization 600 99.122 ms 0.8230 ms 0,7698 ms 0.45 SpartialParallelOptimisations 600 35.825 ms 0.1003 ms 0,0837 ms 0.16 fototra 1200 1,763.335 ms 7.4561 ms 6.2262 ms 1.00 SpartialOptimization 1200 766.675 ms 6.1147 ms 5.7197 ms 0.43 SpartialParallelOptimisations 1200 248.801 ms 0,6040 ms 0,5043 ms 0.14 fototra 2400 14,533.335 ms 63.3518 ms 52.9016 ms 1.00 SpartialOptimization 2400 6,507.878 ms 28.2317 ms 26.4079 ms 0.45 SpartialParallelOptimisations 2400 2,076.403 ms 20.8320 ms 19.4863 ms 0.14 fototra 4800 119,768.219 ms 181.5514 ms 160.9406 ms 1.00 SpartialOptimization 4800 55,590.374 ms 414.6051 ms 387.8218 ms 0.46 SpartialParallelOptimisations 4800 15,614.506 ms 115.6996 ms 102.5647 ms 0.13 Hitantsika avy amin'ny valiny fa ny fampitoviana ny loop dia nampihena in-2-4 ny fotoana kajy raha oharina amin'ny fampiharana teo aloha ( )! Tena mahavariana izany, na izany aza, zava-dehibe ny mitadidy, ny fampitoviana amin'ny kajy madio dia mandany ny loharanon-karena rehetra misy izay mety hitarika amin'ny hanoanana loharanon'ny fampiharana hafa ao amin'ny rafitra. for of i SpartialOptimisation Tokony hampiasaina amim-pitandremana ny parallelisation. Araka ny mety ho eritreretinao – tsy izao no farany 🙂 Fantaro ny sehatrao - vectorisation dia fanovàna fehezan-dalàna miasa amin'ny singa tokana ho fehezan-dalàna miasa amin'ny singa maromaro miaraka. Vectorisation Mety ho toy ny raharaha sarotra izany, ka andeha hojerentsika ny fomba fiasa amin'ny ohatra tsotra: var a = new [] { 5, 7, 8, 1 }; var b = new [] { 4, 2, 2, 6 }; var c = new [] { 0, 0, 0, 0 }; for (var i = 0; i < 4; ++i) c[i] = a[i] + b[i]; Amin'ny fomba , ny famonoana ny amin'ny etsy ambony loop amin'ny haavon'ny CPU dia azo aseho toy izao manaraka izao: tafahoatra 0 for Toy izao ny zava-mitranga. Ny CPU dia mampiditra ny sandan'ny array sy avy amin'ny fitadidiana mankany amin'ny rejisitra CPU (ny rejistra iray dia afaka mitazona sanda ). Avy eo ny CPU dia manatanteraka asa fanampiny scalar amin'ireo rejisitra ireo ary manoratra ny valiny ao anaty fitadidiana lehibe - avy hatrany ao anaty array . Averina inefatra io dingana io alohan'ny hifaranan'ny tadivavarana. a b iray marina c Ny vectorisation dia midika fampiasana rejisitra CPU manokana - rejisitra vector na SIMD (toro-hevitra maromaro maromaro), ary torolàlana CPU mifanaraka amin'izany mba hanatanterahana ny asa amin'ny soatoavina maromaro indray mandeha: Toy izao ny zava-mitranga. Ny CPU dia mameno ny sandan'ny array sy avy amin'ny fitadidiana mankany amin'ny rejisitra CPU (na izany aza, amin'ity indray mitoraka ity, ny rejistra vector iray dia afaka mitazona sanda array ). Avy eo ny CPU dia manatanteraka hetsika fanampiny vector amin'ireo rejisitra ireo ary manoratra ny valiny ho ao amin'ny fitadidiana fototra - avy hatrany ao anaty array . Satria miasa amin'ny soatoavina roa miaraka isika, dia miverimberina indroa io dingana io fa tsy in-efatra. a b roa c Mba hampiharana ny vectorisation amin'ny .NET dia azontsika ampiasaina - karazana sy (azontsika atao koa ny mampiasa karazana avy amin'ny anaran'ny , na izany aza dia mandroso kely izy ireo amin'ny fampiharana ankehitriny, ka tsy hampiasa azy ireo aho, fa mahatsapa. maimaim-poana ny manandrana azy ireo): Vector Vector<T> System.Runtime.Intrinsics public void SpartialVectorOptimisations(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } } } } Ny kaody véctorised dia mety ho somary hafahafa, koa andao hojerentsika tsikelikely. Mamorona vector amin'ny lalana izahay: . Vokatr'izany, raha afaka mitazona soatoavina efatra amin'ny karazana ny vector ary ny lanjan'ny lalana dia mitovy amin'ny 5, dia hamorona vector misy 5's efatra isika - [5, 5, 5, 5]. Manaraka izany, isaky ny miverimberina, dia ataontsika kajy ny lalana avy amin'ny vertex mankany amin'ny vertexes . i ⭢ k var ik_vec = new Vector<int>(matrix[i * sz + k]) int i ⭢ k i j, j + 1, ..., j + Vector<int>.Count Property dia mamerina ny isan'ny singa amin'ny karazana izay mifanaraka amin'ny rejistra vetaveta. Miankina amin'ny maodely CPU ny haben'ny rejistra vector, ka ity fananana ity dia afaka mamerina sanda samihafa amin'ny CPU samihafa. Vector<int>.Count int - Fanamarihan'ny mpanoratra Ny fizotry ny kajy manontolo dia azo zaraina ho dingana telo: Ampidiro ao anaty vector ny fampahalalana avy amin'ny matrix lanja: sy . ij_vec ikj_vec Ampitahao ny vectors sy ary mifidiana sanda kely indrindra ho lasa vector vaovao. ij_vec ikj_vec r_vec Manorata miverina amin'ny matrix lanja. r_vec Na dia tsotra aza sy , dia mila fanazavana. Araka ny voalaza teo aloha, miaraka amin'ny vectors dia manodinkodina soatoavina maromaro miaraka amin'ny fotoana iray. Noho izany, ny vokatry ny asa sasany dia tsy mety ho tokana, izany hoe, fampitahana dia tsy afaka mamerina na satria mampitaha sanda maromaro. Noho izany dia mamerina vector vaovao izay valiny fampitahana eo amin'ny soatoavina mifanandrify avy amin'ny vectors sy ( , raha kely noho ny sanda avy amin'ny ary raha tsy izany). Tsy dia ilaina loatra ny véctor naverina (ho azy), fa afaka mampiasa isika mba hanesorana ny soatoavina ilaina avy amin'ny vectors sy ho lasa vector vaovao – . Ity hetsika ity dia mamerina véctor vaovao izay misy soatoavina mitovy amin'ny soatoavina roa mifanandrify amin'ny vektora fampidirana, izany hoe, raha mitovy amin'ny ny sandan'ny vector , dia mifidy sanda avy amin'ny ny fandidiana, raha tsy izany dia mifidy sanda avy amin'ny . ny #1 #3 ny #2 Vector.LessThan(ij_vec, ikj_vec) true false ikj_vec ij_vec ikj_vec -1 ij_vec 0 Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec) ij_vec ikj_vec r_vec -1 lt_vec ij_vec ikj_vec Ankoatra ny , misy ampahany iray hafa, mitaky fanazavana - ny loop faharoa tsy misy vectorised. Ilaina izany rehefa tsy vokatra avy amin'ny ny haben'ny matriky lanja. Amin'izany toe-javatra izany, ny loop lehibe dia tsy afaka manodina ny soatoavina rehetra (satria tsy afaka mampiditra ampahany amin'ny vector ianao) ary faharoa, tsy misy vectored, loop dia hanao kajy ny fiverenana sisa. #2 Vector<int>.Count Ireto ny vokatr'izany sy ny fampiharana rehetra teo aloha: FOMBA sz fanahy fahadisoana StdDev Taham fototra 300 27.525 ms 0.1937 ms 0.1617 ms 1.00 SpartialOptimization 300 12.399 ms 0,0943 ms 0,0882 ms 0.45 SpartialParallelOptimisations 300 6.252 ms 0,0211 ms 0,0187 ms 0.23 SpartialVectorOptimisations 300 3,056 ms 0,0301 ms 0,0281 ms 0.11 fototra 600 217.897 ms 1.6415 ms 1.5355 ms 1.00 SpartialOptimization 600 99.122 ms 0,8230 ms 0,7698 ms 0.45 SpartialParallelOptimisations 600 35.825 ms 0.1003 ms 0,0837 ms 0.16 SpartialVectorOptimisations 600 24.378 ms 0,4320 ms 0,4041 ms 0.11 fototra 1200 1,763.335 ms 7.4561 ms 6.2262 ms 1.00 SpartialOptimization 1200 766.675 ms 6.1147 ms 5.7197 ms 0.43 SpartialParallelOptimisations 1200 248.801 ms 0,6040 ms 0,5043 ms 0.14 SpartialVectorOptimisations 1200 185.628 ms 2.1240 ms 1,9868 ms 0.11 fototra 2400 14,533.335 ms 63.3518 ms 52.9016 ms 1.00 SpartialOptimization 2400 6,507.878 ms 28.2317 ms 26.4079 ms 0.45 SpartialParallelOptimisations 2400 2,076.403 ms 20.8320 ms 19.4863 ms 0.14 SpartialVectorOptimisations 2400 2,568.676 ms 31.7359 ms 29.6858 ms 0.18 fototra 4800 119,768.219 ms 181.5514 ms 160.9406 ms 1.00 SpartialOptimization 4800 55,590.374 ms 414.6051 ms 387.8218 ms 0.46 SpartialParallelOptimisations 4800 15,614.506 ms 115.6996 ms 102.5647 ms 0.13 SpartialVectorOptimisations 4800 18,257.991 ms 84.5978 ms 79.1329 ms 0.15 Avy amin'ny vokatra dia miharihary, ny vectorisation dia nampihena be ny fotoana kajy - in-3 ka hatramin'ny in-4 raha oharina amin'ny dikan-teny tsy mitovy ( ). Ny fotoana mahaliana eto dia ny dikan-vectorised koa dia mihoatra ny dikan-teny parallel ( ) amin'ny grafika kely kokoa (latsaky ny vertex 2400). SpartialOptimisation SpartialParallelOptimisations Ary farany fa tsy ny kely indrindra – andao hanambatra ny vectorisation sy ny parallèle! Raha liana amin'ny fampiharana azo ampiharina amin'ny vectorisation ianao, dia manoro hevitra anao aho hamaky andian-dahatsoratra nosoratan'i izay nanaovany vectorise (ireo valiny ireo dia hita tao amin'ny fanavaozana ny Garbage Collector tao amin'ny taty aoriana). Dan Shechter Array.Sort .NET 5 Fantaro ny sehatra sy ny fitaovanao - vectorisation sy parallelism! Ny fampiharana farany dia manambatra ny ezaka amin'ny fampitoviana sy ny vectorisation … raha ny marina dia tsy misy maha-tokana azy 🙂 Satria eny, vao avy nosoloina vatana SpartialVectorOptimisations SpartialParallelOptimisations Parallel.For public void SpartialParallelVectorOptimisations(int[] matrix, int sz) { for (var k = 0; k < sz; ++k) { Parallel.For(0, sz, i => { if (matrix[i * sz + k] == NO_EDGE) { return; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; } } }); } } Ny vokatra rehetra amin'ity lahatsoratra ity dia aseho eto ambany. Araka ny efa nampoizina, ny fampiasana mifanandrify sy ny vectorisation dia nampiseho vokatra tsara indrindra, nampihena ny fotoana kajy hatramin'ny in-25 (ho an'ny kisary misy vertex 1200) raha oharina amin'ny fampiharana voalohany. FOMBA sz fanahy fahadisoana StdDev Taham fototra 300 27.525 ms 0.1937 ms 0.1617 ms 1.00 SpartialOptimization 300 12.399 ms 0,0943 ms 0,0882 ms 0.45 SpartialParallelOptimisations 300 6.252 ms 0,0211 ms 0,0187 ms 0.23 SpartialVectorOptimisations 300 3.056 ms 0,0301 ms 0,0281 ms 0.11 SpartialParallelVectorOptimisations 300 3.008 ms 0,0075 ms 0,0066 ms 0.11 fototra 600 217.897 ms 1.6415 ms 1.5355 ms 1.00 SpartialOptimization 600 99.122 ms 0,8230 ms 0,7698 ms 0.45 SpartialParallelOptimisations 600 35.825 ms 0.1003 ms 0,0837 ms 0.16 SpartialVectorOptimisations 600 24.378 ms 0,4320 ms 0,4041 ms 0.11 SpartialParallelVectorOptimisations 600 13.425 ms 0,0319 ms 0,0283 ms 0.06 fototra 1200 1,763.335 ms 7.4561 ms 6.2262 ms 1.00 SpartialOptimization 1200 766.675 ms 6.1147 ms 5.7197 ms 0.43 SpartialParallelOptimisations 1200 248.801 ms 0,6040 ms 0,5043 ms 0.14 SpartialVectorOptimisations 1200 185.628 ms 2.1240 ms 1,9868 ms 0.11 SpartialParallelVectorOptimisations 1200 76.770 ms 0,3021 ms 0,2522 ms 0.04 fototra 2400 14,533.335 ms 63.3518 ms 52.9016 ms 1.00 SpartialOptimization 2400 6,507.878 ms 28.2317 ms 26.4079 ms 0.45 SpartialParallelOptimisations 2400 2,076.403 ms 20.8320 ms 19.4863 ms 0.14 SpartialVectorOptimisations 2400 2,568.676 ms 31.7359 ms 29.6858 ms 0.18 SpartialParallelVectorOptimisations 2400 1,281.877 ms 25.1127 ms 64.8239 ms 0.09 fototra 4800 119,768.219 ms 181.5514 ms 160.9406 ms 1.00 SpartialOptimization 4800 55,590.374 ms 414.6051 ms 387.8218 ms 0.46 SpartialParallelOptimisations 4800 15,614.506 ms 115.6996 ms 102.5647 ms 0.13 SpartialVectorOptimisations 4800 18,257.991 ms 84.5978 ms 79.1329 ms 0.15 SpartialParallelVectorOptimisations 4800 12,785.824 ms 98.6947 ms 87.4903 ms 0.11 Famaranana Ato amin'ity lahatsoratra ity dia nitsofoka kely tamin'ny olan'ny lalana fohy indrindra izahay ary nampihatra algorithm Floyd-Warshall ao amin'ny C# hamahana azy. Nohavaozina ihany koa ny fampiharana ataonay mba hanomezam-boninahitra ny angon-drakitra sy hampiasa ny endri-javatra ambany indrindra amin'ny .NET sy ny fitaovana. Amin'ity lahatsoratra ity dia nilalao ny "all in". Na izany aza, amin'ny fampiharana tena izy dia zava-dehibe ny mitadidy – tsy irery isika. Ny parallelisation hardcore dia mety hanimba ny fahombiazan'ny rafitra ary hiteraka fahavoazana bebe kokoa noho ny tsara. Vectorisation amin'ny lafiny iray hafa dia azo antoka kokoa raha atao amin'ny sehatra tsy miankina. Tsarovy fa ny sasany amin'ireo torolalana vector dia mety tsy misy afa-tsy amin'ny CPU sasany. Manantena aho fa nankafizinao ny famakiana ary nahafinaritra anao tamin'ny "fanindronana" ny zava-bita sasany avy amin'ny algorithm miaraka amin'ny tsingerina TELO fotsiny 🙂 References Floyd, RW Algorithm 97: Lalana fohy indrindra / RW Floyd // Fifandraisana amin'ny ACM. – 1962. – Boky. 5, №. 6. – P. 345-. Ingerman, PZ Algorithm 141: Path matrix / PZ Ingerman // Communications of the ACM. – 1962. – Boky. 5, №. 11. – P. 556.
