আজকাল আমাদেরকে অনেক সময়ই বড় বড় ফাইল নিয়ে প্রসেসিং করে বিভিন্ন রকম ডেটা কালেকশন করতে হয়। যেমন পপুলার কোন ওয়েবসাইটে শুধুমাত্র প্রতিদিনের সার্ভার লগ গুলোই কয়েকশ গিগাবাইট হয়ে যেতে পারে। গিগাবাইট বা টেরাবাইট রেঞ্জের ফাইল নিয়ে কাজ করতে গেলে দেখা যায় একটা মাত্র মেশিনের স্টোরেজ ক্যাপাসিটি বা কম্পিউটিং পাওয়ার যথেষ্ট হয় না। একটা মেশিনে হয় যথেষ্ট হার্ডডিস্ক স্পেস থাকে না, আবার হার্ডডিস্কে স্পেস থাকলেও দেখা যায় র্যামে যথেষ্ট জায়গা থাকেনা, সম্পূর্ণ ফাইল র্যামে লোড করে প্রসেসিং সম্ভব হয় না। "ডিস্ট্রিবিউটেড ফাইল সিস্টেম" এর কাজ হলো একটা ফাইলকে ছোট ছোট অনেকগুলো ভাগ করে বিভিন্ন মেশিনে স্টোর করে রাখা...
বিস্তারিত
ব্যাকএন্ড ইঞ্জিনিয়ারিং: কনসিস্টেন্ট হ্যাশিং
কনসিস্টেন্ট হ্যাশিং সার্ভারে লোড ব্যালেন্স করার একটি অ্যালগরিদম। এটা ব্যবহার করে নিশ্চিত করা হয় ডিস্ট্রিবিউটেড সিস্টেমে নতুন সার্ভার যোগ করলে বা কোন সার্ভার ডাউন হয়ে গেলে অন্যান্য সার্ভারের উপর যতটা সম্ভব কম প্রভাব পরে। এই লেখায় আমি বেসিক হ্যাশিং নিয়ে তেমন আলোচনা করবো না, আমি আলোচনা করবো কনসিস্টেন্ট হ্যাশিং কিভাবে কাজ করে এবং কি ধরণের সমস্যা সমাধান করতে এটা কাজে লাগে সেটা নিয়ে।
শুরুতেই অ্যালগরিদম বর্ণনা করা আগে আমি কিছু ব্যাকগ্রাউন্ড দিয়ে শুরু করবো যাতে তুমি বুঝতে পারো ঠিক কোন সমস্যা সমাধান করার জন্য এটা ব্যবহার করা হয়। কনসিস্টেন্ট হ্যাশিং এর একটা খুবই কমন ব্যবহার হলো ডিস্ট্রিবি...
বিস্তারিত
ব্যাকএন্ড ইঞ্জিনিয়ারিং: লগ-স্ট্রাকচার্ড-ট্রি
আজকে কথা বলবো ডেটাবেজ বানাতে ব্যবহার করা হয় এমন একটি ডেটা স্ট্রাকচার নিয়ে। সাধারণত ডেটাবেসের সাথে আমাদের পরিচয় হয় Sql ধরণের ট্রানজেকশনাল ডেটাবেজ দিয়ে, যেমন MySQL, PostGreSQL। এসব ডেটাবেসে বি+ ট্রি (B+ Tree) ব্যবহার করে ডেটা সংরক্ষণ করা হয়। এই লেখায় আমি আলোচনা করবো ডেটাবেজ তৈরি করতে জনপ্রিয় আরেকটি ডেটা স্ট্রাকচার নিয়ে যার নাম লগ-স্ট্রাকচার্ড-ট্রি বা সংক্ষেপে LSM Tree।
আগেই বলে নেই, এটা প্রোগ্রামিং কনটেস্টে ব্যবহার করার মত কোন ডেটা স্ট্রাকচার না। তবে সফটওয়্যার ইঞ্জিনিয়ারারদের কেন ডেটা স্ট্রাকচার, অ্যালগরিদম এবং হার্ডওয়্যার নিয়ে জানা দরকার তার একটা উদাহরণ এই LSM Tree।
ব্যাকএন্ড ইঞ্জিন...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং ৯ (ট্রি, মিনিমাম ভারটেক্স কভার)
(সবগুলো পর্ব) ডাইনামিক প্রোগ্রামিং দিয়ে ট্রি(Tree) সংক্রান্ত অনেক সমস্যার সমাধান করা যায়। সাধারণ গ্রাফে পলিনোমিয়াল টাইমে সমাধান করা যায় না এমন অনেক প্রবলেম ট্রি গ্রাফে সহজেই ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায় কারণ ট্রি তে কোন সাইকেল থাকে না। এই পর্বে আমরা সেরকমই একটা ক্লাসিক প্রবলেম দেখবো যার নাম মিনিমাম ভারটেক্স কভার।
ধরা যাক একটি শহরে কিছু রাস্তা আছে, এখন প্রতি রাস্তায় মোড় বা জাংশনে আমরা পাহারাদার বসাতে চাই। কোনো মোড়ে পাহারাদার বসালে সে মোড়ের সাথে যুক্ত রাস্তাগুলো একাই পাহারা দিতে পারে। এখন তোমাকে বলতে হবে সব কয়টা রাস্তা পাহারা দিতে নূন্যতম কয়জন পাহারাদার দরকার?
একট...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং ৮ (বিটমাস্ক, ট্রাভেলিং সেলসম্যান)
(সবগুলো পর্ব) বিটমাস্ক ব্যবহার করে বেশ কিছু NP-Complete/NP-Hard প্রবলেম সলভ করা যায়। বিটমাস্কের ব্যবহার জানা থাকলে এটা তেমন কঠিন কিছু নয়। এই লেখা পড়ার আগে তোমার জানা লাগবে কিভাবে বিট ম্যানিপুলেশন করতে হয়, সেজন্য তুমি এই লেখাটা পড়তে পারো। এই প্রবলেম সলভ করতে গ্রাফ থিওরি জানার দরকার নেই।
আজকে আমরা বিখ্যাত ট্রাভেলিং সেলসম্যান প্রবলেম বিটমাস্ক দিয়ে সলভ করবো। প্রবলেমটা হলো তোমাকে কিছু শহর এবং রাস্তা একটা গ্রাফ হিসাবে দেয়া আছে। তোমাকে প্রথম শহর থেকে শুরু করে সবগুলো শহর ঠিক একবার করে ভ্রমণ করে প্রথম শহরে ফিরে আসতে হবে। প্রশ্ন হলো সর্বনিম্ন কত দূরত্ব অতিক্রম করে তুমি কাজটা করতে পারব...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং ৭ (ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন)
(সবগুলো পর্ব) ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন আরেকটা ক্লাসিক ডাইনামিক প্রোগ্রামিং প্রবলেম যেখানে আমাদেরকে বের করতে হবে কিছু ম্যাট্রিক্সকে কিভাবে সবথেকে কম অপারেশন ব্যবহার করে গুণ করা যাবে। ডিভাইড এন্ড কনকোয়ার পদ্ধতির খুবই চমৎকার একটা উদাহরণ এই প্রবলেমটা।
আমি আশা করবো ম্যাট্রিক্স কিভাবে গুণ করতে হয় সেটা সবাই জানো, আমি সেটা নিয়ে বিস্তারিত বলবো না। আমি খালি কয়েকটা প্রোপার্টির কথা মনে করিয়ে দিতে চাই। ধরা যাক আমাদের দুটি ম্যাট্রিক্স আছে $A_{1}$ এবং $A_{2}$ এবং তাদের ডাইমেনশন হলো $(r_{1} \times c_{1})$ এবং $(r_{2} \times c_{2})$।
$A_{1}$ এবং $A_{2}$ গুণ করা যাবে শুধুমাত্র যদি $...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং ৬ (সাবসেট সাম, কম্বিনেটরিক্স, ডিসিশন প্রবলেম)
আগের পর্বগুলোয় যেসব প্রবলেম দেখেছি তার মধ্যে ফিবোনাচ্চি সবগুলোতেই আমাদেরকে কিছু না কিছু ম্যাক্সিমাইজ বা মিনিমাইজ করতে হয়। এগুলো ছাড়া ডাইনামিক প্রোগ্রামিং এর আরো কিছু ব্যবহার আছে, একটা হলো কোন একটা কাজ কত ভাবে করা যায় সেটা বের করা, আরেকটা হলো ডিসিশন প্রবলেম সলভ করা (অর্থাৎ কোন একটা কাজ করা যাবে কি যাবে না সেটা বের করা)।
শুরুতেই দেখবো সাবসেট সাম প্রবলেম। এই প্রবলেমটা অনেকটাই কয়েন চেঞ্জ প্রবলেমের মত, আশা করবো তুমি কয়েন চেঞ্জ নিয়ে লেখাটা পড়ে ফেলেছো, কারণ এবার আমি আগের মত এত বিস্তারিত বর্ণনা করবো না।
সাবসেট সাম
তোমাকে একটা ইন্টিজার অ্যারে $C$ দেয়া আছে এবং একটা ভ্যালু $W$ দে...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং ৫ (কয়েন চেঞ্জ, ০-১ ন্যাপস্যাক)
(আগের পর্ব) আজকে আরো দুটি ক্লাসিকাল ডাইনামিক প্রোগ্রামিং প্রবলেম শিখবো। প্রথমটা হলো কয়েন চেঞ্জ। প্রবলেমটার নাম শুনেই বোঝা যাচ্ছে এটা টাকা ভাংতি করা নিয়ে প্রবলেম, তোমাকে সবথেকে কম সংখ্যক কয়েন ব্যবহার করে নির্দিষ্ট পরিমাণ টাকা ভাংতি করতে হবে।
মনে করো তোমার কাছে $n$ টা ভিন্ন ভিন্ন কয়েন আছে, কয়েনগুলোর ভ্যালুকে $C_{0}, C_{1}...C{n-1}$ দিয়ে প্রকাশ করা যায়। আর তোমাকে একটা অ্যামাউন্ট দেয়া আছে $W$। এখন তোমাকে বলতে সর্বনিম্ন কয়টা কয়েন ব্যবহার করে তুমি $W$ অ্যামাউন্টটা বানাতে পারবে। প্রতিটা ভ্যালুর কয়েন আছে মাত্র ১টা করে।
একটা উদাহরণ দেখি। ধরা যাক কয়েনগুলোর ভ্যালু হলো $C = \...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং ৪ (লংগেস্ট কমন সাবসিকোয়েন্স)
আগের পর্ব গুলোতে আমরা যেসব প্রবলেম দেখে এসেছি সেগুলোর সাবপ্রবলেমের স্টেট ছিল মাত্র ১টা। এইবার আমরা আরেকটু জটিল সমস্যা সমাধান করবো যার নাম লংগেস্ট কমন সাবসিকোয়েন্স বা LCS। এটা শেখার পরে আমি এডিট ডিসটেন্স প্রবলেম নিয়ে অল্প কিছু কথা বলবো এবং তোমার কাজ হবে সেটা নিজে নিজে সমাধান করা।
এই প্রবলেমে তোমাকে দুটি স্ট্রিং দেয়া থাকবে $S$ এবং $W$। তোমাকে তাদের মধ্যে লংগেস্ট কমন সাবসিকোয়েন্স এর দৈর্ঘ্য বের করতে হবে। সাবসিকোয়েন্সের সংজ্ঞাটা মনে করিয়ে দেই, একটা স্ট্রিং থেকে কিছু ক্যারেক্টার মুছে দিলে যা বাকি থাকে সেটাই স্ট্রিংটা সাবসিকোয়েন্স। একটা স্ট্রিং এর $2^{n}$ টা সাবসিকোয়েন্স থাকতে পার...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং-৩ (লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স, পাথ প্রিন্টিং)
আমরা এরই মধ্যে ডাইনামিক প্রোগ্রামিং এর বেসিক শিখে গিয়েছি, আমরা ফিবোনাচ্চি এবং DAG এ শর্টেস্ট পাথ বের করতে পারি। এবার আমরা শিখবো Longest Increasing Subsequence বা LIS বের করা। এতদিন আমরা শুধু অপটিমাল সলিউশনটা বের করতে শিখেছি, কোন পথ ধরে সলিউশনে পৌছাতে হয় সেটা বের করা শিখিনি। এবার আমরা নেক্সট-পয়েন্টার ব্যবহার করে সেটা বের করাও শিখবো।
ধরা যাক আমাদের নিচের ছবির মতো একটা অ্যারে আছে যার নাম $A$।
একটা অ্যারের সাবসিকোয়েন্স বলতে বুঝায় অ্যারে থেকে কিছু এলিমেন্ট মুছে দিলে বাকি যে সিকোয়েন্সটা থাকে সেটা। এলিমেন্টগুলোর অর্ডারিং পরিবর্তন করা যাবে না। $n$ সাইজের একটা অ্যারের $2^{n}$ টি স...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং-২ (শর্টেস্ট পাথ)
আগের পর্বে আমরা ফিবোনাচ্চি নাম্বার নিয়ে আলোচনা করেছি। আমরা দেখেছি কিভাবে ডাইনামিক প্রোগ্রামিং ব্যবহার করে রিকার্সিভলি এবং ইটারেটিভলি ফিবোনাচ্চি সংখ্যা জেনারেট করা যায়। এই পর্বে আমরা কথা বলবো শর্টেস্ট পাথ প্রবলেম নিয়ে এবং সেটা নিয়ে আলোচনা করার সময় ডিপির কিছু নতুন প্রোপার্টি নিয়ে জানবো।
যদিও শর্টেস্ট পাথ গ্রাফ থিওরির একটা প্রবলেম, এই লেখা বুঝতে গ্রাফ নিয়ে না জানলেও চলবে।
মনে করো আমাদেরকে এক শহর থেকে অন্য শহরে যাবার শর্টেস্ট পাথ খুজে বের করতে হবে। শহর আছে মোট $n$ টি। $0$ হলো প্রথম শহর, এবং $n - 1$ হলো শেষ শহর। কোন শহর থেকে কোন শহরে সরাসরি যাওয়া যায় এবং শহরগুলোর মধ্যে দুরত...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং – ১ (ফিবোনাচ্চি)
ডাইনামিক প্রোগ্রামিং নামটা শুনতে একটু কঠিন মনে হলেও এর পিছনে কনসেপ্টটা বেশ সহজ। ডাইনামিক প্রোগ্রামিং কে এক কথায় বর্ণনা করতে গেলে বলা যায় - একটা সমস্যাকে ছোট ছোট ভাগ করে সাব-প্রবলেমগুলো সমাধান করবো তবে একই সাবপ্রবলেম একবারের বেশি সমাধান করবো না। মোটা দাগে বলতে গেলে এটাই ডাইনামিক প্রোগ্রামিং। তবে কখন একটা প্রবলেমকে ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যাবে সেটা বুঝতে একটু অভিজ্ঞতা প্রয়োজন। তো এই সিরিজে আমরা দেখবো ডাইনামিক প্রোগ্রামিং কি এবং কিছু কমন সমস্যা যেগুলো ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়।
ডাইনামিক প্রোগ্রামিং বা ডিপি টার্মটা একটু কনফিউজিং কারণ 'ডাইনামিক' শব্...
বিস্তারিত
প্রোবাবিলিস্টিক ডাটা স্ট্রাকচার: কাউন্ট-মিন স্কেচ
কিছুদিন আগে একটা আর্টিকেল লিখেছিলাম ব্লুম ফিল্টার নিয়ে। কাউন্ট-মিন স্কেচ অনেকটা সেরকমই একটা প্রোবালিস্টিক ডাটা স্ট্রাকচার। এরা কাজও করে অনেকটা একইভাবে যদিও কাজের ধরণ এবং ব্যবহার সম্পূর্ণ আলাদা। অ্যালগরিদম জানা থাকলে কম রিসোর্স খরচ করেই কিভাবে অনেক ডাটা হ্যান্ডেল করা যায় তার একটা চমৎকার উদাহরণ কাউন্ট-মিন স্কেচ। ব্লুম ফিল্টার কিভাবে কাজ করে সেটা না জানলেও তুমি এই লেখাটা বুঝতে পারবে।
ধরো তোমাকে একটা স্ট্রিং এর অ্যারের দেয়া আছে। তোমাকে বলতে হবে অ্যারেতে কোন স্ট্রিং কতবার আছে, অর্থাৎ স্ট্রিংগুলোর ফ্রিকোয়ন্সি বের করতে হবে।
উপরের ছবিতে একটা উদাহরণ দেখানো হয়েছে। ইনপুট অ্যারেতে ৮টা...
বিস্তারিত
ব্যাকএন্ড ইঞ্জিনিয়ারিং: এল-আর-ইউ ক্যাশ
আজকে আমরা জানবো ক্যাশিং কি এবং এল-আর-ইউ ক্যাশ কিভাবে কাজ করে। তুমি যদি ক্যাশিং সম্পর্কে আগে থেকেই জানো তাহলে প্রথম অংশটা দ্রুত পড়ে পরের অংশে চলে যেতে পারো।
ধরা যাক তুমি একটি অ্যান্ড্রয়েড অ্যাপ তৈরি করছো। অ্যাপের ইউজারদের তুমি ৩টা রকমের লেভেল অ্যাসাইন করেছো, প্লাটিনাম, গোল্ড আর সিলভার। যখনই কোনো ইউজার অ্যাপ চালু করে তখনই তোমার ডেটাবেসে ইউজারের লেভেল চেক করতে হয়। তোমার অ্যাপ এ ইউজার আছে এক লাখ এবং প্রতি ঘন্টায় কয়েক হাজার ইউজার অ্যাপটি ব্যবহার করে। একসময় তুমি দেখলে ডাটাবেজের রিকুয়েস্ট খুব বেশি বেড়ে যাচ্ছে এবং পেজ লোড স্লো হয়ে যাচ্ছে। এই সমস্যার সমাধান হলো কিছু ইউজারের ...
বিস্তারিত