ডেটা স্ট্রাকচার ও অ্যালগরিদম#
এই বইটি পড়ে আমরা যারা পাইথনের অনেকটাই শিখে ফেলেছি (অন্ততপক্ষে বেসিকটুকু শিখে ফেলেছি), আমাদের এখন নতুন করে ভাবতে বসতে হবে। আমরা কতটুকু জ্ঞান সত্যিকার অর্থেই অর্জন করতে পারলাম? এটা বোঝার একটা সহজ উপায় আছে। উপায়টা হলো, বিভিন্ন গাণিতিক সমস্যাকে প্রোগ্রামিংয়ের মাধ্যমে সমাধান করার চেষ্টা করা। কিন্তু কথা হলো এত সমস্যা পাব কোথায় আর আমরা যে সমাধানটা বের করব সেটা আসলেই সঠিক সমাধান কিনা সেটা বুঝব কীভাবে? ভয় নাই! এইজন্য রয়েছে অনলাইন জাজ (Online Judge)।
অনলাইন জাজ হলো এমন একটা অনলাইন সিস্টেম যেখানে কোনো প্রোগ্রামকে কোনো সমস্যার বিপরীতে অটোমেটিকালি টেস্ট করে দেখা হয় যে সমাধানটা শতভাগ সঠিক আছে কিনা। বিভিন্ন অনলাইন জাজে প্রচুর প্রোগ্রামিং সমস্যা (সাধারণত প্রোগ্রামিং প্রবলেম বলা হয়) পাওয়া যায়। এসব সমস্যা সমাধান করে উত্তরটা নির্দিষ্ট জায়গায় সাবমিট করলেই জাজ আমাদের জানিয়ে দেবে আমাদের সমাধানটা সঠিক হয়েছে কিনা। পাইথন সাপোর্ট করে এমন কতগুলো জনপ্রিয় অনলাইন জাজ হলো:
শেষের দুটো মূলত কন্টেস্ট প্ল্যাটফর্ম, মানে এসব জায়গায় প্রোগ্রামিং নিয়ে বিভিন্ন অনলাইন প্রতিযোগিতার আয়োজন করা হয় যাতে সবাই অংশ নিতে পারে। তবে কন্টেস্ট প্ল্যাটফর্ম হলেও এসব জায়গায় সলভ করার মতো বহুত প্রবলেম (প্র্যাকটিস প্রবলেম নামে অভিহিত) পাওয়া যায়। কিন্তু আমাদের প্রশ্ন হলো, এত এত অনলাইন জাজের ভিড়ে আমরা শুরু করব কোনটা দিয়ে?
শুরুর দিকে আমরা হ্যাকারর্যাংক, হ্যাকারআর্থ ও লিটকোড ব্যবহার করতে পারি। হ্যাকারআর্থ ও লিটকোডে বিগিনার, ডেটা স্ট্রাকচার, অ্যালগরিদম এইভাবে প্রবলেম বিভিন্ন সেকশনে ভাগ করা আছে। অবশ্য পাইথনের ক্ষেত্রে শুরুটা হ্যাকারর্যাংক দিয়ে করলে ভালো হয়। কারণ, এর প্রবলেম সেকশনে পাইথন বিভাগে পাইথনের প্রতিটা টপিকের জন্য আলাদা আলাদা প্রবলেম আছে। প্রোগ্রামিংয়ের বেসিক শেখা শেষ হয়ে গেলে আমরা সবগুলো টপিকের প্রবলেম সলভ করার চেষ্টা করতে পারি। যে টপিকের প্রবলেম সলভ করতে বেশি হিমশিম খাব, বুঝে নেব ঐ টপিকে আমরা দুর্বল। সেজন্য বই/অফিশিয়াল ডকুমেন্টেশন খুলে আবার ঐ টপিকের আগাগোড়া ভালোমতো বুঝে বুঝে পড়ব। বুঝতে না পারলে বড় কারো সহায়তা নেব। আজকাল ফেসবুকে প্রোগ্রামিংয়ের বিভিন্ন গ্রুপ রয়েছে যেখানে বাংলা ভাষায় নিজের সমস্যার দ্রুত সমাধান পাওয়া যায়। পাইথন নিয়ে বাংলাদেশের সবচেয়ে বড় প্রোগ্রামিং গ্রুপ হলো পাইথন বাংলাদেশ। এই গ্রুপে অত্যন্ত চমৎকারভাবে বাংলা/ইংরেজি ভাষায় নিজেদের সমস্যার কথা সংক্ষেপে কিন্তু পরিপূর্ণভাবে তুলে ধরব আমরা। কেউ না কেউ অবশ্যই আমাদের সমস্যার সমাধান করে দেবেন। তখন তাকে প্রাণঢালা ধন্যবাদ জানিয়ে আবার প্রবলেম সলভিংয়ে লেগে যাব আমরা।
যাহোক, হ্যাকারর্যাংকের প্রবলেম সেকশনের পাইথন বিভাগের সব প্রবলেম সলভ করা হয়ে গেলে আমরা লিটকোডে চলে যাব। লিটকোডের প্রবলেম সেকশনের বিগিনার ক্যাটাগরিতে অনেকগুলো প্রোগ্রামিং প্রবলেম রয়েছে। সবগুলো একের পর এক শেষ করে ফেলব। আর তারপর লাফ দেব ডেটা স্ট্রাকচারের সমুদ্রে।
ডেটা স্ট্রাকচার#
ডেটা স্ট্রাকচার হলো ডেটা অর্গানাইজ ও স্টোর করার স্পেশালাইজড ফরম্যাট যাতে পরবর্তীতে এসব ডেটা সর্বোত্তমভাবে ফিরে পাওয়া যায় ও বিভিন্ন কাজে ব্যবহার করা যায়। কিন্তু আমাদের জন্য ডেটা স্ট্রাকচার কতটা গুরুত্বপূর্ণ?
কম্পিউটারে ডেটা নিয়ে আমরা সাধারণত তিন ধরনের কাজ করি: (১) ডেটা ইনপুট নিই, (২) ডেটা প্রসেস করি ও (৩) ডেটা আউটপুট দিই। আর ডেটা স্ট্রাকচারের উদ্দেশ্য হলো এই তিন ধরনের কাজকেই অপটিমাইজ করা বা করতে সাহায্য করা। ধরা যাক, আমরা আমাদের ব্যক্তিগত লাইব্রেরিতে ১০ হাজার বই রাখলাম। বইগুলো যদি আমরা নির্দিষ্ট প্যাটার্ন বা কোনো পদ্ধতি অনুসরণ না করে সেলফে রাখি তাহলে সময়কালে একটা বই খুঁজে বের করতে আমাদের কিন্তু ইহজনম পার হয়ে যাবে। এইসব ঝামেলা থেকে মুক্তি পাবার জন্য ডেটা স্ট্রাকচার জানা দরকার আমাদের।
লিস্ট, টাপল, সেট, ডিকশনারি ছিল পাইথনের বিল্ট-ইন ডেটা স্ট্রাকচার। তবে এসবের পাশাপাশি আমাদেরকে আরো কিছু ডেটা স্ট্রাকচার সম্পর্কে জানতে হবে। কমন বা না জানলেই নয় এরকম কিছু ডেটা স্ট্রাকচার হলো:
- স্ট্যাক
- কিউ
- ডেক
- লিংকড লিস্ট
- বাইনারি সার্চ ট্রি
- হিপস
- এভিএল (AVL) ট্রি
- বি ট্রি
- বি-প্লাস (B+) ট্রি
- বাইনারি ইনডেক্সড ট্রি
- ট্রাই (Trie)
- ডিসজয়েন্ট-সেট
- সেগমেন্ট ট্রি
পাইথন ব্যবহার করে ডেটা স্ট্রাকচার শেখার জন্য আমরা এই ফ্রি অনলাইন কোর্সটি করতে পারি। আমেরিকার ইউনিভার্সিটি অব মিশিগানের স্কুল অব ইনফরমেশনের ক্লিনিক্যাল প্রফেসর চার্লস সেভারেন্স এই কোর্সটি পড়িয়েছেন। শিক্ষক হিসেবে তিনি অসাধারণ। সবচেয়ে বড় কথা হলো, পড়ানোর ক্ষেত্রে নিজস্ব ভঙ্গিমা রয়েছে তাঁর। কোর্সের ভাষা ইংরেজি। আর কোর্সটি ভিডিও লেকচার হিসেবে দেখতে হবে।
ইংরেজি বইয়ের মধ্যে সবচেয়ে ভালো হলো প্রবলেম সলভিং উইথ অ্যালগরিদমস অ্যান্ড ডেটা স্ট্রাকচারস ইউজিং পাইথন। এই বইটা সম্পূর্ণ যে পড়বে তার ডেটা স্ট্রাকচার ও অ্যালগরিদমের যাবতীয় বেসিক ক্লিয়ার হয়ে যাবে। বইটাতে যথাযথ উদাহরণও যোগ করা হয়েছে।
ডেটা স্ট্রাকচার ও অ্যালগরিদম ভিজ্যুয়ালাইজ (দৃষ্টিগোচর) করার একটা অসাধারণ সাইট হলো এটা। আমরা যেসব ডেটা স্ট্রাকচার থিওরেটিকালি শিখব, সেগুলো এই সাইটে ভিজ্যুয়ালাইজ করে দেখানো হয়েছে।
বাংলায় ডেটা স্ট্রাকচার ও অ্যালগরিদম শেখার একটা চমৎকার জায়গা হলো শাফায়েত আশরাফ ভাইয়ের ব্লগ। যদিও ব্লগে প্রতিটা উদাহরণ সুডো কোডেই বেশি দেখানো হয়েছে তবে একটা টপিক শেখার পর সেটার সুডো কোডকে ফলো করে পাইথনে ইমপ্লিমেন্ট করার চেষ্টা করা যেতেই পারে। (Pseudocode হলো একটা অ্যালগরিদম বা প্রোগ্রাম কীভাবে ধাপে ধাপে কাজ করে তার সংক্ষিপ্ত বর্ণনা।)
মোটামুটি শেখা হয়ে গেলে হ্যাকারর্যাংকের প্রবলেম সেকশনের ডেটা স্ট্রাকচার বিভাগের প্রতিটা প্রবলেম সলভ করার চেষ্টা করব আমরা। লিটকোডের প্রবলেম সেকশনে ডেটা স্ট্রাকচারের উপর বেশকিছু প্রবলেম রয়েছে। এগুলোও সলভ করার চেষ্টা করব।
অ্যালগরিদম#
ইতিমধ্যেই আমরা অ্যালগরিদম শব্দটার সঙ্গে পরিচিত হয়ে গিয়েছি। অ্যালগরিদম হলো কতগুলো অপারেশনের সেট। আরো ভালোভাবে বলতে গেলে, কোনো একটা সমস্যাকে সবচেয়ে উৎকৃষ্ট যে পদ্ধতিতে সমাধান করা যায় তাকেই অ্যালগরিদম বলে। এগুলো মূলত গণিত দ্বারা প্রমাণিত পদ্ধতি। কোনো একটা সমস্যা সাধারণ বুদ্ধি প্রয়োগ করে সমাধান করলে সেটা যতটা ইফেক্টিভ হয়, অ্যালগরিদম ব্যবহার করে সলভ করলে ঢের বেশি ইফেক্টিভ হয়।
সুতরাং মদ্দা কথা হলো আমাদেরকে অ্যালগরিদম শিখতে হবে। দুনিয়ায় বহুত অ্যালগরিদম আছে। তবে কমন বা না জানলেই নয়, এরকম কিছু অ্যালগরিদম হলো:
- বাবল সর্ট
- ইনসার্শন সর্ট
- সিলেকশন সর্ট
- কুইক সর্ট
- হিপ সর্ট
- ডেপথ ফার্স্ট সার্চ (ডিএফএস)
- ব্রেথ ফার্স্ট সার্চ (বিএফএস)
- এ-স্টার (A*) সার্চ
- হিল ক্লাইম্বিং
পূর্বে উল্লেখিত প্রবলেম সলভিং উইথ অ্যালগরিদমস অ্যান্ড ডেটা স্ট্রাকচারস ইউজিং পাইথন বইটা দিয়েই শেখা শুরু করতে পারি আমরা। বাংলায় শিখতে চাইলে শাফায়েত ভাইয়ের গ্রাফ অ্যালগরিদম বইটা কিনে নেওয়া যেতে পারে। তবে সেক্ষেত্রে প্রতিটা অ্যালগরিদম নিজে নিজে পাইথনে ইমপ্লিমেন্ট করার চেষ্টা করতে হবে।
তবে যেখান থেকেই শিখি না কেন প্রবলেম সলভিংয়ে জোর দিতে হবে আমাদের। বিভিন্ন কন্টেস্টে অংশ নিতে হবে। বিশেষত আমাদের মধ্যে যাদের গুগল বা মাইক্রোসফটের মতো বড়সড় কোম্পানিতে চাকরি করার প্রবল ইচ্ছা আছে। এসব কোম্পানি প্রবলেম সলভিংয়ে সিদ্ধহস্তদের অনেক পছন্দ করে। তাছাড়া এসব কোম্পানির ইন্টারভিউতেও বিভিন্ন প্রবলেম সলভ করতে দেওয়া হয়।
মোটামুটি এই ছিল কথাবার্তা। তো, এখন কাজ কী? প্রবলেম সলভিং চালিয়ে যাওয়া।
