Ҳалли масъалаи ҳамаи ҷуфтҳои кӯтоҳтарин роҳҳо бо алгоритми Флойд-Уоршалл дар C#

Ҳар яки мо дар як рӯз чанд маротиба масъалаи “ роҳи кӯтоҳтарин ”-ро ҳал мекунем. Албатта нохост. Мо онро дар роҳи кор ё ҳангоми дидани Интернет ё ҳангоми ҷойгир кардани чизҳои худ дар мизи корӣ ҳал мекунем.

Садо каме… аз ҳад зиёд? Биёед бифаҳмем.

Тасаввур кунед, ки шумо қарор додед, ки бо дӯстон вохӯред, хуб ... биёед дар қаҳвахона бигӯед. Пеш аз ҳама, ба шумо лозим аст, ки як масир (ё роҳ) ба қаҳвахона пайдо кунед, бинобар ин шумо ба ҷустуҷӯи нақлиёти ҷамъиятии дастрас (агар шумо пиёда бошед) ё хатсайрҳо ва кӯчаҳо (агар шумо ронандагӣ бошед) оғоз кунед. Шумо масирро аз макони ҳозираи худ то қаҳвахона меҷӯед, аммо на "ягон масир" - кӯтоҳтарин ё зудтарин.

Инак як мисоли дигар, ки мисли мисоли қаблӣ чандон равшан нест. Ҳангоми кор шумо қарор медиҳед, ки аз кӯчаи канори "бури кӯтоҳ" гузаред, зеро ... ин "бури кӯтоҳ" аст ва рафтан ба ин роҳ "тезтар" аст. Аммо шумо аз куҷо медонистед, ки ин "бури кӯтоҳ" тезтар аст? Дар асоси таҷрибаи шахсӣ шумо як масъалаи "кӯтоҳтарин роҳ" -ро ҳал кардед ва масиреро интихоб кардед, ки аз кӯчаи канор мегузарад.

Дар ҳарду мисол, масири "кӯтоҳтарин" дар масофа ё вақт муайян карда мешавад, ки барои аз як ҷо ба ҷои дигар рафтан лозим аст. Намунаҳои сайёҳӣ барномаҳои хеле табиии назарияи графикӣ ва махсусан мушкилоти "роҳи кӯтоҳтарин" мебошанд. Бо вуҷуди ин, дар бораи намунаи ба тартиб даровардани чизҳо дар рӯи миз чӣ гуфтан мумкин аст? Дар ин ҳолат "кӯтоҳтарин" метавонад як миқдор ё мураккабии амалҳоеро нишон диҳад, ки шумо бояд барои ба даст овардани варақи коғаз иҷро кунед: мизи кушода, папкаи кушода, варақи коғазро гиред ва варақи коғазро рост аз мизи корӣ гиред. .

Ҳамаи мисолҳои дар боло овардашуда мушкилоти дарёфти роҳи кӯтоҳтарин байни ду қуллаи графикро ифода мекунанд (маршрут ё роҳи байни ду ҷой, як қатор амалҳо ё мураккабии гирифтани варақ аз ин ё он ҷо). Ин синфи мушкилоти роҳи кӯтоҳтарин 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

Давраи аз ҳама берунӣ for k дар болои ҳамаи қуллаҳои график такрор мешавад ва дар ҳар як итератсия, тағирёбандаи k қуллаеро ифода мекунад , ки мо роҳҳои ҷустуҷӯи тавассути . Давраи дохилӣ for on 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] .

Акнун, вақте ки мо механикаро мефаҳмем, вақти татбиқи алгоритм аст.

Татбиқи асосӣ

Пеш аз ворид шудан ба татбиқ, мо бояд якчанд лаҳзаҳои техникиро равшан кунем:

1. Ҳама татбиқҳо бо матритсаи вазн, ки дар шакли массиви хатӣ муаррифӣ шудаанд, кор мекунанд.
2. Ҳама татбиқҳо арифметикаи бутунро истифода мебаранд. Набудани роҳ дар байни қуллаҳо бо вазни махсуси доимӣ ифода карда мешавад: NO_EDGE = (int.MaxValue / 2) - 1 .

Акнун биёед бифаҳмем, ки чаро ин аст.

Дар бораи №1. Вақте ки мо дар бораи матритсаҳо сухан меронем, мо ҳуҷайраҳоро аз рӯи “сатрҳо” ва “сутунҳо” муайян мекунем. Аз ин рӯ, тасаввур кардани матритса дар шакли «мураббаъ» ё «росткунҷа» табиист (Расми 4а).

Аммо, ин маънои онро надорад, ки мо бояд матритсаро дар шакли массивҳо муаррифӣ кунем (Расми 4б) то ба тасаввуроти худ пайваст шавем. Ба ҷои ин, мо метавонем матритсаро дар шакли массиви хатӣ муаррифӣ кунем (Расми 4c), ки индекси ҳар як чашмак бо формулаи зерин ҳисоб карда мешавад:

 i = row * row_size + col; // where row - cell row index, // col - cell column index, // row_size - number of cells in a row.

Массиви хаттии матритсаи вазн шарти пешакии иҷрои самараноки алгоритми Флойд-Уоршалл мебошад. Сабаби ин содда нест ва шарҳи муфассал сазовори як мақолаи алоҳида ... ё чанд паём аст. Бо вуҷуди ин, айни замон бояд қайд кард, ки чунин муаррифӣ ҷойгиршавии маълумотро ба таври назаррас беҳтар мекунад, ки дар асл ба кори алгоритм таъсири калон мерасонад.

Дар бораи № 2. Агар шумо ба алгоритми псевдокоди бодиққат назар андозед, шумо ягон санҷиши марбут ба мавҷудияти роҳ байни ду қулларо намеёбед. Ба ҷои ин, псевдокод танҳо функсияи min() ро истифода мебарад. Сабаб оддӣ аст - дар аввал, агар байни қуллаҳо роҳ мавҷуд набошад, арзиши ячейка ба infinity муқаррар карда мешавад ва дар ҳама забонҳо, ба истиснои JavaScript, ҳама арзишҳо аз infinity камтаранд. Дар сурати мавҷуд будани ададҳо, он метавонад васвасаи истифодаи int.MaxValue ҳамчун арзиши "ҳеҷ роҳ" бошад. Аммо ин боиси зиёд шудани ададҳои бутун мегардад, дар ҳолатҳое, ки қиматҳои ҳам i ⭢ k ва k ⭢ j роҳҳо ба int.MaxValue баробар мешаванд. Аз ин рӯ, мо арзишеро истифода мебарем, ки як камтар аз нисфи int.MaxValue аст.

Ин дар ҳақиқат имконпазир аст, аммо мутаассифона он ба ҷазои назарраси иҷроиш оварда мерасонад. Хулоса, CPU омори натиҷаҳои арзёбии филиалҳоро нигоҳ медорад, масалан. вақте ки баъзе аз изҳороти if true ё false арзёбӣ мешаванд. Он ин оморро барои иҷро кардани рамзи "шохаи аз ҷиҳати оморӣ пешбинишуда" пеш аз баҳодиҳии if воқеӣ истифода мебарад (ин иҷроиши тахминӣ номида мешавад) ва аз ин рӯ кодро самараноктар иҷро мекунад. Аммо, вақте ки пешгӯии CPU нодуруст аст, он дар муқоиса бо пешгӯии дуруст ва иҷрои бечунучаро талафоти назаррасро ба бор меорад, зеро CPU бояд шохаи дурустро қатъ ва ҳисоб кунад.

Азбаски дар ҳар як такрори k мо як қисми зиёди матритсаи вазнро навсозӣ мекунем, омори филиали CPU бефоида мешавад, зеро намунаи рамз вуҷуд надорад, ҳама шохаҳо танҳо ба маълумот асос ёфтаанд. Ҳамин тавр, чунин санҷиш боиси миқдори зиёди пешгӯиҳои нодурусти соҳа мегардад.

Дар ин ҷо ман инчунин аз шумо хоҳиш мекунам, ки ба ман бовар кунед (ҳоло) ва сипас барои омӯзиши мавзӯъ каме вақт ҷудо кунед.

Уҳ, ба назар чунин мерасад, ки мо қисми назариявиро анҷом додем - биёед алгоритмро амалӣ кунем (мо ин татбиқро ҳамчун 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 навсозии ячейка танҳо ҳангоми зарурат истифода мебарем.

Сабаб оддӣ аст. Дар лаҳзаи навиштани 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 мавҷуд набудани навиштани нолозим.

Ҳоло, вақте ки мо татбиқро анҷом додем, вақти он расидааст, ки кодро иҷро кунем ва бубинем, ки он чӣ қадар тез аст?!

Ман Benchmark.NET (версияи 0.12.1) -ро барои санҷиши код истифода мекунам. Ҳама графикҳое, ки дар нишондиҳандаҳо истифода мешаванд , равона карда шудаанд, графикҳои асиклии 300, 600, 1200, 2400 ва 4800. Миқдори кунҷҳо дар графикҳо тақрибан 80% аз ҳадди имконпазирро ташкил медиҳад, ки барои графикҳои мутаҳаррикшуда ва даврӣ чунин ҳисоб кардан мумкин аст:

 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 ядро):

Аз натиҷаҳое, ки мо мебинем, вақти ҳисобкунӣ дар муқоиса бо андозаи график хеле зиёд мешавад - барои графики 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 ) дар як маҷмӯи графикҳо (натиҷаҳои зудтарин бо ғафс нишон дода шудаанд):

Хеле таъсирбахш!

Мо вақти ҳисобкуниро дар як ним кам кардем! Албатта, график чӣ қадар зичтар бошад, суръат ҳамон қадар камтар мешавад. Аммо, ин яке аз оптимизатсияҳоест, ки агар шумо пешакӣ донед, ки шумо бо кадом синфи маълумот кор кардан мехоҳед, муфид аст.

Оё мо метавонем бештар кор кунем? 🙂

Таҷҳизоти худро бидонед - параллелизм

Компютери ман бо протсессори Inter Core i7-7700 CPU 3.60GHz (Kaby Lake) бо 8 протсессори мантиқӣ ( HW ) ё 4 ядро бо технологияи Hyper-Threading муҷаҳҳаз шудааст. Доштани зиёда аз як ядро ба монанди доштани "дастҳои эҳтиётии" бештар аст, ки мо метавонем онҳоро ба кор гузорем. Пас, биёед бубинем, ки кадом қисми корро байни коргарони сершумор ба таври муассир тақсим кардан мумкин аст ва сипас онро параллел созед.

Доиравҳо ҳамеша номзади возеҳтарин барои параллелизатсия мебошанд, зеро дар аксари мавридҳо такрорҳо мустақиланд ва метавонанд ҳамзамон иҷро шаванд. Дар алгоритм, мо се ҳалқа дорем, ки мо бояд онҳоро таҳлил кунем ва бубинем, ки оё ягон вобастагӣ вуҷуд дорад, ки моро ба параллелизатсияи онҳо бозмедоранд.

Биёед аз for of k оғоз кунем. Дар ҳар як ҳалқаи такрорӣ роҳҳоро аз ҳар як қулла ба ҳар як қулла тавассути қуллаи k ҳисоб мекунад. Роҳҳои нав ва навшуда дар матритсаи вазн нигоҳ дошта мешаванд. Ба такрорҳо нигоҳ карда, шумо метавонед мушоҳида кунед - онҳо метавонанд бо ҳама гуна тартиб иҷро карда шаванд: 0, 1, 2, 3 ё 3, 1, 2, 0 бидуни таъсир ба натиҷа. Бо вуҷуди ин, онҳо бояд ба таври пайдарпай иҷро карда шаванд, вагарна баъзе аз такрорҳо наметавонанд роҳҳои нав ё навшударо истифода баранд, зеро онҳо ҳанӯз дар матритсаи вазн навишта намешаванд. Чунин номутобиқатӣ бешубҳа натиҷаҳоро хароб хоҳад кард. Пас, мо бояд ҷустуҷӯро давом диҳем.

Номзади навбатӣ for of i loop аст. Дар ҳар як даври такрорӣ роҳро аз қуллаи 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 ишора мекунем).

 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 анҷом дода мешавад):

Аз натиҷаҳо мо мебинем, ки параллелизатсияи даври for of i вақти ҳисобкуниро нисбат ба татбиқи қаблӣ ( SpartialOptimisation ) 2-4 маротиба кам кардааст! Ин хеле таъсирбахш аст, аммо дар хотир доштан муҳим аст, ки параллелизатсияи ҳисобҳои холис тамоми захираҳои ҳисоббарории мавҷударо истеъмол мекунад, ки метавонад ба гуруснагии захираҳои барномаҳои дигар дар система оварда расонад. Параллелизатсия бояд бо эҳтиёт истифода шавад.

Тавре ки шумо тахмин карда метавонед - ин охири нест 🙂

Платформаи худро бидонед - векторизатсия

Векторизатсия табдил додани коди дар як элемент коркунанда ба коде мебошад, ки дар як вақт дар якчанд элемент амал мекунад.

Ин метавонад ба мисли як масъалаи мураккаб садо диҳад, пас биёед бубинем, ки он дар мисоли оддӣ чӣ гуна кор мекунад:

 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];

Бо роҳи аз ҳад зиёд соддакардашуда , иҷрои итератсияи 0 и for даври дар боло зикршуда дар сатҳи CPU метавонад ба таври зерин тасвир карда шавад:

Ин аст он чизе ки рӯй медиҳад. CPU арзишҳои массивҳои a ва b аз хотира ба регистрҳои CPU бор мекунад (як реестр маҳз як арзиш дошта метавонад). Сипас CPU амалиёти иловаи скаляриро дар ин реестрҳо иҷро мекунад ва натиҷаро дубора ба хотираи асосӣ - рост ба массиви c менависад. Ин раванд чор маротиба пеш аз ба охир расидани давра такрор карда мешавад.

Векторизатсия маънои истифодаи регистрҳои махсуси CPU - регистрҳои векторӣ ё SIMD (як дастури чанд маълумот) ва дастурҳои мувофиқи CPU барои иҷрои амалиётҳо дар як вақт дар арзишҳои массивҳои сершумор мебошад:

Дар ин ҷо чӣ рӯй дода истодааст. CPU арзишҳои массивҳои a ва b аз хотира ба регистрҳои CPU бор мекунад (аммо ин дафъа як реестри вектор метавонад ду арзиши массивро нигоҳ дорад). Сипас CPU амалиёти иловаи векториро дар ин реестрҳо иҷро мекунад ва натиҷаро ба хотираи асосӣ - рост ба массиви 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; } } } } }

Рамзи векторӣ метавонад каме аҷиб ба назар расад, бинобар ин биёед онро зина ба зина гузарем.

Мо вектори i ⭢ k роҳро эҷод мекунем: var ik_vec = new Vector<int>(matrix[i * sz + k]) . Дар натиҷа, агар вектор чаҳор қимати навъи int дошта бошад ва вазни роҳи i ⭢ k ба 5 баробар бошад, мо вектори чор 5-ро эҷод мекунем – [5, 5, 5, 5]. Минбаъд, дар ҳар як такрор, мо ҳамзамон роҳҳоро аз қуллаи i то қуллаҳои j, j + 1, ..., j + Vector<int>.Count ҳисоб мекунем.

Тамоми раванди ҳисобкуниро ба се марҳила тақсим кардан мумкин аст:

1. Маълумотро аз матритсаи вазн ба векторҳо бор кунед: ij_vec ва ikj_vec .
2. Векторҳои ij_vec ва ikj_vec муқоиса кунед ва арзишҳои хурдтаринро ба вектори нави r_vec интихоб кунед.
3. 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 набошад. Дар ин ҳолат, ҳалқаи асосӣ наметавонад ҳамаи арзишҳоро коркард кунад (зеро шумо қисми векторро бор карда наметавонед) ва дуюм, ғайривекторӣ, давра такрори боқимондаро ҳисоб мекунад.

Инҳоянд натиҷаҳои ин ва ҳама амалҳои қаблӣ:

Аз натиҷа маълум аст, ки векторизатсия вақти ҳисобкуниро ба таври назаррас коҳиш додааст - аз 3 то 4 маротиба дар муқоиса бо версияи параллелнашуда ( SpartialOptimisation ). Лаҳзаи ҷолиб дар ин ҷо ин аст, ки версияи векторӣ инчунин аз версияи параллелӣ ( SpartialParallelOptimisations ) дар графикҳои хурдтар (камтар аз 2400 қуллаҳо) бартарӣ дорад.

Ва ниҳоят, вале на камтар аз он - биёед векторизатсия ва параллелизмро якҷоя кунем!

Платформа ва сахтафзори худро бидонед - векторизатсия ва параллелизм!

Иҷрои охирин кӯшишҳои параллелизатсия ва векторизатсияро муттаҳид мекунад ва … ростқавлона он фардият надорад 🙂 Зеро… хуб, мо танҳо як ҷузъи 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 қулла) нисбат ба татбиқи аввалия кам кард.

Хулоса

Дар ин мақола мо каме ба як мушкили кӯтоҳтарин роҳи ҳама ҷуфт ғарқ шудем ва алгоритми Флойд-Уоршаллро дар C# барои ҳалли он татбиқ кардем. Мо инчунин татбиқи худро барои эҳтироми додаҳо ва истифодаи хусусиятҳои сатҳи пасти .NET ва сахтафзор навсозӣ кардем.

Дар ин паём мо "ҳама дар" бозӣ кардем. Бо вуҷуди ин, дар барномаҳои ҳаёти воқеӣ дар хотир доштан муҳим аст - мо танҳо нестем. Параллелизатсияи хардкор метавонад кори системаро ба таври назаррас коҳиш диҳад ва зарари бештар аз фоида расонад. Векторизатсия аз тарафи дигар, агар он бо роҳи мустақили платформа анҷом дода шавад, каме бехатартар аст. Дар хотир доред, ки баъзе дастурҳои векторӣ метавонанд танҳо дар CPU-ҳои муайян дастрас бошанд.

Умедворам, ки шумо аз хондан лаззат бурдаед ва аз "фишурдани" баъзе битҳои иҷроиш аз алгоритм бо ҳамагӣ СЕ давра лаззат бурдед 🙂

Иқтибосҳо

1. Флойд, Алгоритми RW 97: Роҳи кӯтоҳтарин / RW Floyd // Коммуникатсияи ACM. – 1962. – Ҷилди. 5, №. 6. – С. 345-.
2. Ingerman, PZ Algorithm 141: Матритсаи роҳ / PZ Ingerman // Коммуникатсияи ACM. – 1962. – Ҷилди. 5, №. 11. – С. 556.