DSA memoizatsiya

Memoizatsiya

Memoizatsiya — bir xil hisob-kitoblarni ko‘p marta bajarmaslik uchun natijalar saqlanadigan usul.

Memoizatsiya rekursiv algoritmlarni yaxshilash uchun ishlatilganda, u "yuqoridan pastga" (top-down) yondashuv deb ataladi, chunki u asosiy masaladan boshlab, uni kichikroq qism masalalarga ajratadi.

Memoizatsiya dinamik dasturlashda qo‘llaniladi.

Memoizatsiya yordamida \(n\)-Fibonachchi sonini topish

\(n\)-Fibonachchi sonini rekursiya yordamida topish mumkin. Bu qanday amalga oshirilishi haqida ushbu sahifada batafsil o‘qing.

Bu amalga oshirishdagi muammo shundaki, kattaroq Fibonachchi sonini topishga harakat qilinganda hisoblashlar va rekursiv chaqiruvlar soni "portlab" ketadi, chunki bir xil hisob-kitoblar qayta-qayta bajariladi.

def F(n):
    print('Computing F('+str(n)+')')
    if n <= 1:
        return n
    else:
        return F(n - 1) + F(n - 2)

print('F(6) = ',F(6))

Yuqoridagi misolni ishga tushirib ko‘rganingizdek, hatto 6-Fibonachchi sonini topish uchun ham 25 ta hisoblash bajariladi va bir xil hisoblashlar ko‘p marta takrorlanadi.

Ammo memoizatsiyadan foydalanish \(n\)-Fibonachchi sonini rekursiya yordamida ancha samaraliroq topishga yordam beradi.

Memoizatsiyadan foydalanish uchun Fibonachchi sonlarini saqlaydigan memo massivini yaratamiz, shunda n-Fibonachchi sonini memo[n] elementi sifatida topish mumkin bo‘ladi. Fibonachchi sonini esa faqat u memo massivida hali mavjud bo‘lmasa hisoblaymiz.

def F(n):
    if memo[n] != None: # Already computed
        return memo[n]
    else: # Computation needed
        print('Computing F('+str(n)+')')
        if n <= 1:
            memo[n] = n
        else:
            memo[n] = F(n - 1) + F(n - 2)
        return memo[n] 

memo = [None]*7
print('F(6) = ',F(6))
print('memo = ',memo)

Yuqoridagi misollarni ishga tushirib ko‘rganingizdek, memoizatsiya hisoblashlar sonini kamaytirishda juda foydali.

Hisoblashlar soni dastlabki koddagi 25 tadan memoizatsiyadan foydalanilgan oxirgi misolda atigi 7 taga kamayadi va biz topmoqchi bo‘lgan Fibonachchi soni qanchalik katta bo‘lsa, memoizatsiyadan foydalanish foydasi shunchalik tez ortadi.

30-Fibonachchi sonini topish dastlabki kodda 2 692 537 ta hisoblashni talab qiladi, memoizatsiya yordamida amalga oshirilgan algoritmda esa atigi 31 ta hisoblash kerak bo‘ladi!

Bu natijani quyidagi kodni ishga tushirib olasiz.

computation_count = 0
def F(n):
    global computation_count
    computation_count += 1
    if n <= 1:
        return n
    else:
        return F(n - 1) + F(n - 2)
        
computation_count_mem = 0
def F_mem(n):
    if memo[n] != None: # Already computed
        return memo[n]
    else: # Computation needed
        global computation_count_mem
        computation_count_mem += 1
        if n <= 1:
            memo[n] = n
        else:
            memo[n] = F_mem(n - 1) + F_mem(n - 2)
        return memo[n] 

print('F(30) = ',F(30))
print(f'Number of computations: {computation_count}')
print('\nUsing memoization:')
memo = [None]*31
print('F(30) = ',F_mem(30))
print(f'Number of computations with memoiztion: {computation_count_mem}')

AVL daraxtlarida memoizatsiya

AVL daraxti nima ekanligi haqida batafsil ma’lumot uchun ushbu sahifaga qarang.

AVL daraxti — o‘zini o‘zi muvozanatlaydigan ikkilik daraxt turi.

AVL daraxtiga tugun qo‘shilgan yoki undan tugun o‘chirilgan har safar muvozanatni tiklash uchun aylantirish (rotation) kerakmi-yo‘qligini aniqlash maqsadida barcha ajdod tugunlar uchun chap va o‘ng qism daraxtlar balandligidan foydalanib muvozanat koeffitsiyenti hisoblanishi kerak.

Muvozanat koeffitsiyentlarini hisoblashda har bir tugunning balandligini (barg tugunlargacha pastga tushib) hisoblamaslik uchun har bir tugunda uning qism daraxti balandligi saqlanadi.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

Bu tugunning muvozanat koeffitsiyentini topish uchun allaqachon saqlangan o‘ng bola balandligidan allaqachon saqlangan chap bola balandligi ayirilishini anglatadi, boshqa hisob-kitob kerak emas.

AVL daraxtlarida balandlikni saqlash memoizatsiyaning bir shaklidir, chunki qiymatlar ularni qayta hisoblamaslik uchun saqlanadi. AVL daraxtlarida balandlik shu tarzda saqlanganda, u kengaytirilgan xususiyat (augmented property) deb ataladi.

Kengaytirilgan xususiyat — elementning saqlanishi shart bo‘lmagan, lekin amallarni samaraliroq qilish uchun saqlanadigan xususiyati.

Albatta, tugun balandliklari qachondir hisoblanishi kerak, ammo bu faqat qat’iy zarur bo‘lgandagina retracing (orqaga qaytib yangilash) yordamida bajariladi.