Ҳар яки мо дар як рӯз чанд маротиба масъалаи “ ”-ро ҳал мекунем. Албатта нохост. Мо онро дар роҳи кор ё ҳангоми дидани Интернет ё ҳангоми ҷойгир кардани чизҳои худ дар мизи корӣ ҳал мекунем. роҳи кӯтоҳтарин Садо каме… аз ҳад зиёд? Биёед бифаҳмем. Тасаввур кунед, ки шумо қарор додед, ки бо дӯстон вохӯред, хуб ... биёед дар қаҳвахона бигӯед. Пеш аз ҳама, ба шумо лозим аст, ки як масир (ё роҳ) ба қаҳвахона пайдо кунед, бинобар ин шумо ба ҷустуҷӯи нақлиёти ҷамъиятии дастрас (агар шумо пиёда бошед) ё хатсайрҳо ва кӯчаҳо (агар шумо ронандагӣ бошед) оғоз кунед. Шумо масирро аз макони ҳозираи худ то қаҳвахона меҷӯед, аммо на "ягон масир" - кӯтоҳтарин ё зудтарин. Инак як мисоли дигар, ки мисли мисоли қаблӣ чандон равшан нест. Ҳангоми кор шумо қарор медиҳед, ки аз кӯчаи канори "бури кӯтоҳ" гузаред, зеро ... ин "бури кӯтоҳ" аст ва рафтан ба ин роҳ "тезтар" аст. Аммо шумо аз куҷо медонистед, ки ин "бури кӯтоҳ" тезтар аст? Дар асоси таҷрибаи шахсӣ шумо як масъалаи "кӯтоҳтарин роҳ" -ро ҳал кардед ва масиреро интихоб кардед, ки аз кӯчаи канор мегузарад. Дар ҳарду мисол, масири "кӯтоҳтарин" дар масофа ё вақт муайян карда мешавад, ки барои аз як ҷо ба ҷои дигар рафтан лозим аст. Намунаҳои сайёҳӣ барномаҳои хеле табиии ва махсусан мушкилоти "роҳи кӯтоҳтарин" мебошанд. Бо вуҷуди ин, дар бораи намунаи ба тартиб даровардани чизҳо дар рӯи миз чӣ гуфтан мумкин аст? Дар ин ҳолат "кӯтоҳтарин" метавонад як миқдор ё мураккабии амалҳоеро нишон диҳад, ки шумо бояд барои ба даст овардани варақи коғаз иҷро кунед: мизи кушода, папкаи кушода, варақи коғазро гиред ва варақи коғазро рост аз мизи корӣ гиред. . назарияи графикӣ Ҳамаи мисолҳои дар боло овардашуда мушкилоти дарёфти роҳи кӯтоҳтарин байни ду қуллаи графикро ифода мекунанд (маршрут ё роҳи байни ду ҷой, як қатор амалҳо ё мураккабии гирифтани варақ аз ин ё он ҷо). Ин синфи мушкилоти роҳи кӯтоҳтарин номида мешавад ва алгоритми асосии ҳалли ин масъалаҳо мебошад, ки мураккабии ҳисоббарории дорад. SSSP (Single Source Shortest Path) алгоритми Dijkstra O(n^2) Аммо, баъзан мо бояд ҳамаи роҳҳои кӯтоҳтаринро дар байни ҳама қуллаҳо пайдо кунем. Мисоли зеринро дида бароед: шумо барои шумо харитаи ҳаракатҳои мунтазами байни , ва эҷод мекунед. Дар ин сенария шумо бо 6 масир хотима хоҳед ёфт: , , , , ва (масалан, масирҳои баръакс аз сабаби роҳҳои яктарафа метавонанд гуногун бошанд) . хона кор театр work ⭢ home home ⭢ work work ⭢ theatre theatre ⭢ work home ⭢ theatre theatre ⭢ home Илова кардани ҷои бештар ба харита боиси афзоиши назарраси комбинатсияҳо мегардад - мувофиқи формулаи онро метавон чунин ҳисоб кард: ивазкунии n комбинаторика 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) Ин ба мо 12 хатсайр барои 4 ҷой ва 90 хатсайр барои 10 ҷой медиҳад (ки таъсирбахш аст). Эзоҳ… ин бе назардошти нуқтаҳои мобайнии байни ҷойҳо аст, яъне барои аз хона ба кор рафтан шумо бояд 4 кӯчаро убур кунед, аз дарё сайр кунед ва аз купрук гузаред. Агар мо тасаввур кунем, баъзе масирҳо метавонанд нуқтаҳои мобайнии умумӣ дошта бошанд… хуб… дар натиҷа мо як графикаи хеле калон бо қуллаҳои зиёд дорем, ки дар он ҳар як қулла ё ҷой ё нуқтаи мобайнии муҳимро ифода мекунад. Синфи масъалаҳо, ки дар он мо бояд ҳамаи роҳҳои кӯтоҳтарини байни ҳамаи ҷуфтҳои қуллаҳои графикро пайдо кунем, номида мешавад ва алгоритми асосии ҳалли ин масъалаҳо мебошад, ки дорои мебошад. мураккабии хисоббарорй. APSP (All Pairs Shortest Paths) алгоритми Флойд-Варшалл O(n^3) O(n^3) Ва ин алгоритмест, ки мо имрӯз амалӣ хоҳем кард 🙂 Алгоритми Флойд-Уоршалл Алгоритми Флойд-Уоршалл ҳамаи роҳҳои кӯтоҳтаринро байни ҳар як ҷуфт қуллаҳои графикӣ пайдо мекунад. Алгоритмҳоро Роберт Флойд дар [1] нашр кардааст (барои тафсилоти бештар ба бахши “Истифодабарандагон” нигаред). Дар ҳамон сол, Питер Ингерман дар [2] татбиқи муосири алгоритмро дар шакли се ҳалқаҳои гузошташуда тавсиф кард: 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 Агар шумо ҳеҷ гоҳ барои кор бо графике, ки дар шакли матритса нишон дода шудааст, тағир наёфта бошед, пас фаҳмидани он ки алгоритми дар боло зикршуда чӣ кор мекунад, душвор буда метавонад. Пас, барои боварӣ ҳосил кардан, ки мо дар як саҳифа ҳастем, биёед бубинем, ки чӣ гуна графикро дар шакли матритса муаррифӣ кардан мумкин аст ва чаро чунин муаррифӣ барои ҳалли масъалаи роҳи кӯтоҳтарин муфид аст. Дар расми зер графики 5 қулла нишон дода шудааст. Дар тарафи чап, график дар шакли визуалӣ оварда шудааст, ки аз доираҳо ва тирҳо сохта шудааст, ки дар он ҳар як доира қулла ва тирча канори самтро ифода мекунад. Рақами дохили доира ба рақами қулла ва рақами болои канор ба вазни канор мувофиқат мекунад. Дар тарафи рост, ҳамон график дар шакли матритсаи вазн оварда шудааст. Матритсаи вазн як шакли мебошад, ки дар он ҳар як ячейкаи матритса дорои "вазн" - масофаи байни қуллаи (сатр) ва қуллаи (сутун) мебошад. Матритсаи вазн маълумотро дар бораи "роҳ" байни қуллаҳо (рӯйхати қуллаҳое, ки тавассути онҳо шумо аз то ба даст меоред) дар бар намегирад – танҳо вазн (масофа) байни ин қуллаҳо. мутамарказ ва вазншудаи матритсаи ҳамсоя i j i j Дар матритсаи вазн мо мебинем, ки арзишҳои чашмакҳо ба вазнҳои байни қуллаҳои баробаранд. Аз ин рӯ, агар мо роҳҳоро аз қуллаи (сатри ) тафтиш кунем, мебинем, ки ... танҳо як роҳ вуҷуд дорад - аз то . Аммо, дар тасвири визуалӣ мо метавонем роҳҳоро аз қуллаи то қуллаҳои ва (тавассути қуллаи ) равшан бубинем. Сабаби ин оддӣ аст - дар ҳолати аввал, матритсаи вазн танҳо масофаи байни қуллаҳои ҳамсояро дар бар мегирад. Аммо, танҳо ин маълумот барои боқимонда кофӣ аст. ҳамсоя 0 0 0 1 0 2 3 1 пайдо кардани Биёед бубинем, ки он чӣ гуна кор мекунад. Ба чашмаки диққат диҳед. Қимати он нишон медиҳад, ки роҳ аз қуллаи то қуллаи бо вазни баробар ба мавҷуд аст (дар кӯтоҳ мо метавонем чунин нависед: ). Бо ин дониш, мо ҳоло метавонем ҳамаи ячейкаҳои сатри скан кунем (ки ҳамаи вазнҳои ҳамаи роҳҳоро аз қуллаи дар бар мегирад) ва бандари ин маълумотро ба сатри интиқол дода, вазнро ба зиёд кунем (қимати ). W[0, 1] 0 1 1 0 ⭢ 1: 1 1 1 0 1 W[0, 1] Бо истифода аз ҳамон қадамҳо мо метавонем роҳҳоро аз қуллаи тавассути қуллаҳои дигар пайдо кунем. Ҳангоми ҷустуҷӯ, шояд рӯй диҳад, ки зиёда аз як роҳе вуҷуд дорад, ки ба як қулла мебарад ва муҳимтар аз он, вазнҳои ин роҳҳо метавонанд гуногун бошанд. Намунаи чунин вазъият дар расми зер тасвир шудааст, ки ҷустуҷӯ аз қуллаи то қуллаи боз як роҳи дигарро ба қуллаи -и вазни камтар ошкор кард. 0 0 2 3 Мо ду роҳ дорем: роҳи аслӣ – ва роҳи наве, ки мо ҳоло кашф кардем – (дар хотир доред, ки матритсаи вазн роҳҳоро дар бар намегирад, бинобар ин мо намедонем, ки кадоме аз онҳост. қуллаҳо ба роҳи аслӣ дохил карда шудаанд). Ин лаҳзаест, ки мо тасмим мегирем, ки кӯтоҳтаринро нигоҳ дорем ва ба чашмаки нависед. 0 ⭢ 3: 4 0 ⭢ 2 ⭢ 3: 3 3 W[0, 3] Чунин ба назар мерасад, ки мо навтарин роҳи кӯтоҳтаринамонро пайдо кардаем! Қадамҳое, ки мо дидаем, моҳияти алгоритми Флойд-Уоршалл мебошанд. Бори дигар ба псевдокоди алгоритм нигаред: 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 Давраи аз ҳама берунӣ дар болои ҳамаи қуллаҳои график такрор мешавад ва дар ҳар як итератсия, тағирёбандаи қуллаеро ифода мекунад . Давраи дохилӣ on инчунин дар болои ҳамаи қуллаҳои график такрор мешавад ва дар ҳар як такрор, қуллаеро нишон медиҳад . Ва ниҳоят, як давраи ботинӣ дар болои ҳамаи қуллаҳои график ва дар ҳар як итератсия такрор мешавад, қуллаеро нишон медиҳад Дар якҷоягӣ он ба мо чунин медиҳад: дар ҳар як такрори мо роҳҳоро аз ҳама қуллаҳои ба ҳамаи қуллаҳои тавассути қуллаи ҷустуҷӯ мекунем. Дар дохили давра мо роҳи (нишондодашуда бо ) бо роҳи (бо маблағи ва ифода карда мешавад) муқоиса мекунем ва кӯтоҳтаринро менависем. як баргашт ба . for k k , ки мо роҳҳои ҷустуҷӯи тавассути for i i , ки мо роҳҳоро аз for j j , ки мо роҳро ҷустуҷӯ мекунем. k i j k i ⭢ j W[i, j] i ⭢ k ⭢ j W[I, k] W[k, j] W[i, j] Акнун, вақте ки мо механикаро мефаҳмем, вақти татбиқи алгоритм аст. Татбиқи асосӣ Рамзи сарчашма ва графикҳои таҷрибавӣ дар GitHub дастрасанд. Графикҳои таҷрибавиро дар феҳристи пайдо кардан мумкин аст. Ҳама нишондиҳандаҳои ин мақола дар файли амалӣ карда мешаванд. анбори Data/Sparse-Graphs.zip APSP01.cs Пеш аз ворид шудан ба татбиқ, мо бояд якчанд лаҳзаҳои техникиро равшан кунем: Ҳама татбиқҳо бо матритсаи вазн, ки дар шакли массиви хатӣ муаррифӣ шудаанд, кор мекунанд. Ҳама татбиқҳо арифметикаи бутунро истифода мебаранд. Набудани роҳ дар байни қуллаҳо бо вазни махсуси доимӣ ифода карда мешавад: . NO_EDGE = (int.MaxValue / 2) - 1 Акнун биёед бифаҳмем, ки чаро ин аст. Вақте ки мо дар бораи матритсаҳо сухан меронем, мо ҳуҷайраҳоро аз рӯи “сатрҳо” ва “сутунҳо” муайян мекунем. Аз ин рӯ, тасаввур кардани матритса дар шакли «мураббаъ» ё «росткунҷа» табиист (Расми 4а). Дар бораи №1. Аммо, ин маънои онро надорад, ки мо бояд матритсаро дар шакли массивҳо муаррифӣ кунем (Расми 4б) то ба тасаввуроти худ пайваст шавем. Ба ҷои ин, мо метавонем матритсаро дар шакли массиви хатӣ муаррифӣ кунем (Расми 4c), ки индекси ҳар як чашмак бо формулаи зерин ҳисоб карда мешавад: i = row * row_size + col; // where row - cell row index, // col - cell column index, // row_size - number of cells in a row. Массиви хаттии матритсаи вазн иҷрои самараноки алгоритми Флойд-Уоршалл мебошад. Сабаби ин содда нест ва шарҳи муфассал сазовори як мақолаи алоҳида ... ё чанд паём аст. Бо вуҷуди ин, айни замон бояд қайд кард, ки чунин муаррифӣ ба таври назаррас беҳтар мекунад, ки дар асл ба кори алгоритм таъсири калон мерасонад. шарти пешакии ҷойгиршавии маълумотро Дар ин ҷо ман аз шумо хоҳиш мекунам, ки ба ман бовар кунед ва танҳо ин маълумотро ба назар гиред, аммо дар айни замон ман тавсия медиҳам, ки каме вақт сарф кунед ва саволро омӯзед ва дар омади гап - ба одамон дар Интернет бовар накунед . - Эзоҳҳои муаллиф Агар шумо ба алгоритми псевдокоди бодиққат назар андозед, шумо ягон санҷиши марбут ба мавҷудияти роҳ байни ду қулларо намеёбед. Ба ҷои ин, псевдокод танҳо функсияи ро истифода мебарад. Сабаб оддӣ аст - дар аввал, агар байни қуллаҳо роҳ мавҷуд набошад, арзиши ячейка ба муқаррар карда мешавад ва дар ҳама забонҳо, ба истиснои JavaScript, ҳама арзишҳо аз камтаранд. Дар сурати мавҷуд будани ададҳо, он метавонад васвасаи истифодаи ҳамчун арзиши "ҳеҷ роҳ" бошад. Аммо ин боиси зиёд шудани ададҳои бутун мегардад, дар ҳолатҳое, ки қиматҳои ҳам ва роҳҳо ба баробар мешаванд. Аз ин рӯ, мо арзишеро истифода мебарем, ки як камтар аз нисфи аст. Дар бораи № 2. min() infinity infinity int.MaxValue i ⭢ k k ⭢ j int.MaxValue int.MaxValue Эй! Аммо чаро мо пеш аз анҷом додани ҳисобҳо танҳо тафтиш карда наметавонем, ки оё роҳ мавҷуд аст ё не. Масалан, бо муқоисаи роҳҳо ҳарду ба 0 (агар мо сифрро ҳамчун арзиши “роҳ нест” гирем). - Хонандаи боандеша Ин дар ҳақиқат имконпазир аст, аммо мутаассифона он ба ҷазои назарраси иҷроиш оварда мерасонад. Хулоса, CPU омори натиҷаҳои арзёбии филиалҳоро нигоҳ медорад, масалан. вақте ки баъзе аз изҳороти ё арзёбӣ мешаванд. Он ин оморро барои иҷро кардани рамзи "шохаи аз ҷиҳати оморӣ пешбинишуда" пеш аз баҳодиҳии воқеӣ истифода мебарад (ин номида мешавад) ва аз ин рӯ кодро самараноктар иҷро мекунад. Аммо, вақте ки пешгӯии CPU нодуруст аст, он дар муқоиса бо пешгӯии дуруст ва иҷрои бечунучаро талафоти назаррасро ба бор меорад, зеро CPU бояд шохаи дурустро қатъ ва ҳисоб кунад. if true false if иҷроиши тахминӣ Азбаски дар ҳар як такрори мо як қисми зиёди матритсаи вазнро навсозӣ мекунем, омори филиали CPU бефоида мешавад, зеро намунаи рамз вуҷуд надорад, ҳама шохаҳо танҳо ба маълумот асос ёфтаанд. Ҳамин тавр, чунин санҷиш боиси миқдори зиёди мегардад. k пешгӯиҳои нодурусти соҳа Дар ин ҷо ман инчунин аз шумо хоҳиш мекунам, ки ба ман бовар кунед (ҳоло) ва сипас барои омӯзиши мавзӯъ каме вақт ҷудо кунед. Уҳ, ба назар чунин мерасад, ки мо қисми назариявиро анҷом додем - биёед алгоритмро амалӣ кунем (мо ин татбиқро ҳамчун нишон медиҳем): 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; } } } } } Рамзи дар боло зикршуда қариб як нусхаи псевдокоди қаблан зикршуда бо истиснои ягона аст - ба ҷои мо навсозии ячейка танҳо ҳангоми зарурат истифода мебарем. Math.Min() if Эй! Як дақиқа сабр кунед, магар шумо набудед, ки дар бораи он ки чаро дар ин ҷо if's хуб нест ва чанд сатр баъд мо худамон ифро муаррифӣ мекунем? - Хонандаи боандеша Сабаб оддӣ аст. Дар лаҳзаи навиштани JIT рамзи тақрибан баробарро ҳам барои татбиқи ва мебарорад. Шумо метавонед онро ба таври муфассал дар тафтиш кунед, аммо дар ин ҷо порчаҳои сохторҳои асосии ҳалқа мавҷуданд: 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 Шумо метавонед бубинед, новобаста аз он ки мо ё истифода мебарем, то ҳол санҷиши шартӣ мавҷуд аст. Аммо, дар мавҷуд набудани навиштани нолозим. if Math.Min if Ҳоло, вақте ки мо татбиқро анҷом додем, вақти он расидааст, ки кодро иҷро кунем ва бубинем, ки он чӣ қадар тез аст?! Шумо метавонед дурустии кодро тавассути гузаронидани санҷишҳо дар тафтиш кунед. анбор Ман (версияи 0.12.1) -ро барои санҷиши код истифода мекунам. Ҳама графикҳое, ки дар нишондиҳандаҳо истифода мешаванд 300, 600, 1200, 2400 ва 4800. Миқдори кунҷҳо дар графикҳо тақрибан 80% аз ҳадди имконпазирро ташкил медиҳад, ки барои графикҳои мутаҳаррикшуда ва даврӣ чунин ҳисоб кардан мумкин аст: Benchmark.NET , равона карда шудаанд, графикҳои асиклии var max = v * (v - 1)) / 2; // where v - is a number of vertexes in a graph. Биёед санг кунем! Инҳоянд натиҷаҳои санҷишҳои дар компютери ман иҷрошуда (Windows 10.0.19042, Intel Core i7-7700 CPU 3.60Ghz (Kaby Lake) / 8 протсессори мантиқӣ / 4 ядро): Усул Андоза Маънои Хатогӣ StdDev Асосӣ 300 27,525 мс 0,1937 мс 0,1617 мс Асосӣ 600 217,897 мс 1,6415 мс 1,5355 мс Асосӣ 1200 1,763,335 мс 7,4561 мс 6,2262 мс Асосӣ 2400 14,533,335 мс 63,3518 мс 52,9016 мс Асосӣ 4800 119,768,219 мс 181,5514 мс 160,9406 мс Аз натиҷаҳое, ки мо мебинем, вақти ҳисобкунӣ дар муқоиса бо андозаи график хеле зиёд мешавад - барои графики 300 қуллаи он 27 миллисония, барои графики 2400 қуллаи - 14,5 сония ва барои графики 4800 - 119 сония, ки ! қариб 2 дақиқа Агар ба коди алгоритм нигоҳ карда тасаввур кардан душвор бошад, мо барои суръат бахшидан ба ҳисобҳо коре карда метавонем… зеро хуб… СЕ ҳалқаҳо мавҷуданд, ҳамагӣ СЕ ҳалқа. Аммо, чунон ки одатан рӯй медиҳад - имкониятҳо дар тафсилот пинҳон мешаванд 🙂 Шумо маълумотро медонед - графикҳои пароканда Алгоритми Флойд-Уоршалл як алгоритми асосӣ барои ҳалли мушкилоти роҳи кӯтоҳтарин барои ҳама ҷуфтҳо мебошад, хусусан вақте ки сухан дар бораи графикҳои ё меравад (зеро алгоритм роҳҳоро байни ҳамаи ҷуфтҳои қуллаҳоро ҷустуҷӯ мекунад). зич пурра Бо вуҷуди ин, мо дар таҷрибаҳои худ графикҳои истифода мебарем, ки хусусияти аҷибе доранд – агар аз қуллаи то қуллаи роҳ мавҷуд бошад, пас аз қуллаи то қуллаи роҳ вуҷуд надорад. Барои мо, ин маънои онро дорад, ки бисёр қуллаҳои ҳамсоя вуҷуд доранд, ки агар аз то роҳ набошад, мо метавонем онро гузаронем (мо ин татбиқро ҳамчун ишора мекунем). мутаҳаррикро 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; } } } } } Инҳоянд натиҷаҳои татбиқи қаблӣ ( ) ва ҷорӣ ( ) дар як маҷмӯи графикҳо (натиҷаҳои зудтарин бо нишон дода шудаанд): Baseline SpartialOptimisation ғафс Усул Андоза Маънои Хатогӣ StdDev Таносуб Асосӣ 300 27,525 мс 0,1937 мс 0,1617 мс 1.00 Optimization Spartial 300 12,399 мс 0,0943 мс 0,0882 мс 0,45 Асосӣ 600 217,897 мс 1,6415 мс 1,5355 мс 1.00 Optimization Spartial 600 99,122 мс 0,8230 мс 0,7698 мс 0,45 Асосӣ 1200 1,763,335 мс 7,4561 мс 6,2262 мс 1.00 Optimization Spartial 1200 766,675 мс 6,1147 мс 5,7197 мс 0,43 Асосӣ 2400 14,533,335 мс 63,3518 мс 52,9016 мс 1.00 Optimization Spartial 2400 6,507,878 мс 28,2317 мс 26,4079 мс 0,45 Асосӣ 4800 119,768,219 мс 181,5514 мс 160,9406 мс 1.00 Optimization Spartial 4800 55,590,374 мс 414,6051 мс 387,8218 мс 0,46 Хеле таъсирбахш! Мо вақти ҳисобкуниро дар як ним кам кардем! Албатта, график чӣ қадар зичтар бошад, суръат ҳамон қадар камтар мешавад. Аммо, ин яке аз оптимизатсияҳоест, ки агар шумо пешакӣ донед, ки шумо бо кадом синфи маълумот кор кардан мехоҳед, муфид аст. Оё мо метавонем бештар кор кунем? 🙂 Таҷҳизоти худро бидонед - параллелизм Компютери ман бо протсессори бо 8 протсессори мантиқӣ ( ) ё 4 ядро бо технологияи муҷаҳҳаз шудааст. Доштани зиёда аз як ядро ба монанди доштани "дастҳои эҳтиётии" бештар аст, ки мо метавонем онҳоро ба кор гузорем. Пас, биёед бубинем, ки кадом қисми корро байни коргарони сершумор ба таври муассир тақсим кардан мумкин аст ва сипас онро параллел созед. Inter Core i7-7700 CPU 3.60GHz (Kaby Lake) HW Hyper-Threading Доиравҳо ҳамеша номзади возеҳтарин барои параллелизатсия мебошанд, зеро дар аксари мавридҳо такрорҳо мустақиланд ва метавонанд ҳамзамон иҷро шаванд. Дар алгоритм, мо се ҳалқа дорем, ки мо бояд онҳоро таҳлил кунем ва бубинем, ки оё ягон вобастагӣ вуҷуд дорад, ки моро ба параллелизатсияи онҳо бозмедоранд. Биёед аз оғоз кунем. Дар ҳар як ҳалқаи такрорӣ роҳҳоро аз ҳар як қулла ба ҳар як қулла тавассути қуллаи ҳисоб мекунад. Роҳҳои нав ва навшуда дар матритсаи вазн нигоҳ дошта мешаванд. Ба такрорҳо нигоҳ карда, шумо метавонед мушоҳида кунед - онҳо метавонанд бо ҳама гуна тартиб иҷро карда шаванд: 0, 1, 2, 3 ё 3, 1, 2, 0 бидуни таъсир ба натиҷа. Бо вуҷуди ин, онҳо бояд ба таври пайдарпай иҷро карда шаванд, вагарна баъзе аз такрорҳо наметавонанд роҳҳои нав ё навшударо истифода баранд, зеро онҳо ҳанӯз дар матритсаи вазн навишта намешаванд. Чунин номутобиқатӣ бешубҳа натиҷаҳоро хароб хоҳад кард. Пас, мо бояд ҷустуҷӯро давом диҳем. for of k k Номзади навбатӣ loop аст. Дар ҳар як даври такрорӣ роҳро аз қуллаи то қуллаи (ячейка: ), роҳро аз қуллаи то қуллаи (ячейка: ]) мехонад ва сипас тафтиш мекунад, ки роҳи маълум аз ба (ячейка: ) аз роҳ кӯтоҳтар аст (маблағи: + ). Агар шумо ба намунаи дастрасӣ бодиққат назар кунед, шумо метавонед пайхас кунед - дар ҳар як итератсия цикли маълумот аз сатр ва навсозии сатрро мехонад, ки аслан маънои онро дорад - такрорҳо мустақиланд ва на танҳо бо ҳама гуна тартиб, балки дар баробари ҳам иҷро кардан мумкин аст! 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] i k i Ин умедбахш менамояд, аз ин рӯ биёед онро амалӣ кунем (мо ин татбиқро ҳамчун ишора мекунем). SpartialParallelOptimisations давриро низ мувозӣ кардан мумкин аст. Аммо, параллелизатсияи давраи ботинӣ дар ин ҳолат хеле бесамар аст. Шумо метавонед онро худатон бо ворид кардани чанд тағйироти оддӣ дар тафтиш кунед. for of j коди манбаъ - Эзоҳҳои муаллиф 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; } } }); } } Инҳоянд натиҷаҳои татбиқи , ва дар як маҷмӯи графикҳо (параллелизатсия бо истифода аз синфи анҷом дода мешавад): Baseline SpartialOptimisation SpartialParallelOptimisations Parallel Усул Андоза Маънои Хатогӣ StdDev Таносуб Асосӣ 300 27,525 мс 0,1937 мс 0,1617 мс 1.00 Optimization Spartial 300 12,399 мс 0,0943 мс 0,0882 мс 0,45 Оптимизатсияи SpartialParallel 300 6,252 мс 0,0211 мс 0,0187 мс 0,23 Асосӣ 600 217,897 мс 1,6415 мс 1,5355 мс 1.00 Optimization Spartial 600 99,122 мс 0,8230 мс 0,7698 мс 0,45 Оптимизатсияи SpartialParallel 600 35,825 мс 0,1003 мс 0,0837 мс 0,16 Асосӣ 1200 1,763,335 мс 7,4561 мс 6,2262 мс 1.00 Optimization Spartial 1200 766,675 мс 6,1147 мс 5,7197 мс 0,43 Оптимизатсияи SpartialParallel 1200 248,801 мс 0,6040 мс 0,5043 мс 0,14 Асосӣ 2400 14,533,335 мс 63,3518 мс 52,9016 мс 1.00 Optimization Spartial 2400 6,507,878 мс 28,2317 мс 26,4079 мс 0,45 Оптимизатсияи SpartialParallel 2400 2,076,403 мс 20,8320 мс 19,4863 мс 0,14 Асосӣ 4800 119,768,219 мс 181,5514 мс 160,9406 мс 1.00 Optimization Spartial 4800 55,590,374 мс 414,6051 мс 387,8218 мс 0,46 Оптимизатсияи SpartialParallel 4800 15,614,506 мс 115,6996 мс 102,5647 мс 0,13 Аз натиҷаҳо мо мебинем, ки параллелизатсияи даври вақти ҳисобкуниро нисбат ба татбиқи қаблӣ ( ) 2-4 маротиба кам кардааст! Ин хеле таъсирбахш аст, аммо дар хотир доштан муҳим аст, ки параллелизатсияи ҳисобҳои холис тамоми захираҳои ҳисоббарории мавҷударо истеъмол мекунад, ки метавонад ба гуруснагии захираҳои барномаҳои дигар дар система оварда расонад. for of i SpartialOptimisation Параллелизатсия бояд бо эҳтиёт истифода шавад. Тавре ки шумо тахмин карда метавонед - ин охири нест 🙂 Платформаи худро бидонед - векторизатсия табдил додани коди дар як элемент коркунанда ба коде мебошад, ки дар як вақт дар якчанд элемент амал мекунад. Векторизатсия Ин метавонад ба мисли як масъалаи мураккаб садо диҳад, пас биёед бубинем, ки он дар мисоли оддӣ чӣ гуна кор мекунад: 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]; Бо роҳи , иҷрои итератсияи и даври дар боло зикршуда дар сатҳи CPU метавонад ба таври зерин тасвир карда шавад: аз ҳад зиёд соддакардашуда 0 for Ин аст он чизе ки рӯй медиҳад. CPU арзишҳои массивҳои ва аз хотира ба регистрҳои CPU бор мекунад (як реестр арзиш дошта метавонад). Сипас CPU амалиёти иловаи скаляриро дар ин реестрҳо иҷро мекунад ва натиҷаро дубора ба хотираи асосӣ - рост ба массиви менависад. Ин раванд чор маротиба пеш аз ба охир расидани давра такрор карда мешавад. a b маҳз як c Векторизатсия маънои истифодаи регистрҳои махсуси CPU - регистрҳои векторӣ ё SIMD (як дастури чанд маълумот) ва дастурҳои мувофиқи CPU барои иҷрои амалиётҳо дар як вақт дар арзишҳои массивҳои сершумор мебошад: Дар ин ҷо чӣ рӯй дода истодааст. CPU арзишҳои массивҳои ва аз хотира ба регистрҳои CPU бор мекунад (аммо ин дафъа як реестри вектор метавонад арзиши массивро нигоҳ дорад). Сипас CPU амалиёти иловаи векториро дар ин реестрҳо иҷро мекунад ва натиҷаро ба хотираи асосӣ - рост ба массиви менависад. Азбаски мо якбора дар ду арзиш амал мекунем, ин раванд ба ҷои чаҳор маротиба ду маротиба такрор мешавад. a b ду c Барои татбиқи векторизатсия дар .NET мо метавонем - ва -ро истифода барем (мо инчунин метавонем намудҳоро аз фазои номҳои истифода барем, аммо онҳо барои татбиқи ҷорӣ каме пешакӣ ҳастанд, бинобар ин ман онҳоро истифода намебарам, аммо эҳсос мекунам ройгон барои санҷидани онҳо): Вектор Вектор<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; } } } } } Рамзи векторӣ метавонад каме аҷиб ба назар расад, бинобар ин биёед онро зина ба зина гузарем. Мо вектори роҳро эҷод мекунем: . Дар натиҷа, агар вектор чаҳор қимати навъи дошта бошад ва вазни роҳи ба 5 баробар бошад, мо вектори чор 5-ро эҷод мекунем – [5, 5, 5, 5]. Минбаъд, дар ҳар як такрор, мо ҳамзамон роҳҳоро аз қуллаи то қуллаҳои ҳисоб мекунем. i ⭢ k var ik_vec = new Vector<int>(matrix[i * sz + k]) int i ⭢ k i j, j + 1, ..., j + Vector<int>.Count Хосияти шумораи унсурҳои навъи ро, ки ба регистрҳои векторӣ мувофиқанд, бармегардонад. Андозаи регистрҳои векторӣ аз модели CPU вобаста аст, бинобар ин ин амвол метавонад арзишҳои гуногунро дар CPU-ҳои гуногун баргардонад. Vector<int>.Count int - Эзоҳи муаллиф Тамоми раванди ҳисобкуниро ба се марҳила тақсим кардан мумкин аст: Маълумотро аз матритсаи вазн ба векторҳо бор кунед: ва . ij_vec ikj_vec Векторҳои ва муқоиса кунед ва арзишҳои хурдтаринро ба вектори нави интихоб кунед. ij_vec ikj_vec r_vec ба матритсаи вазн баргардонед. r_vec Дар ҳоле ки ва хеле соддаанд, шарҳро талаб мекунад. Тавре ки қаблан зикр гардид, бо векторҳо мо дар як вақт арзишҳои сершуморро идора мекунем. Аз ин рӯ, натиҷаи баъзе амалиётҳо ягона буда наметавонад, яъне амалиёти муқоисавии наметавонад ё баргардонад, зеро он арзишҳои сершуморро муқоиса мекунад. Ба ҷои ин, он вектори наверо бар мегардонад, ки дорои натиҷаҳои муқоиса байни арзишҳои мувофиқ аз векторҳои ва ( , агар арзиши камтар аз арзиши ва бошад, агар дар акси ҳол). Вектори баргардонидашуда (худ) аслан муфид нест, аммо мо метавонем амалиёти вектории барои истихроҷи арзишҳои зарурӣ аз векторҳои ва ба вектори нав - истифода барем. Ин амалиёт вектори наверо бармегардонад, ки дар он арзишҳо ба хурдтар аз ду қимати мувофиқи векторҳои воридотӣ баробаранд, яъне агар арзиши вектори ба баробар бошад, пас амалиёт қиматро аз интихоб мекунад, вагарна аз арзиш интихоб мекунад. №1 №3 №2 Vector.LessThan(ij_vec, ikj_vec) true false ij_vec ikj_vec -1 ij_vec ikj_vec 0 Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec) ij_vec ikj_vec r_vec lt_vec -1 ij_vec ikj_vec Ба ғайр аз , як қисми дигар вуҷуд дорад, ки шарҳро талаб мекунад - ҳалқаи дуюми векторнашуда. Он вақте лозим аст, ки андозаи матритсаи вазн ҳосили арзиши набошад. Дар ин ҳолат, ҳалқаи асосӣ наметавонад ҳамаи арзишҳоро коркард кунад (зеро шумо қисми векторро бор карда наметавонед) ва дуюм, ғайривекторӣ, давра такрори боқимондаро ҳисоб мекунад. №2 Vector<int>.Count Инҳоянд натиҷаҳои ин ва ҳама амалҳои қаблӣ: Усул сз Маънои Хатогӣ StdDev Таносуб Асосӣ 300 27,525 мс 0,1937 мс 0,1617 мс 1.00 Optimization Spartial 300 12,399 мс 0,0943 мс 0,0882 мс 0,45 Оптимизатсияи SpartialParallel 300 6,252 мс 0,0211 мс 0,0187 мс 0,23 Optimizations SpartialVector 300 3,056 мс 0,0301 мс 0,0281 мс 0,11 Асосӣ 600 217,897 мс 1,6415 мс 1,5355 мс 1.00 Optimization Spartial 600 99,122 мс 0,8230 мс 0,7698 мс 0,45 Оптимизатсияи SpartialParallel 600 35,825 мс 0,1003 мс 0,0837 мс 0,16 Optimizations SpartialVector 600 24,378 мс 0,4320 мс 0,4041 мс 0,11 Асосӣ 1200 1,763,335 мс 7,4561 мс 6,2262 мс 1.00 Optimization Spartial 1200 766,675 мс 6,1147 мс 5,7197 мс 0,43 Оптимизатсияи SpartialParallel 1200 248,801 мс 0,6040 мс 0,5043 мс 0,14 Optimizations SpartialVector 1200 185,628 мс 2,1240 мс 1,9868 мс 0,11 Асосӣ 2400 14,533,335 мс 63,3518 мс 52,9016 мс 1.00 Optimization Spartial 2400 6,507,878 мс 28,2317 мс 26,4079 мс 0,45 Оптимизатсияи SpartialParallel 2400 2,076,403 мс 20,8320 мс 19,4863 мс 0,14 Optimizations SpartialVector 2400 2,568,676 мс 31,7359 мс 29,6858 мс 0,18 Асосӣ 4800 119,768,219 мс 181,5514 мс 160,9406 мс 1.00 Optimization Spartial 4800 55,590,374 мс 414,6051 мс 387,8218 мс 0,46 Оптимизатсияи SpartialParallel 4800 15,614,506 мс 115,6996 мс 102,5647 мс 0,13 Optimizations SpartialVector 4800 18,257,991 мс 84,5978 мс 79,1329 мс 0,15 Аз натиҷа маълум аст, ки векторизатсия вақти ҳисобкуниро ба таври назаррас коҳиш додааст - аз 3 то 4 маротиба дар муқоиса бо версияи параллелнашуда ( ). Лаҳзаи ҷолиб дар ин ҷо ин аст, ки версияи векторӣ инчунин аз версияи параллелӣ ( ) дар графикҳои хурдтар (камтар аз 2400 қуллаҳо) бартарӣ дорад. SpartialOptimisation SpartialParallelOptimisations Ва ниҳоят, вале на камтар аз он - биёед векторизатсия ва параллелизмро якҷоя кунем! Агар шумо ба татбиқи амалии векторизатсия таваҷҷӯҳ дошта бошед, ман ба шумо тавсия медиҳам, ки силсилаи паёмҳои хонед, ки дар он ро вектор кардааст (ин натиҷаҳо баъдтар дар навсозӣ барои ҷамъоварии партов дар пайдо шуданд). Дэн Шехтерро Array.Sort .NET 5 Платформа ва сахтафзори худро бидонед - векторизатсия ва параллелизм! Иҷрои охирин кӯшишҳои параллелизатсия ва векторизатсияро муттаҳид мекунад ва … ростқавлона он фардият надорад 🙂 Зеро… хуб, мо танҳо як ҷузъи -ро аз бо ҳалқаи векторишудаи иваз кардем: Parallel.For SpartialParallelOptimisations SpartialVectorOptimisations 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; } } }); } } Ҳамаи натиҷаҳои ин мақола дар зер оварда шудаанд. Тавре ки интизор мерафт, истифодаи ҳамзамон параллелизм ва векторизатсия натиҷаҳои беҳтаринро нишон дода, вақти ҳисобкуниро то 25 маротиба (барои графикҳои 1200 қулла) нисбат ба татбиқи аввалия кам кард. Усул сз Маънои Хатогӣ StdDev Таносуб Асосӣ 300 27,525 мс 0,1937 мс 0,1617 мс 1.00 Optimization Spartial 300 12,399 мс 0,0943 мс 0,0882 мс 0,45 Оптимизатсияи SpartialParallel 300 6,252 мс 0,0211 мс 0,0187 мс 0,23 Optimizations SpartialVector 300 3,056 мс 0,0301 мс 0,0281 мс 0,11 Оптимизатсияи SpartialParallelVector 300 3,008 мс 0,0075 мс 0,0066 мс 0,11 Асосӣ 600 217,897 мс 1,6415 мс 1,5355 мс 1.00 Optimization Spartial 600 99,122 мс 0,8230 мс 0,7698 мс 0,45 Оптимизатсияи SpartialParallel 600 35,825 мс 0,1003 мс 0,0837 мс 0,16 Optimizations SpartialVector 600 24,378 мс 0,4320 мс 0,4041 мс 0,11 Оптимизатсияи SpartialParallelVector 600 13,425 мс 0,0319 мс 0,0283 мс 0,06 Асосӣ 1200 1,763,335 мс 7,4561 мс 6,2262 мс 1.00 Optimization Spartial 1200 766,675 мс 6,1147 мс 5,7197 мс 0,43 Оптимизатсияи SpartialParallel 1200 248,801 мс 0,6040 мс 0,5043 мс 0,14 Optimizations SpartialVector 1200 185,628 мс 2,1240 мс 1,9868 мс 0,11 Оптимизатсияи SpartialParallelVector 1200 76,770 мс 0,3021 мс 0,2522 мс 0,04 Асосӣ 2400 14,533,335 мс 63,3518 мс 52,9016 мс 1.00 Optimization Spartial 2400 6,507,878 мс 28,2317 мс 26,4079 мс 0,45 Оптимизатсияи SpartialParallel 2400 2,076,403 мс 20,8320 мс 19,4863 мс 0,14 Optimizations SpartialVector 2400 2,568,676 мс 31,7359 мс 29,6858 мс 0,18 Оптимизатсияи SpartialParallelVector 2400 1,281,877 мс 25,1127 мс 64,8239 мс 0,09 Асосӣ 4800 119,768,219 мс 181,5514 мс 160,9406 мс 1.00 Optimization Spartial 4800 55,590,374 мс 414,6051 мс 387,8218 мс 0,46 Оптимизатсияи SpartialParallel 4800 15,614,506 мс 115,6996 мс 102,5647 мс 0,13 Optimizations SpartialVector 4800 18,257,991 мс 84,5978 мс 79,1329 мс 0,15 Оптимизатсияи SpartialParallelVector 4800 12,785,824 мс 98,6947 мс 87,4903 мс 0,11 Хулоса Дар ин мақола мо каме ба як мушкили кӯтоҳтарин роҳи ҳама ҷуфт ғарқ шудем ва алгоритми Флойд-Уоршаллро дар C# барои ҳалли он татбиқ кардем. Мо инчунин татбиқи худро барои эҳтироми додаҳо ва истифодаи хусусиятҳои сатҳи пасти .NET ва сахтафзор навсозӣ кардем. Дар ин паём мо "ҳама дар" бозӣ кардем. Бо вуҷуди ин, дар барномаҳои ҳаёти воқеӣ дар хотир доштан муҳим аст - мо танҳо нестем. Параллелизатсияи хардкор метавонад кори системаро ба таври назаррас коҳиш диҳад ва зарари бештар аз фоида расонад. Векторизатсия аз тарафи дигар, агар он бо роҳи мустақили платформа анҷом дода шавад, каме бехатартар аст. Дар хотир доред, ки баъзе дастурҳои векторӣ метавонанд танҳо дар CPU-ҳои муайян дастрас бошанд. Умедворам, ки шумо аз хондан лаззат бурдаед ва аз "фишурдани" баъзе битҳои иҷроиш аз алгоритм бо ҳамагӣ СЕ давра лаззат бурдед 🙂 Иқтибосҳо Флойд, Алгоритми RW 97: Роҳи кӯтоҳтарин / RW Floyd // Коммуникатсияи ACM. – 1962. – Ҷилди. 5, №. 6. – С. 345-. Ingerman, PZ Algorithm 141: Матритсаи роҳ / PZ Ingerman // Коммуникатсияи ACM. – 1962. – Ҷилди. 5, №. 11. – С. 556.
