অ্যারে ও স্ট্রিংপড়তে ৫ মিনিট লাগবে

ডায়নামিক অ্যারে (Dynamic Array)

এমন একটা অ্যারে, যার জায়গা ফুরিয়ে গেলে নিজে নিজেই বড় হয়ে যায়

access by index: তাৎক্ষণিক · O(1)append (amortized): তাৎক্ষণিক · O(1)insert/delete middle: স্লো · O(n)search: স্লো · O(n)

মনে আছে সাধারণ বা স্ট্যাটিক অ্যারের কথা? ডিমের বাক্সের মতো, যার সাইজ আগে থেকেই ফিক্স করা থাকে? ডায়নামিক অ্যারে ঠিক এই সমস্যাটাই সমাধান করে। এটা বলতে পারেন একটা স্মার্ট স্ট্যাটিক অ্যারে, যেটা বোঝে কখন তার ডিমের বাক্সটা ভর্তি হয়ে গেছে, আর তখন সে নিজে নিজেই বড় একটা বাক্স কিনে নিয়ে আসে।

ভেতরের ইঞ্জিনের গঠন দেখলে, এটা আসলে একটা সাধারণ স্ট্যাটিক অ্যারে ছাড়া আর কিছুই না। কিন্তু ডায়নামিক অ্যারে সবসময় দুটো জিনিসের হিসেব রাখে:

ক্যাপাসিটি (Capacity) মোট জায়গা: ভেতরের স্ট্যাটিক অ্যারেটাতে মোট কতগুলো বক্স বা স্লট আছে।
সাইজ (Size) বা লেন্থ (Length): বর্তমানে আপনি তার মধ্যে ঠিক কতগুলো স্লট ব্যবহার করছেন বা ভর্তি করেছেন।

যখন সাইজ আর ক্যাপাসিটি সমান হয়ে যায়, তার মানে অ্যারেটা পুরোপুরি ভর্তি। এরপরও যদি আপনি নতুন কিছু ঢোকাতে চান, তখন ডায়নামিক অ্যারে একটা জাদুকরী কাজ করে, যাকে বলা হয় রিসাইজ (resize) বা সাইজ বাড়ানো।

◈ Watch dynamic resizing

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

রিসাইজ করার জাদু

অ্যারে যখন ভর্তি হয়ে যায়, তখন সে চাইলেই হুট করে পাশের জায়গাটা দখল করে বড় হতে পারে না — কারণ কে জানে, হয়তো ওই জায়গাটা অন্য কোনো প্রোগ্রাম ব্যবহার করছে! এর বদলে, তাকে পুরো জিনিসপত্র নিয়ে একটু বড় নতুন কোনো জায়গায় শিফট করতে হয়। পুরো প্রসেসটা নিচে দেওয়া হলো:

Create: প্রথমে একদম নতুন আরেকটা স্ট্যাটিক অ্যারে মেমোরিতে তৈরি করা হয়, যার সাইজ পুরোনোটার ঠিক দ্বিগুণ (Double)।
Copy: পুরোনো অ্যারে থেকে একটা একটা করে ডেটা কপি করে নতুন অ্যারেতে এনে বসানো হয়।
Add: এবার যে নতুন সংখ্যা বা জিনিসটা আপনি ঢোকাতে চেয়েছিলেন, সেটা নতুন অ্যারের প্রথম খালি জায়গায় বসিয়ে দিন।
Delete: সবশেষে পুরোনো বা ছোট অ্যারেটাকে মেমোরি থেকে মুছে ফেলা হয়, যাতে কম্পিউটার ওই স্টোরেজ অন্য কাজে লাগাতে পারে।

এই যে সবগুলো ডেটা কপি করে আনা হলো, এর জন্য O(n) সময় লাগে। এটা একটু ধীর গতির আর ব্যয়বহুল কাজ!

অ্যামোর্টাইজড টাইম (Amortized Time — 'প্রায় সবসময় ফাস্ট' থাকার নিয়ম)

আপনার মনে হতে পারে, এই যে বারবার রিসাইজ আর কপি করতে হয়, এর মানে ডায়নামিক অ্যারেতে শেষে ডেটা যোগ করা (append) তো তাহলে অনেক স্লো কাজ! কিন্তু আসল মজাটা হলো, প্রতিবার আমরা সাইজ দ্বিগুণ বা ডাবল করে দিচ্ছি, ফলে এই রিসাইজের কাজটা খুব রেয়ার বা কালেভদ্রে করতে হয়।

ধরুন আপনি ৮টা সংখ্যা ঢোকালেন, তাহলে আপনাকে রিসাইজ করতে হবে ১ম, ২য়, ৩য়, ৫ম আর ৯ম সংখ্যাটা ঢোকানোর সময়। কিন্তু অ্যারে যখন অনেক বড় হয়ে যাবে (ধরুন ১ মিলিয়ন সংখ্যা আছে), তখন পরের বার রিসাইজ করার আগে আপনাকে আরও নতুন ১ মিলিয়ন সংখ্যা বিনাধাক্কায় ঢোকাতে দেওয়া হবে! তাই বেশিরভাগ সময়ই ডেটা ঢোকানোটা একদম তাৎক্ষণিক বা O(1) অপারেশন। এই কনসেপ্টটাকেই আমরা বলি O(1) amortized time — যার মানে হলো, "মাঝে মাঝে একটু সময় লাগলেও, লম্বা সময়ের গড়ে দেখলে এটা সবসময় O(1) স্পিডেই চলে।"

দ্রষ্টব্য: আজকালকার প্রায় সব আধুনিক প্রোগ্রামিং ল্যাঙ্গুয়েজ ডিফল্ট হিসেবে ডায়নামিক অ্যারে ব্যবহার করে। পাইথনের list, জাভার ArrayList, জাভাস্ক্রিপ্টের Array, আর C++ এর std::vector — এগুলোর ভেতরে তাকালে দেখবেন সবই আসলে ডায়নামিক অ্যারে!