Rope data structure
XOR বাইনারি অপারেশনটা দিয়ে বেশ মজার মজার সব কাজ করা যায় যেগুলো প্রথম দেখায় ম্যাজিকের মত মনে হয়, কিন্তু একটু ভিতরের দিকে তাকালেই বোঝা যায় কি হচ্ছে। যেমন ধরা যাক গেম থিওরির কথা, তোমরা যারা নিম গেমের সাথে পরিচিত তারা জান যে কিভাবে শুধু XOR অপারেশন দিয়ে বের করে ফেলা যায় খেলায় কে জিতবে বা হারবে। প্রোগ্রামিং কনটেস্টে XOR রিলেটেড প্রবলেম খুবই কমন, আমি নিজেই বেশ কিছু কনটেস্টে এধরণের প্রবলেম সেট করেছি। আজকে দেখাবো কিভাবে XOR ব্যবহার করে লিংকড লিস্টের মেমরি কমিয়ে ফেলা যায়। বাস্তবে তুমি কখনোই হয়তো এরকম লিংকড লিস্ট লিখবে না, কিন্তু এই লেখাটা পড়ার পর XOR এর প্রোপার্টিগুলোর ব্যবহার নিয়ে তোমার ধা...
বিস্তারিতব্যাকএন্ড ইঞ্জিনিয়ারিং: ডিস্ট্রিবিউটেড ফাইল সিস্টেম
আজকাল আমাদেরকে অনেক সময়ই বড় বড় ফাইল নিয়ে প্রসেসিং করে বিভিন্ন রকম ডেটা কালেকশন করতে হয়। যেমন পপুলার কোন ওয়েবসাইটে শুধুমাত্র প্রতিদিনের সার্ভার লগ গুলোই কয়েকশ গিগাবাইট হয়ে যেতে পারে। গিগাবাইট বা টেরাবাইট রেঞ্জের ফাইল নিয়ে কাজ করতে গেলে দেখা যায় একটা মাত্র মেশিনের স্টোরেজ ক্যাপাসিটি বা কম্পিউটিং পাওয়ার যথেষ্ট হয় না। একটা মেশিনে হয় যথেষ্ট হার্ডডিস্ক স্পেস থাকে না, আবার হার্ডডিস্কে স্পেস থাকলেও দেখা যায় র্যামে যথেষ্ট জায়গা থাকেনা, সম্পূর্ণ ফাইল র্যামে লোড করে প্রসেসিং সম্ভব হয় না। "ডিস্ট্রিবিউটেড ফাইল সিস্টেম" এর কাজ হলো একটা ফাইলকে ছোট ছোট অনেকগুলো ভাগ করে বিভিন্ন মেশিনে স্টোর করে রাখা...
বিস্তারিতঅ্যালগরিদম কমপ্লেক্সিটি(বিগ “O” নোটেশন)
তুমি যখন একটা অ্যালগরিদমকে কোডে ইমপ্লিমেন্ট করবে তার আগে তোমার জানা দরকার অ্যালগরিদমটি কতটা কার্যকর। অ্যালগোরিদম লেখার আগে নিজে নিজে কিছু প্রশ্নের উত্তর দিতে হবে,যেমন: ১. আমার অ্যালগোরিদম কি নির্ধারিত সময়ের মধ্যে ফলাফল এনে দিবে? ২. সর্বোচ্চ কত বড় ইনপুটের জন্য আমার অ্যালগোরিদম কাজ করবে? ৩. আমার অ্যালগোরিদম কতখানি মেমরি ব্যবহার করছে? আমরা অ্যালগোরিদমের কমপ্লেক্সিটি বের করে প্রথম দুটি প্রশ্নের উত্তর দিতে পারি। একটি অ্যালগরিদম যতগুলো "ইনস্ট্রাকশন" ব্যবহার করে কাজ করে সেটাই সোজা কথাই সেই অ্যালগোরিদমের কমপ্লেক্সিটি। দুটি নম্বর গুণ করা একটি ইনস্ট্রাকশন, আবার একটি লুপ ১০০ বার চললে সেখান...
বিস্তারিতব্যাকএন্ড ইঞ্জিনিয়ারিং: কনসিস্টেন্ট হ্যাশিং
কনসিস্টেন্ট হ্যাশিং সার্ভারে লোড ব্যালেন্স করার একটি অ্যালগরিদম। এটা ব্যবহার করে নিশ্চিত করা হয় ডিস্ট্রিবিউটেড সিস্টেমে নতুন সার্ভার যোগ করলে বা কোন সার্ভার ডাউন হয়ে গেলে অন্যান্য সার্ভারের উপর যতটা সম্ভব কম প্রভাব পরে। এই লেখায় আমি বেসিক হ্যাশিং নিয়ে তেমন আলোচনা করবো না, আমি আলোচনা করবো কনসিস্টেন্ট হ্যাশিং কিভাবে কাজ করে এবং কি ধরণের সমস্যা সমাধান করতে এটা কাজে লাগে সেটা নিয়ে। শুরুতেই অ্যালগরিদম বর্ণনা করা আগে আমি কিছু ব্যাকগ্রাউন্ড দিয়ে শুরু করবো যাতে তুমি বুঝতে পারো ঠিক কোন সমস্যা সমাধান করার জন্য এটা ব্যবহার করা হয়। কনসিস্টেন্ট হ্যাশিং এর একটা খুবই কমন ব্যবহার হলো ডিস্ট্রিবি...
বিস্তারিতব্যাকএন্ড ইঞ্জিনিয়ারিং: লগ-স্ট্রাকচার্ড-ট্রি
আজকে কথা বলবো ডেটাবেজ বানাতে ব্যবহার করা হয় এমন একটি ডেটা স্ট্রাকচার নিয়ে। সাধারণত ডেটাবেসের সাথে আমাদের পরিচয় হয় Sql ধরণের ট্রানজেকশনাল ডেটাবেজ দিয়ে, যেমন MySQL, PostGreSQL। এসব ডেটাবেসে বি+ ট্রি (B+ Tree) ব্যবহার করে ডেটা সংরক্ষণ করা হয়। এই লেখায় আমি আলোচনা করবো ডেটাবেজ তৈরি করতে জনপ্রিয় আরেকটি ডেটা স্ট্রাকচার নিয়ে যার নাম লগ-স্ট্রাকচার্ড-ট্রি বা সংক্ষেপে LSM Tree। আগেই বলে নেই, এটা প্রোগ্রামিং কনটেস্টে ব্যবহার করার মত কোন ডেটা স্ট্রাকচার না। তবে সফটওয়্যার ইঞ্জিনিয়ারারদের কেন ডেটা স্ট্রাকচার, অ্যালগরিদম এবং হার্ডওয়্যার নিয়ে জানা দরকার তার একটা উদাহরণ এই LSM Tree। ব্যাকএন্ড ইঞ্জিন...
বিস্তারিতডাইনামিক প্রোগ্রামিং ৯ (ট্রি, মিনিমাম ভারটেক্স কভার)
(সবগুলো পর্ব) ডাইনামিক প্রোগ্রামিং দিয়ে ট্রি(Tree) সংক্রান্ত অনেক সমস্যার সমাধান করা যায়। সাধারণ গ্রাফে পলিনোমিয়াল টাইমে সমাধান করা যায় না এমন অনেক প্রবলেম ট্রি গ্রাফে সহজেই ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায় কারণ ট্রি তে কোন সাইকেল থাকে না। এই পর্বে আমরা সেরকমই একটা ক্লাসিক প্রবলেম দেখবো যার নাম মিনিমাম ভারটেক্স কভার। ধরা যাক একটি শহরে কিছু রাস্তা আছে, এখন প্রতি রাস্তায় মোড় বা জাংশনে আমরা পাহারাদার বসাতে চাই। কোনো মোড়ে পাহারাদার বসালে সে মোড়ের সাথে যুক্ত রাস্তাগুলো একাই পাহারা দিতে পারে। এখন তোমাকে বলতে হবে সব কয়টা রাস্তা পাহারা দিতে নূন্যতম কয়জন পাহারাদার দরকার? একট...
বিস্তারিতডাইনামিক প্রোগ্রামিং ৮ (বিটমাস্ক, ট্রাভেলিং সেলসম্যান)
(সবগুলো পর্ব) বিটমাস্ক ব্যবহার করে বেশ কিছু NP-Complete/NP-Hard প্রবলেম সলভ করা যায়। বিটমাস্কের ব্যবহার জানা থাকলে এটা তেমন কঠিন কিছু নয়। এই লেখা পড়ার আগে তোমার জানা লাগবে কিভাবে বিট ম্যানিপুলেশন করতে হয়, সেজন্য তুমি এই লেখাটা পড়তে পারো। এই প্রবলেম সলভ করতে গ্রাফ থিওরি জানার দরকার নেই। আজকে আমরা বিখ্যাত ট্রাভেলিং সেলসম্যান প্রবলেম বিটমাস্ক দিয়ে সলভ করবো। প্রবলেমটা হলো তোমাকে কিছু শহর এবং রাস্তা একটা গ্রাফ হিসাবে দেয়া আছে। তোমাকে প্রথম শহর থেকে শুরু করে সবগুলো শহর ঠিক একবার করে ভ্রমণ করে প্রথম শহ
