ডাটা স্ট্রাকচার ও অ্যালগরিদম

ডাটা স্ট্রাকচার ও অ্যালগরিদম #

এই বইটি পড়ে আমরা যারা পাইথনের অনেকটাই শিখে ফেলেছি (অন্ততপক্ষে বেসিকটুকু শিখে ফেলেছি), আমাদের এখন নতুন করে ভাবতে বসতে হবে। আমরা কতটুকু জ্ঞান সত্যিকার অর্থেই অর্জন করতে পারলাম? এটা বোঝার একটা সহজ উপায় আছে। উপায়টা হল, বিভিন্ন গাণিতিক সমস্যাকে প্রোগ্রামিংয়ের মাধ্যমে সমাধান করার চেষ্টা করা। কিন্তু কথা হল এত সমস্যা পাব কোথায় আর আমরা যে সমাধানটা বের করব সেটা আসলেই সঠিক সমাধান কিনা সেটা বুঝব কিভাবে? ভয় নাই! এইজন্য রয়েছে অনলাইন জাজ (Online Judge)।

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

শেষের দুইটা মূলত কন্টেস্ট প্লাটফর্ম, মানে এসব জায়গায় প্রোগ্রামিং নিয়ে বিভিন্ন অনলাইন প্রতিযোগীতার আয়োজন করা হয় যাতে সবাই অংশ নিতে পারে। তবে কন্টেস্ট প্লাটফর্ম হলেও এসব জায়গায় সলভ করার মত বহুত প্রব্লেম (প্রাকটিস প্রব্লেম নামে অভিহিত) পাওয়া যায়। কিন্তু আমাদের প্রশ্ন হল, এত এত অনলাইন জাজের ভিড়ে আমরা শুরু করব কোনটা দিয়ে?

শুরুর দিকে আমরা হ্যাকারর‍্যাংক, হ্যাকারআর্থ ও লিটকোড ব্যবহার করতে পারি। হ্যাকারআর্থ ও লিটকোডে বিগিনার, ডাটা স্ট্রাকচার, অ্যালগরিদম এইভাবে প্রব্লেম বিভিন্ন সেকশনে ভাগ করা আছে। অবশ্য পাইথনের ক্ষেত্রে শুরুটা হ্যাকারর‍্যাংক দিয়ে করলে ভাল হয়। কারণ, এর প্রব্লেম সেকশনে পাইথন বিভাগে পাইথনের প্রতিটা টপিকের জন্য আলাদা আলাদা প্রব্লেম আছে। প্রোগ্রামিংয়ের বেসিক শেখা শেষ হয়ে গেলে আমরা সবগুলো টপিকের প্রব্লেম সলভ করার চেষ্টা করতে পারি। যে টপিকের প্রব্লেম সলভ করতে বেশি হিমশিম খাব, বুঝে নেব ঐ টপিকে আমরা দুর্বল। সেজন্য বই/অফিসিয়াল ডকুমেন্টেশন খুলে আবার ঐ টপিকের আগা-গোড়া ভালমত বুঝে বুঝে পড়ব। বুঝতে না পারলে বড় কারো সহায়তা নেব। আজকাল ফেসবুকে প্রোগ্রামিংয়ের বিভিন্ন গ্রুপ রয়েছে যেখানে বাংলা ভাষায় নিজের সমস্যার দ্রুত সমাধান পাওয়া যায়। পাইথন নিয়ে বাংলাদেশের সবচেয়ে বড় প্রোগ্রামিং গ্রুপ হল পাইথন বাংলাদেশ। এই গ্রুপে অত্যন্ত চমৎকারভাবে বাংলা/ইংরেজি ভাষায় নিজেদের সমস্যার কথা সংক্ষেপে কিন্তু পরিপূর্ণভাবে তুলে ধরব আমরা। কেউ না কেউ অবশ্যই আমাদের সমস্যার সমাধান করে দেবেন। তখন তাকে প্রাণঢালা ধন্যবাদ জানিয়ে আবার প্রব্লেম সলভিংয়ে লেগে যাব আমরা।

যাহোক, হ্যাকারর‍্যাংকের প্রব্লেম সেকশনের পাইথন বিভাগের সব প্রব্লেম সলভ করা হয়ে গেলে আমরা লিটকোডে চলে যাব। লিটকোডের প্রব্লেম সেকশানের বিগিনার ক্যাটাগরিতে অনেকগুলো প্রোগ্রামিং প্রব্লেম রয়েছে। সবগুলো একের পর এক শেষ করে ফেলব। আর তারপর লাফ দেব ডাটা স্ট্রাকচারের সমুদ্রে।

ডাটা স্ট্রাকচার #

ডাটা স্ট্রাকচার হল ডাটা অর্গানাইজ ও স্টোর করার স্পেশালাইজড ফরম্যাট যাতে পরবর্তীতে এসব ডাটা সর্বোত্তমভাবে ফিরে পাওয়া যায় ও বিভিন্ন কাজে ব্যবহার করা যায়। কিন্তু আমাদের জন্য ডাটা স্ট্রাকচার কতটা গুরুত্বপূর্ণ?

কম্পিউটারে ডাটা নিয়ে আমরা সাধারণত তিন ধরনের কাজ করি - (১) ডাটা ইনপুট নিই, (২) ডাটা প্রসেস করি ও (৩) ডাটা আউটপুট দিই। আর ডাটা স্ট্রাকচারের উদ্দেশ্য হল এই তিন ধরনের কাজকেই অপটিমাইজ করা বা করতে সাহায্য করা। ধরা যাক, আমরা আমাদের ব্যক্তিগত লাইব্রেরিতে ১০ হাজার বই রাখলাম। বইগুলো যদি আমরা নির্দিষ্ট প্যাটার্ন বা কোন পদ্ধতি অনুসরণ না করে সেলফে রাখি তাহলে সময়কালে একটা বই খুঁজে বের করতে আমাদের কিন্তু ইহজনম পার হয়ে যাবে। এইসব ঝামেলা থেকে মুক্তি পাবার জন্য ডাটা স্ট্রাকচার জানা দরকার আমাদের।

লিস্ট, টাপল, সেট, ডিকশনারি ছিল পাইথনের বিল্ট-ইন ডাটা স্ট্রাকচার। তবে এসবের পাশাপাশি আমাদেরকে আরো কিছু ডাটা স্ট্রাকচার সম্পর্কে জানতে হবে। কমন বা না জানলেই নয় এরকম কিছু ডাটা স্ট্রাকচার হল:

পাইথন ব্যবহার করে ডাটা স্ট্রাকচার শেখার জন্য আমরা এই ফ্রী অনলাইন কোর্সটি করতে পারি। আমেরিকার ইউনিভার্সিটি অব মিশিগানের স্কুল অব ইনফরমেশনের ক্লিনিক্যাল প্রফেসর চার্লস সেভারেন্স এই কোর্সটি পড়িয়েছেন। শিক্ষক হিসেবে তিনি অসাধারণ। সবচেয়ে বড় কথা হল, পড়ানোর ক্ষেত্রে নিজস্ব ভঙ্গিমা রয়েছে তাঁর। কোর্সের ভাষা ইংরেজি। আর কোর্সটি ভিডিও লেকচার হিসেবে দেখতে হবে।

ইংরেজি বইয়ের মধ্যে সবচেয়ে ভাল হল প্রব্লেম সলভিং উইথ অ্যালগরিদমস অ্যান্ড ডাটা স্ট্রাকচারস ইউজিং পাইথন। এই বইটা সম্পূ্র্ণ যে পড়বে তার ডাটা স্ট্রাকচার ও অ্যালগরিদমের যাবতীয় বেসিক ক্লিয়ার হয়ে যাবে। বইটাতে যথাযথ উদাহরণও যোগ করা হয়েছে।

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

বাংলায় ডাটা স্ট্রাকচার ও অ্যালগরিদম শেখার একটা চমৎকার জায়গা হল শাফায়েত আশরাফ ভাইয়ের ব্লগ। যদিও ব্লগে প্রতিটা উদাহরণ সুডো কোডেই বেশি দেখানো হয়েছে তবে একটা টপিক শেখার পর সেটার সুডো কোডকে ফলো করে পাইথনে ইমপ্লিমেন্ট করার চেষ্টা করা যেতেই পারে। (Pseudocode হল একটা অ্যালগরিদম বা প্রোগ্রাম কিভাবে ধাপ-বাই-ধাপ কাজ করে তার সংক্ষিপ্ত বর্ণনা।)

মোটামুটি শেখা হয়ে গেলে হ্যাকারর‍্যাংকের প্রব্লেম সেকশনের ডাটা স্ট্রাকচার বিভাগের প্রতিটা প্রব্লেম সলভ করার চেষ্টা করব আমরা। লিটকোড-এর প্রব্লেম সেকশনে ডাটা স্ট্রাকচারের উপর বেশকিছু প্রব্লেম রয়েছে। এগুলোও সলভ করার চেষ্টা করব।

অ্যালগরিদম #

ইতিমধ্যেই আমরা অ্যালগরিদম শব্দটার সঙ্গে পরিচিত হয়ে গিয়েছি। অ্যালগরিদম হল কতগুলো অপারেশনের সেট। আরো ভালভাবে বলতে গেলে, কোন একটা সমস্যাকে সবচেয়ে উৎকৃষ্ট যে পদ্ধতিতে সমাধান করা যায় তাকেই অ্যালগরিদম বলে। এগুলো বল গণিত দ্বারা প্রমাণিত পদ্ধতি। কোন একটা সমস্যা সাধারণ বুদ্ধি প্রয়োগ করে সমাধান করলে সেটা যতটা ইফেক্টিভ হয়, অ্যালগরিদম ব্যবহার করে সলভ করলে ঢের বেশি ইফেক্টিভ হয়।

সুতরাং মদ্দা কথা হল আমাদেরকে অ্যালগরিদম শিখতে হবে। দুনিয়ায় বহুত অ্যালগরিদম আছে। তবে কমন বা না জানলেই নয়, এরকম কিছু অ্যালগরিদম হল:

  • বাবল সর্ট
  • ইনসার্শন সর্ট
  • সিলেকশন সর্ট
  • কুইক সর্ট
  • হিপ সর্ট
  • ডেপথ ফার্স্ট সার্চ (ডিএফএস)
  • ব্রেথ ফার্স্ট সার্চ (বিএফএস)
  • এ-স্টার (A*) সার্চ
  • হিল ক্লাইম্বিং

পূ্র্বে উল্লেখিত প্রব্লেম সলভিং উইথ অ্যালগরিদমস অ্যান্ড ডাটা স্ট্রাকচারস ইউজিং পাইথন বইটা দিয়েই শেখা শুরু করতে পারি আমরা। বাংলায় শিখতে চাইলে শাফায়েত ভাইয়ের গ্রাফ অ্যালগরিদম বইটা কিনে নেয়া যেতে পারে। তবে সেক্ষেত্রে প্রতিটা অ্যালগরিদম নিজে নিজে পাইথনে ইমপ্লিমেন্ট করার চেষ্টা করতে হবে।

তবে যেখান থেকেই শিখি না কেন প্রব্লেম সলভিংয়ে জোড় দিতে হবে আমাদের। বিভিন্ন কন্টেস্টে অংশ নিতে হবে। বিশেষত আমাদের ভিতর যাদের গুগল বা মাইক্রোসফটের মত বড়সড় কোম্পানিতে চাকরি করার প্রবল ইচ্ছা আছে। এসব কোম্পানি প্রব্লেম সলভিংয়ে সিদ্ধহস্তদের অনেক পছন্দ করে। তাছাড়া এসব কোম্পানির ইন্টারভিউতেও বিভিন্ন প্রব্লেম সলভ করতে দেয়া হয়।

মোটামুটি এই ছিল কথাবার্তা। তো, এখন কাজ কি? প্রব্লেম সলভিং চালিয়ে যাওয়া।

মন্তব্য করুন