Ako sa používa memoizácia v dynamických programovacích algoritmoch?

Memoizácia je rozhodujúcou technikou optimalizácie, ktorá sa používa pri dynamickom programovaní na významné zlepšenie účinnosti. Funguje tým, že ukladá výsledky drahých funkčných hovorov a vráti výsledok v pamäti cache, keď sa rovnaké vstupy objavia znova. Tým sa vyhýba nadbytočným výpočtom, čo vedie k dramatickému zrýchleniu, najmä v prípade problémov s prekrývajúcimi sa subproblémmi.

Takto sa používa:

1. Identifikácia prekrývajúcich sa podpísaných Dynamické programovanie rieši problémy tým, že ich rozdelí na menšie prekrývajúce sa subproblémy. Ak sa s rovnakým podpísanom vyskytuje viackrát, memoizácia môže zabrániť prepočítaniu.

2. Ukladanie výsledkov: Na ukladanie výsledkov subproblémov sa používa dátová štruktúra, zvyčajne tabuľka hash (slovník v Pythone) alebo pole. Ako kľúč slúži vstupom do podprofoku (napr. Parametre rekurzívnej funkcie) a vypočítaným výsledkom je hodnota.

3. Pred vypočítaním riešenia subproblému algoritmus skontroluje úložisko, aby sa zistilo, či je výsledok už k dispozícii. Ak je, výsledok v pamäti cache sa okamžite vráti.

4. Ukladanie a návrat výsledkov: Ak výsledok nie je ukladaný do vyrovnávacej pamäte, algoritmus ho vypočíta, uloží ho do dátovej štruktúry a potom ho vráti.

Príklad (Fibonacci Sekvencia):

Naivný rekurzívny roztok pre sekvenciu fibonacci je vysoko neefektívny v dôsledku opakovaných výpočtov. Memoizácia drasticky to zlepšuje:

naivné (neefektívne) rekurzívne riešenie:

`` `Python

def fibonacci_naive (n):

ak n <=1:

návrat n

návrat fibonacci_naive (n-1) + fibonacci_naive (n-2)

`` `

Memoizované rekurzívne riešenie:

`` `Python

memo ={} # Slovník pre poznámku

def fibonacci_memo (n):

Ak n v memore:

návrat poznámky [n]

ak n <=1:

výsledok =n

inak:

Výsledok =fibonacci_memo (n-1) + fibonacci_memo (n-2)

Memo [n] =výsledok

výsledok návratnosti

`` `

V poznámkovej verzii:

* `Memo` ukladá predtým vypočítané čísla fibonacci.

* Pred uskutočnením rekurzívneho hovoru `Fibonacci_memo` skontroluje, či je výsledok pre` n` už v `memo`.

* Ak je, uložená hodnota sa vráti priamo. V opačnom prípade sa výsledok vypočíta, uložený v `memo` a potom sa vráti.

Táto zmena transformuje algoritmus exponenciálneho času na algoritmus lineárneho času. Kľúčom je vyhnúť sa redundantným výpočtom rovnakých čísel fibonacci viackrát.

V podstate: Memoizácia transformuje prístup zhora nadol (rekurzívny) dynamický programovací prístup na efektívnejší prístup do ukladania do vyrovnávacej pamäte medziprodukty. Dopĺňa prístupy tabuľky (zdola nahor), ktoré sa tiež vyhýbajú nadbytočným výpočtom, ale namiesto rekurzie používajú iteračné metódy. Výber medzi poznámkou a tabuľkou často závisí od konkrétneho problému a preferencie programátora; Obaja dosahujú rovnaký cieľ vyhnúť sa redundantným výpočtom.

• Predchádzajúca strana: Považuje sa C programovací jazyk na vysokej úrovni alebo na nízkej úrovni? 
• Ďalšia strana: Ako môžem optimalizovať svoj kód pre rýchle matematické výpočty pomocou kompilátora GCC?