অ্যাডভান্সড / স্পেশালপড়তে ৬ মিনিট লাগবে

LRU ক্যাশ (LRU Cache)

যেটা বেশি দরকার সেটা হাতের কাছে রাখুন, আর যেটা ভুলে গেছ সেটা ফেলে দিন

get: O(1)put: O(1)space: O(ক্যাপাসিটি বা ধারণক্ষমতা)

ধরুন আপনার পড়ার টেবিলে মাত্র ৫টা বই রাখার জায়গা আছে। যখন আপনার ৬ নম্বর বইটা দরকার হয়, তখন আপনি টেবিল থেকে এমন একটা বই সরিয়ে ফেলেন যেটা আপনি সবচেয়ে বেশি দিন ধরে পড়েননি বা ধরেননি, যাতে নতুন বইটার জায়গা হয়। এটাই হলো লিস্ট রিসেন্টলি ইউজড (Least Recently Used বা LRU) নিয়ম — আর আমাদের কম্পিউটার, মোবাইল, ব্রাউজার থেকে শুরু করে ডেটাবেস পর্যন্ত সবাই মেমোরি বাঁচানোর জন্য এই একই পদ্ধতি ব্যবহার করে।

একটা LRU ক্যাশ (Cache) মূলত দুটো কাজ করে:

get(key) — জিনিসটা যদি টেবিলে (ক্যাশে) থাকে তবে সেটা দেয়; আর সাথে সাথে ওটাকে 'সদ্য ব্যবহৃত' বা সবচেয়ে দরকারি হিসেবে মার্ক করে রাখে।
put(key, value) — নতুন জিনিস টেবিলে রাখে; যদি টেবিল পুরো ভর্তি থাকে, তবে সবচেয়ে পুরোনো বা অবহেলিত জিনিসটাকে আগে ফেলে দিয়ে জায়গা করে নেয়।

এই দুটো কাজই চোখের পলকে বা O(1) সময়ে হতে হবে। আর এটা করার জন্য আমাদের দুটো ডেটা স্ট্রাকচারকে একসাথে মেলাতে হয়: একটা ডাবলি লিংকড লিস্ট (Doubly linked list) এবং একটা হ্যাশ ম্যাপ (Hash map)।

◈ দেখুন কীভাবে দরকারি জিনিস লিস্টের সামনে চলে আসে, আর অবহেলিত জিনিস পেছন থেকে ছিটকে পড়ে

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

দুই ডেটা স্ট্রাকচারের যুগলবন্দী

ডাবলি লিংকড লিস্ট (Doubly linked list)-এর কাজ হলো জিনিসগুলোকে তাদের ব্যবহারের সময়ের ওপর ভিত্তি করে সিরিয়ালে সাজিয়ে রাখা। লিস্টের হেড বা মাথায় থাকে সবচেয়ে তাজা বা দরকারি জিনিসটা; আর টেইল বা লেজে থাকে সবচেয়ে পুরোনো বা অবহেলিত জিনিসটা। যেহেতু এটা ডাবলি লিংকড লিস্ট, তাই পেছনের বা মাঝখানের কাউকেও টেনে হেডে আনতে, অথবা একদম পেছনের লেজকে কেটে ফেলে দিতে কোনো সময়ই (O(1)) লাগে না।

হ্যাশ ম্যাপ (Hash map)-এর কাজ হলো প্রতিটা জিনিসের নাম বা 'key' দিয়ে সরাসরি লিংকড লিস্টের ওই নির্দিষ্ট ঠিকানা বা নোডটাকে মনে রাখা। এর ফলে কোনো কিছু খুঁজতে হলে লিস্টের শুরু থেকে একটা একটা করে চেক করতে হয় না — বরং O(1) স্পিডে সোজা ওই জিনিসের ঘরে ঢুকে যানয়া যায়।

get(key) বা খোঁজা

হ্যাশ ম্যাপে খুঁজুন জিনিসটা আছে কি না। না থাকলে -1 বা 'নেই' বলে দিন।
যদি থাকে, তবে লিস্টের ওই নোডটাকে টেনে একদম সামনে বা হেডে (Head) নিয়ে আসুন (যাতে প্রমাণ হয় যে এটা এখনই ব্যবহার হলো)।
তারপর জিনিসটা বা ভ্যালুটা দিয়ে দিন।

put(key, value) বা রাখা

যদি জিনিসটা আগে থেকেই থাকে, তবে তার মান আপডেট করুন এবং তাকে টেনে সামনে (Head) নিয়ে আসুন।
যদি জিনিসটা নতুন হয়: নতুন একটা নোড বানান, সেটাকে সামনে (Head) বসান, এবং হ্যাশ ম্যাপে তার ঠিকানা সেভ করে রাখুন।
এখন যদি দেখা যায় ক্যাশের সাইজ তার ক্ষমতার (Capacity) বাইরে চলে গেছে, তবে লিস্টের একদম পেছনে বা লেজে (Tail) যে অবহেলিত নোডটা আছে, তাকে ঘাড় ধাক্কা দিয়ে বের করে দিন এবং হ্যাশ ম্যাপ থেকেও তার হিসাব মুছে ফেলুন।

সেন্টিনেল নোড (Sentinel nodes) বা পাহারাদার

কোড পরিষ্কার রাখার জন্য দুই মাথায় দুটো নকল বা ডামি নোড বসিয়ে দেওয়া হয় — সামনে একটা পার্মানেন্ট head পাহারাদার, আর পেছনে একটা tail পাহারাদার। আসল ডেটাগুলো এই দুজনের মাঝখানে থাকে। এতে করে যদি লিস্ট ফাঁকাও হয়ে যায়, তবুও আমাদের কোড null-pointer এর খেয়ে ক্র্যাশ করে না।

pseudocode

head ↔ [A] ↔ [B] ↔ [C] ↔ tail
(সদ্য ব্যবহৃত)        (সবচেয়ে পুরোনো, পরেরবার একেই ফেলা হবে)

দ্রষ্টব্য: Python-এ collections মডিউলের OrderedDict আসলে ভেতরে ভেতরে এই LRU ক্যাশ কনসেপ্টটাই ব্যবহার করে। তবে ইন্টারভিউতে আপনাকে এই ডিকশনারি (dict) + ডাবলি লিংকড লিস্ট ব্যবহার করে একদম শূন্য থেকে এটা বানাতে বলবে — ইন্টারভিউয়াররা ঠিক এটাই দেখতে চান।