“Skaldi un valdi” – Algoritmu paradigma

“Skaldi un valdi”, jeb “Divide and conquer” paradigma piedāvā noderīgu ietvaru domāšanai par to, kā atrisināt konkrēto problēmu. Tas ietver apspriestos principus, proti, rekursiju un problēmu sadalīšanu mazākās problēmās. Šajā rakstā jūs uzzināsiet par “Skaldi un valdi” paradigmu un to, kā tā piedāvā sistēmu problēmu risināšanai. Jūs arī uzzināsiet par obligātajiem un izvēles soļiem, kas saistīti ar “Skaldi un valdi” paradigmu, un par to, kādas priekšrocības šī paradigma sniedz datoriem.

Tātad, kā darbojas dalīšanas un valdīšanas algoritms? Algoritms sastāv no diviem soļiem ar neobligātu trešo, proti, sadali un iekaro, kas ir obligātie soļi, un apvieno, kas ir izvēles solis.

• Sadalīšanas posmā ievade tiek sadalīta mazākos segmentos un tiek apstrādāta atsevišķi. – Divide
• Iekarošanas solī tiek atrisināts katrs uzdevums, kas saistīts ar konkrēto segmentu. – Conquer
• Izvēles pēdējais solis, apvienošana, ir visu atrisināto segmentu apvienošana. – Combine

Tas nenotiks katrā gadījumā, bet gan norādītajā piemērā. Tālāk ir sniegts skaldi un valdi paradigmas piemērs. Apspriežot šķirošanas pieejas, tika parādīts, ka problēmas risināšanai ir daudz veidu. Izmantojot šķirošanu kā piemēru, apspriedīsim citu šķirošanas pieeju, ko var atrisināt, izmantojot “Skaldi un valdi” pieeju.

Sapludināšanas kārtošana ir sarežģīta pieeja masīva kārtošanai. Tas sākas ar masīvu, šīs divas puses, pēc tam uz pusēm un vēlreiz uz pusēm. Šis process tiek atkārtots, līdz ir palicis tikai viens elements, pēc tam process tiek apgriezts un katrs mazākais saraksts tiek sakārtots pirms atkārtotas pievienošanas daļai, no kuras tas tika samazināts uz pusi. Šis problēmas risinājums ir balstīts uz domu, ka, sadalot problēmu mazākās problēmās, ir vieglāk izpildīt kopējo uzdevumu.

Lai iegūtu labāku intuīciju par to, kā skaldīt un valdīt var izmantot sapludināšanas kārtošanai, izpētīsim reālās pasaules piemēru. Apsveriet, ka jūs un trīs mājinieki esat nolēmuši iepirkties kopā. Pēc plašā saraksta sastādīšanas jūs visi dodieties uz lielveikalu. Viens no risinājumiem varētu būt, ka jūs visi staigājat pa lielveikalu un paņemat katru preci no saraksta. Labāka pieeja varētu būt sarakstu sadalīt četrās daļās un katram paņemt vienu sadaļu, tādējādi samazinot kopējo veikalā pavadīto laiku. Lai gan tas var izraisīt pušu pārklāšanos, turpmāka uzdevuma optimizācija varētu būt vispirms saraksta kārtošana. Lai visi līdzīgi priekšmeti būtu kopā, piemēram, visi dzērieni, augļi, gaļa un tā tālāk.

Pēc tam katram dalībniekam piešķiriet noteiktu lielveikala zonu, tā būtu vēl efektīvāka pieeja uzdevuma izpildei. Kā jau saka, ka kopīga problēma ir uz pusi mazāka problēma. Tātad, kā tas darbojas datoros?

Ir divas tūlītējas priekšrocības, proti, paralēlizācija (Parallelization) un atmiņas pārvaldība (Memory management).

• Paralēlisms ir tad, kad ar vienu un to pašu problēmu vienlaikus strādā dažādi pavedieni vai datori, lai to paveiktu ātrāk. Ieguvums, izmantojot “Skaldi un valdi” risinājumus, ir tāds, ka pēc tam kodēšanas laikā varat izmantot paralēlismu.
• Tagad izpētīsim atmiņas pārvaldību. Izmantojot sapludināšanas kārtošanas piemēru, ņemiet vērā, ka katru masīvu var nosūtīt uz citu kodolu vai serveri atkarībā no jūsu organizācijas arhitektūras, un rezultāti pēc tam tiek atgriezti. Iespējams, apstrādātie dati ir pārāk lieli, lai tos saglabātu atmiņā, un tie ir jāapstrādā gabalos.

Turklāt priekšniekam var būt nodrošināta piekļuve mākoņdatošanai. Tātad risinājums var ietvert piekļuvi tiešsaistes serverim un dažu problēmu eksportēšanu no uzņēmuma serveriem. Tas viss palīdz pārvaldīt pieejamo atmiņu.

Neliels skaidrojošs piemērs, kā “Skaldi un valdi” izskatītos JavaScript kodā:

function divideAndConquer(arr) {
if (arr.length === 0) {
return null; // ja masīvs ir tukšs, atgriež null
}
if (arr.length === 1) {
return arr[0]; // ja masīvā ir tikai viens elements, atgriež to
}
const mid = Math.floor(arr.length / 2); // aprēķina masīva vidusindeksu
const left = arr.slice(0, mid); // sagriež masīvu pa kreisi no vidusindeksa
const right = arr.slice(mid); // sagriež masīvu pa labi no vidusindeksa
return merge(divideAndConquer(left), divideAndConquer(right)); // rekursīvi izsauc sevi pašu katram apakšmasīvam un apvieno rezultātus
}

function merge(left, right) {
const result = []; // izveido jaunu masīvu rezultātam
let i = 0; // i ir kreisā apakšmasīva indekss
let j = 0; // j ir labā apakšmasīva indekss
while (i < left.length && j < right.length) { // kamēr abiem apakšmasīviem ir elementi
if (left[i] < right[j]) { // ja kreisais elements ir mazāks par labo
result.push(left[i]); // pievieno kreiso elementu rezultāta masīvam
i++; // palielina i par vienu
} else { // ja labais elements ir mazāks vai vienāds ar kreiso
result.push(right[j]); // pievieno labo elementu rezultāta masīvam
j++; // palielina j par vienu
}
}
return result.concat(left.slice(i)).concat(right.slice(j)); // pievieno atlikušos elementus no abiem apakšmasīviem rezultāta masīvam un atgriež to
}

Šajā rakstā jūs iepazināties ar “Skaldi un valdi” paradigmu, izmantojot sapludināšanas kārtošanas piemēru un to, kā tā piedāvā sistēmu problēmu risināšanai. Tika parādīta dažāda ar to saistītā terminoloģija, kā arī tas, kā šī pieeja ir piemērota reālās pasaules datoru optimizācijas pieejām. Jūs arī uzzinājāt par obligātajiem un izvēles soļiem, kas saistīti ar “Skaldi un valdi” paradigmu, un kādas priekšrocības šī paradigma sniedz datoriem

.