4.1 Memoizasiyanın tərifi və onun əsas konsepsiyaları
Memoizasiya — bu bir optimizasiya texnikasıdır, hansı ki baha başa gələn funksiyaların nəticələrini yadda saxlayır ki, eyni arqumentlərlə təkrar çağırışlar zamanı həmin nəticələrdən istifadə olunsun. Bu, təkrar hesablamaların sayını azaldır, beləliklə məhsuldarlığı artırır.
Əsas konsepsiyalar:
1. Keşləmə:
Funksiyanın nəticələrini müəyyən bir məlumat strukturasında (məsələn, sözlükdə ya da massivdə) yadda saxlamaq, ki təkrar çağırış zamanı həmin saxlanmış nəticəni qaytarsın və onu yenidən hesablamağa ehtiyac olmasın.
2. Lookup Table (Axtarış Cədvəli):
Funksiyanın əvvəlki çağırışlarının nəticələrini saxlamaq üçün istifadə olunan məlumat strukturası. Bu, hash-cədvəl (sözlük) və ya massiv ola bilər.
3. Rekursiv çağırışlar:
Memoizasiya xüsusilə rekursiv funksiyalar üçün faydalıdır, harada ki, eyni alt problemlər bir neçə dəfə eyni parametrlərlə icra oluna bilər.
Optimizasiya edilmiş alqoritmlərin vaxt və yer mürəkkəbliyi:
Vaxt mürəkkəbliyi:
Bir çox rekursiv problemlər üçün memoizasiya təkrar hesablamaların azalması sayəsində vaxt mürəkkəbliyini azaldır. Məsələn, Fibonacci ədədlərini rekursiv hesablama vaxt mürəkkəbliyinə malikdir O(2^n), amma memoizasiya ilə — O(n).
Yer mürəkkəbliyi:
Nəticələrin keşdə saxlanması üçün yer tutumunun artması. Adətən bu O(n) olur, memoizasiyaya ehtiyacı olan məsələlər üçün.
Yekun:
Memoizasiya rekursiv alqoritmlərin məhsuldarlığını əhəmiyyətli dərəcədə artırmağa imkan verən güclü bir optimizasiya texnikasıdır, hesablamaların təkrar olunmasını azaltmaqla.
Bu xüsusilə bir çox hallarda eyni alt problemlərin təkrar-təkrar eyni parametrlərlə icra olunması olan məsələlər üçün faydalıdır. Memoizasiya konsepsiyalarını başa düşmək və praktiki tətbiqi, yüksək hesablamalı məsələləri effektiv şəkildə həll etməyə imkan verir.
4.2 Optimizasiya nümunələri
Memoizasiya istifadə edərək rekursiv alqoritmlərin optimizasiya nümunələri
Nümunə 1: Fibonacci rəqəmləri
Memoizasiya olmadan Fibonacci rəqəmlərini hesablayan rekursiv alqoritm eksponensial vaxt mürəkkəbliyinə malikdir. Memoizasiya istifadəsi performansı əhəmiyyətli dərəcədə yaxşılaşdırır.
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# İstifadə nümunəsi:
print(fibonacci(10)) # Çıxış: 55
Vacib! Qeyd etmək lazımdır ki, biz memo=None dəyərini default olaraq istifadə edirik və sonra əgər memo ötürülmürsə, funksiyanın içində boş dictionary yaradılır. Bu, dəyişdirilə bilən obyektin default olaraq problem yaratmasının qarşısını alır.
Nümunə 2: Alt cəmin yoxlanışı
Verilmiş məcmudan elə bir alt məcmu varlığını tapmaq lazımdır ki, onun elementlərinin cəmi verilmiş dəyərə bərabər olsun.
def is_subset_sum(arr, n, sum_value, memo=None):
if memo is None:
memo = {}
if (n, sum_value) in memo:
return memo[(n, sum_value)]
if sum_value == 0:
return True
if n == 0 and sum_value != 0:
return False
if arr[n - 1] > sum_value:
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
return memo[(n, sum_value)]
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
return memo[(n, sum_value)]
# İstifadə nümunəsi:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Çıxış: True
Memoizasiya — əslində alt problemlərin nəticələrini cache etməkdir.
Məsələn, Fibonacci rəqəmi F(10) == F(9) + F(8), amma F(9)-u hesablamalı olmaq üçün F(8) və F(7)-i hesablamalıyıq. Yəni F(8)-i iki dəfə hesablamalıyıq: F(9) üçün ilk toplama olaraq və F(10) üçün ikinci toplama olaraq. Onu iki dəfə hesablamamaq üçün, ilk hesablamadan sonra onu cache etmək lazımdır.
GO TO FULL VERSION