Nhanganyaya , takaona magadzirisiro ezvese-pairi pfupi nzira dambudziko uchishandisa iyo . Isu takaongororawo nzira dzinoverengeka dzekuvandudza kuita kwealgorithm nekushandisa parallelism uye vectorization. Muchinyorwa chakapfuura Floyd-Warshall algorithm Nekudaro, kana iwe ukafunga nezve mhedzisiro yeiyo Floyd-Warshall algorithm, iwe unokurumidza kuona iyo inonakidza nguva - isu tinoziva madaro (tsika dzenzira pfupi) pakati pema vertex mugirafu asi isu hatizive "nzira" kureva, hatizive kuti ma vertex api anobatsira munzira imwe neimwe pfupi, uye hatigone kuvaka patsva idzi “nzira” kubva mumibairo yatinayo. Mune ino post, ini ndinokukoka iwe kuti ubatane neni uye kuwedzera iyo Floyd-Warshall algorithm. Panguva ino, tichava nechokwadi chekuti tinogona kuverenga chinhambwe uye kuvakazve "nzira". Chidimbu cheIchi Chinozivikanwa Theory… Tisati tanyura mukodhi uye mabhenji, ngationgororei dzidziso yekuti Floyd-Warshall algorithm inoshanda sei. Heino tsananguro yezvinyorwa zve algorithm: Tinotanga nekumiririra girafu ( ) yehukuru sematrix ( ) yehukuru apo sero rega rega rine huremu hwemupendero kubva kune vertex kusvika kune vertex (ona Mufananidzo 1). Muzviitiko kana pasina mupendero pakati pemavheti, sero rinoiswa kune yakakosha kukosha (inoratidzwa semaseru erima muMufananidzo 1). G N W N x N W[i,j] i j NO_EDGE Kubva zvino zvichienda mberi, tinoti – ine chinhambwe pakati pemavheti na . W[i,j] i j Tevere, tinotora vertex todzokorora nepamaviri ese ema vertex tichitarisa kana nhambwe idiki pane nhambwe inozivikanwa parizvino pakati na . k W[i,j] i ⭢ k ⭢ j i j Hukoshi hudiki hwakachengetwa muW uye nhanho #3 inodzokororwa kune inotevera kusvika mavheti ese ashandiswa se . W[i,j] k G k Heino pseudo-code: 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 Kana yaitwa, sero yega yega yematrix ingave ine chinhambwe chenzira ipfupi pakati pe vertex na kana kukosha, kana pasina nzira pakati pawo. W[i,j] W i j NO_EDGE Sezvandambotaura pakutanga - kungova neruzivo urwu chete kunoita kuti zvisaite kugadzirazve nzira dziri pakati pemavheti aya. Saka… chii chatinofanira kuita kuti tikwanise kuvaka patsva nzira idzi? Zvakanaka ... zvingaite sezviri pachena asi ... tinoda kuunganidza mamwe data! … Chidiki chedzidziso imwechete asi Kubva kune Yakasiyana Engiro Hwaro hweiyo Floyd-Warshall algorithm inzvimbo yezvinhambwe inozivikanwa ine chinhambwe chenzira ingangove itsva kubva kuna kuenda kuburikidza nepakati vertex . W[i,j] i j k Ini ndinokwevera kutarisisa kune iyi tsanangudzo nekuti ndiyo kiyi yekuti tingachengetedza sei ruzivo rwenzira. Ngatitorei yapfuura girafu ye5 vertexes (ona Mufananidzo 2) uye tiite iyo Floyd-Warshall algorithm pairi. Pakutanga, tinoziva nezvese girafu mipendero, inotipa nzira dzinotevera: , , , , uye . 0 ⭢ 1 :2 0 ⭢ 4 :10 1 ⭢ 3 :1 2 ⭢ 4 :1 3 ⭢ 2 :1 3 ⭢ 4 :3 Ini ndinoshandisa iyo "kubva" ⭢ "ku" :"kure" fomati kubva kune kunyora pasi nzira. yapfuura positi - Chinyorwa chemunyori Isu tinoziva zvakare kuti hapana mipendero inotungamira kune vertex , saka kuita algorithm ye haina musoro. Zviri pachena zvakare, kune mupendero mumwechete ( ) unotungamira kubva ku vertex kuenda ku vertex , izvo zvinoitawo kuurayiwa kwezvose (iyo "kubva" pano) hazvina zvazvinoreva uye nekuti vertex ine mipendero na na , hazvina musorowo kuita algorithms kune chero isiri kana (iyo ndi "ku" pano). 0 k = 0 0 ⭢ 1 0 1 i != 0 i 1 2 4 j 2 4 j Ndicho chikonzero danho redu rekutanga richava rekuita algorithm ye , uye . k = 1 i = 0 j = 2,4 Danho Path Comment 1 0 ⭢ 1 ⭢ 2 Nzira yawanikwa. Chinhambwe = 3 (paive pasina) 2 0 ⭢ 1 ⭢ 4 Nzira yawanikwa. Chinhambwe = 8 (chaive gumi). Tawana nzira mbiri: nzira itsva ( ) uye nzira yekudimbudzira ( ). Ose ari maviri anopinda nepakati . Kana tikasachengeta ruzivo urwu (iyo yatinayo kusvika kusvika ) pane imwe nzvimbo izvozvi, inorasika zvachose (uye izvo zvakapesana nezvatinoda). 0 ⭢ 1 ⭢ 2 0 ⭢ 1 ⭢ 4 1 2 4 1 Saka tinofanira kuitei? Tichavandudza matrix nemhando itsva (ona Mufananidzo 3a) uyewo chengetedza kukosha (iyo ) mumasero uye yematrix itsva yehukuru hwakafanana. sematrix asi yakatanga kukosha (ona Mufananidzo 3b). W k k = 1 R[0,2] R[0,4] R W NO_EDGE Parizvino, usatarise kuti chii chaizvo matrix Ngatirambei tichienda uye tiite algorithm yeinotevera . R k = 2 Pano, tichaita kuongorora kwakafanana (kunzwisisa kuti zvipi zvakasanganiswa zvine musoro kuti tiite) sezvatakaita asi panguva ino, tichashandisa matrix pane girafu Tarisa matrix , kunyanya mukoromo #2 uye mutsara #2 (Mufananidzo 4). k = 1, W G W Pano unogona kuona, kune nzira mbiri dzekuenda kuvertex kubva kuvertex uye kubva kuvertex (column #2), uye nzira mbiri kubva kune kuenda kuvertex uye kune vertex (mutsara #2). Kuziva izvozvo, zvine musoro kuita algorithm chete kusanganisa , uye . 2 0 1 2 3 4 k = 2 i = 0,1 j = 3,4 Danho Path Comment 1 0 ⭢ 2 ⭢ 3 Nzira yawanikwa. Kureba = 4 (paive pasina) 2 0 ⭢ 2 ⭢ 4 Nzira yawanikwa. Chinhambwe = 6 (chaive 8) 3 1 ⭢ 2 ⭢ 3 Nzira yawanikwa. Distance = 2 (paive pasina) 4 1 ⭢ 2 ⭢ 4 Nzira yawanikwa. Chinhambwe = 4 (chaive 6) Sezvatatoita kare, tiri kugadzirisa masero , , , ane madaro matsva uye masero , , uye ine (ona Mufananidzo 5). W[0,3] W[0,4] W[1,3] W[1,4] R[0,3] R[0,4] R[1,3] R[1,4] k = 2 Pane chete yasara kuti igadziriswe (nekuti hapana mipendero inotungamira kubva kune vertex kune chero imwe vertex mugirafu). k = 3 4 Zvakare, ngatitarisei matrix (Mufananidzo 6). W Maererano nematrix , kune nzira nhatu dzekuenda kune vertex kubva kune vertexes , uye (column #3), uye pane imwe nzira kubva ku vertex kusvika kune vertex (mutsara #3). Naizvozvo, isu tine nzira dzinotevera dzekugadzirisa: W 3 0 1 2 3 4 Danho Path Comment 1 0 ⭢ 3 ⭢ 4 Nzira yawanikwa. Chinhambwe = 5 (chaive 6) 2 1 ⭢ 3 ⭢ 4 Nzira yawanikwa. Chinhambwe = 3 (chaive 4) 3 2 ⭢ 3 ⭢ 4 Nzira yawanikwa. Chinhambwe = 2 (chaive 3) Iyi yaive yekupedzisira iteration yealgorithm. Chasara kugadzirisa maseru , , ane madaro matsva uye kuseta maseru , , kusvika . W[0,4] W[1,4] W[2,4] R[0,4] R[1,4] R[2,4] 3 Hezvino izvo zvatinazvo pamagumo egorgorithm (Mufananidzo 7). Sezvatinoziva kubva kune , matrix ikozvino ine mapeya ese enzira mapfupi mugirafu Asi chii chakachengetwa mukati mematrix ? yapfuura positi W G R Kuuya kumba Pese patakawana nzira ipfupi pfupi, taive tichivandudza sero rinoenderana rematrix nehuwandu hwazvino hwe . Nepo pekutanga, chiitiko ichi chingaite sechisinganzwisisike chine chirevo chakareruka - isu taichengeta vertex, kubva kwatakasvika kwainosvika vertex: (pano tave kusvika zvakananga kubva ). R k i ⭢ k ⭢ j j k Iyi nguva yakakosha. Nekuti kuziva vertex yatakabva kunotibvumira kuvaka patsva nzira nekudzokera kumashure (selobster) kubva kuvertex (iyo "kusvika") kuenda kuvertex ("kubva"). j i Heino tsananguro yezvinyorwa zve algorithm yekuvakazve nzira kubva ku kuenda : i j Gadzirira isina chinhu dynamic array . X Tanga nekuverenga kukosha kubva muchitokisi . z R[i,j] Kana ari , ipapo nzira kubva kuna kuenda inowanikwa uye tinofanira kuenderera kunhanho #7. z NO_EDGE i j Gadzirira kune inoshanduka-shanduka . z X Verenga kukosha kwesero mu . R[i,z] z Dzokorora nhanho #3, #4, uye #5 kusvika mamiriro ekubuda mu#3 asvikwa. Gadzirira kuna X. i Wedzera kuna . j X Ikozvino dynamic array ine nzira kubva kuenda . X i j Ndokumbira utarise, iyo algorithm iri pamusoro inoshanda chete kune iripo nzira. Iyo zvakare haina kukwana kubva pakuita kwekutarisa uye zvechokwadi inogona kugadzirwa. Nekudaro, muchikamu cheiyo positi, inotsanangurwa zvakananga nenzira yekuita kuti zvive nyore kunzwisisa uye kubereka pabepa. - Chinyorwa chemunyori Mune pseudo-code, inotaridzika zvakanyanya nyore: algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm Ngatiiedzei pagirafu yedu uye tivakezve nzira kubva kune vertex kuenda kuvertex (ona Mufananidzo 8). G 0 4 Heino tsananguro yezvinyorwa zvemufananidzo uri pamusoro: Tinotanga nekuverenga kukosha kubva , izvo zvinoguma . Zvinoenderana nealgorithm, izvi zvinoreva kuti nzira inoenda kune vertex kubva vertex (inoratidzwa muBLUE). R[0,4] 3 4 3 Nekuti kukosha kweR hakusi , tinoenderera mberi nekuverenga kukosha kweR izvo zvinoguma (inoratidzwa muGREEN). R[0,4] NO_EDGE R[0,3] 2 Zvekare, nekuti kukosha kweR hakusi , tinoenderera mberi nekuverenga kukosha kweR inoguma (inoratidzwa muRED). R[0,3] NO_EDGE R[0,2] 1 Pakupedzisira, tinoverenga kukosha kweR , izvo zvinoguma kukosha, zvinoreva, hapasisina vertexes kunze uye iyo inobatsira munzira. Nokudaro, nzira inoguma ndeiyi: iyo kana iwe ukatarisa girafu inonyatsoenderana nenzira ipfupi kubva kuvertex kusvika kune vertex . R[0,1] NO_EDGE 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 Muverengi anofunga angabvunza kuti: Tingave sei nechokwadi chekuti data rese ratinoverenga kubva kumatrix nderomunzira imwechete? R - Muverengi anofunga Mubvunzo wakanaka kwazvo. Isu tine chokwadi nekuti isu tinovandudza matrix nehutsva hutsva patinogadzirisa iyo pfupi nzira kukosha mune matrix Saka mukupedzisira, mutsara wega wega we matrix une data rine chekuita nemakwara mapfupi. Kwete, kwete zvishoma. R W R Zvino, isu tapedza nedzidziso, inguva yekushandisa. Kuitwa muC# Mune iyo , kunze kwekuita iyo yekutanga vhezheni yeFloyd-Warshall algorithm, isu takabatanidzawo akasiyana optimizations: rutsigiro rwemagirafu mashoma, parallelism, uye vectorization, uye pakupedzisira, isu takabatanidza ese. yapfuura positi Hapana chikonzero chekudzokorora zvese izvi nhasi. Nekudaro, ini ndoda kukuratidza nzira yekubatanidza nzira yekuyeuka mune yepakutanga uye vectorized (nerutsigiro rwe sparse magirafu) shanduro yegorgorithm. Kubatanidzwa Mukutanga Algorithm Zvingave zvakaoma kutenda asi kubatanidza nzira yemusoro mushanduro yekutanga yealgorithms, zvese zvatinofanira kuita ndezvekuti: Wedzera siginicha yebasa kuti ubatanidze matrix separamita yakaparadzana - . R int[] routes Sevha k pese panochinjwa nzira ipfupi (mitsara: 2 ne14). routes Ndizvozvo. Mutsetse mumwe nehafu wekodhi: public void BaselineWithRoutes( int[] matrix, int[] routes, 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; routes[i * sz + j] = k; } } } } } Kubatanidzwa muVectorized Algorithm Kubatanidzwa mune vectorized (nerutsigiro rwemagirafu mashoma) vhezheni inotora imwe nhamburiko kuti ipedze, zvisinei, nhanho dzepfungwa dzakafanana: Wedzera siginicha yebasa kuti ubatanidze matrix separamita yakaparadzana - . R int[] routes Pane imwe neimwe iteration, tanga vector itsva ye values (mutsara: 6). k Chengetedza values vector pese painoshandurwa nzira pfupi (mitsetse: 31-32). k routes Gadziridza iyo isiri-vectorized chikamu chegorgorithm nenzira imwechete sezvatakagadzirisa iyo yekutanga algorithm (mutsara: 41). public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.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); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, 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; routes[i * sz + j] = k; } } } } } Chiyeuchidzo chidiki - operation inodzosa vhekita itsva apo ma values akaenzana nediki patwu twunhu twakaenzana twemapput vectors, kureva, kana kukosha kwe vector kwakaenzana ne , ipapo oparesheni inosarudza kukosha kubva , kana zvisina kudaro, inosarudza kukosha kubva . Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - Chinyorwa chemunyori Benchmarking Kuunganidza ruzivo rwemakwara kunoita sekwakakwana nekuti… zvakanaka nei? Kunyanya kana zviri nyore kubatanidza mune iripo algorithms. Nekudaro, ngationei kuti inoshanda sei kuibatanidza nekukasira. Heano maviri seti emabhenji: ane uye pasina (ese ari maviri epa epakutanga uye vectorized shanduro yegorgorithm). Mabhenjimaki ese akaitwa v0.13.1 (.NET 6.0.4 x64) pamuchina une Intel Core i5-6200U CPU 2.30GHz (Skylake) processor uye inoshanda Windows 10. neBenchmarkDotNet Zvese zviedzo zvakaitwa pane yakafanotsanangurwa seti yemagirafu akashandiswa mune : 300, 600, 1200, 2400, uye 4800 vertexes. yapfuura positi Iyo kodhi kodhi uye yekuyedza magirafu anowanikwa mune repository paGitHub. Iwo ekuyedza magirafu anogona kuwanikwa muData dhairekitori. Data/Sparse-Graphs.zip Ese mabhenji mutsamba ino anoiswa muAPSP02.cs faira. Pazasi pane mibairo yekumisikidza apo nzira dzinoenderana neshanduro yekutanga yegorgorithm uye uye nzira dzinoenderana nevectorized (nerutsigiro rwemagirafu mashoma) yegorgorithm. Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes Nzira Size Zvinoreva (ms) kukanganisa (ms) StdDev (ms) Baseline 300 40.233 0.0572 0.0477 BaselineWithRoutes 300 40.349 0.1284 0.1201 SpartialVectorOptimisations 300 4.472 0.0168 0.0140 SpartialVectorOptimisationsWithRoutes 300 4.517 0.0218 0.0193 Baseline 600 324.637 5.6161 4.6897 BaselineWithRoutes 600 321.173 1.4339 1.2711 SpartialVectorOptimisations 600 32.133 0.2151 0.1679 SpartialVectorOptimisationsWithRoutes 600 34.646 0.1286 0.1073 Baseline 1200 2,656.024 6.9640 5.8153 BaselineWithRoutes 1200 2,657.883 8.8814 7.4164 SpartialVectorOptimisations 1200 361.435 2.5877 2.2940 SpartialVectorOptimisationsWithRoutes 1200 381.625 3.6975 3.2777 Baseline 2400 21,059.519 38.2291 33.8891 BaselineWithRoutes 2400 20,954.852 56.4719 50.0609 SpartialVectorOptimisations 2400 3,029.488 12.1528 11.3677 SpartialVectorOptimisationsWithRoutes 2400 3,079.006 8.6125 7.1918 Baseline 4800 164,869.803 547.6675 427.5828 BaselineWithRoutes 4800 184,305. 980 210.9535 164.6986 SpartialVectorOptimisations 4800 21,882.379 200.2820 177.5448 SpartialVectorOptimisationsWithRoutes 4800 21,004.612 79.8752 70.8073 Benchmark zvawanikwa hazvisi nyore kududzira. Kana iwe ukanyatsotarisisa, iwe unowana musanganiswa apo nzira yekuunganidza yakanyatsoita kuti algorithm imhanye nekukurumidza kana pasina yakakosha mhedzisiro. Izvi zvinotaridzika zvakanyanya kuvhiringidza (uye kana zviri izvo - ndinokurayira zvakasimba kuti uteerere uku naDenis naAndrey kuti unzwisise zviri nani zvinhu zvinonyengera zvinogona kukanganisa zviyero). Chandinonyanya kutora pano ndechekuti "kuvhiringa" maitiro anokonzerwa nehukuru hweCPU cache kuita (nekuti magirafu haana kukura zvakakwana kugutsa cache). Zvishoma, dzidziso iyi yakavakirwa pa " " sampuli apo isu tinogona kuona kuderera kukuru pane yakakura girafu. Zvisinei, handina kuzviongorora. kuratidzwa Bakhvalov Akinshin bold Kazhinji, mucherechedzo unoratidza kuti kana tisiri kutaura nezve yakanyanyisa-inoshanda mamiriro uye magirafu mahombe, zvakanaka kubatanidza nzira yekurangarira mune ese maalgorithms nekukasira (asi ramba uchifunga, ichapeta ndangariro kushandiswa nekuti isu tinoda govera matrices maviri uye pane imwe). W R Chinhu chega chasara kuita kweiyo nzira yekuvakazve algorithm. Kuitwa kweRoute Rebuild Algorithm Kuitwa kwenzira yekuvakazve maalgorithms muC# kwakatwasuka uye kunenge kwakanyatso kuratidza yakamboratidzwa pseudo-code (tinoshandisa kumiririra dynamic array): LinkedList<T> public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; } Iyo algorithm iri pamusoro haina kukwana uye zvechokwadi inogona kuvandudzwa. Iko kunatsiridza kuri nyore kwatinogona kuita ndeye kugovera dhizaini yehukuru hwe uye kuizadza mune reverse order: sz public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); } Kunyange iyi "optimization" ichidzikisa huwandu hwekugoverwa kune imwe, hazviiti kuti algorithm "ikurumidze" kana "kugovera ndangariro shoma" pane yapfuura. Pfungwa iri pano ndeyokuti kana tichida kuva negwara rakarayirwa kubva kusvika , isu nguva dzose tichafanira "kudzosera" data yatinotora kubva kumatrix , uye hapana nzira yekupukunyuka nayo. i j R Asi kana tikakwanisa kupa data mune reverse order, saka tinogona kushandisa LINQ uye kudzivirira chero kugoverwa kusingakoshi: public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; } Panogona kuve nemimwe misiyano yakawanda yekuti kodhi iyi inogona "kushandurwa" kana "kuvandudzwa." Nguva yakakosha pano ndeyekuyeuka - chero "shanduko" ine yakaderera maererano nendangariro kana CPU kutenderera. Inzwa wakasununguka kuedza! Mikana inenge isingagumi! Unogona kuwana mashandisirwo enzira dzese algorithms paGitHub muRoutes.cs faira. Mhedziso Mune ino positi, takave nekunyura kwakadzama mune dzidziso kuseri kweiyo Floyd-Warshall algorithm uye takaiwedzera nemukana wekuyeuka mapfupi nzira "makwara." Ipapo takagadziridza C # maitirwo (yekutanga uye vectorized) kubva kune . Pakupedzisira, takashandisa shanduro shomanana dzegorgorithm kuti tivakezve "nzira". yapfuura positi Takadzokorora kakawanda, asi panguva imwe chete, ndinovimba wawana chimwe chinhu chitsva uye chinonakidza mune ino. Uku hakusi kupera kwedambudziko renzira pfupi-peiri. Aya angori mavambo. Ndinovimba wakanakidzwa nekuverenga, uye tozoonana nguva inotevera!
