কাজের জায়গায় যখন আগে শেখা এলগোরিদম, ডাটা স্ট্রাকচার কাজে লাগে!

কাজের জায়গায় যখন আগে শেখা এলগোরিদম, ডাটা স্ট্রাকচার কাজে লাগে!

স্কুলে/কলেজে/ইউনিভার্সিটিতে যেইসব এলগোরিদম আর ডাটা স্ট্রাকচার আমরা শিখি, কিংবা ইন্টারভিউ'র প্রিপারেশন নিতে গিয়ে প্রব্লেম সলভিং প্রাকটিস করতে যেইসব জটিল সল্যুশন আমরা ব্যবহার করি - তার কতটুকু জবের দৈনন্দিন সত্যিকার কাজে গিয়ে আসলে লাগে? আমার ধারণা খুব একটা না। অন্তত আমার লাগে না। কিন্তু তাই বলে আমি বলছি না যে এইগুলো শেখার দরকার নাই, প্র্যাক্টিস করা বৃথা - মাথা কাজ করানোর জন্য এইসব খুবই জরুরি। আর কাজের জায়গায় যখন কোনো একটা প্রব্লেম সল্ভ করতে গিয়ে আগের শেখা কোনো এলগোরিদম, ডাটা স্ট্রাকচার কিংবা টেকনিক কাজে লাগে, তখন আসলেই খুব ভালো লাগে। এতো ভূমিকা দেয়ার কারণ হচ্ছে, কয়েকদিন আগে আমার তাই-ই হয়েছিল, জেনেরিক প্রব্লেমটা আর সল্যুশনটা শেয়ার করার লোভ সামলাতে পারছি না। নিচে দিচ্ছি:

প্রব্লেম: ধরা যাক, n সংখ্যক লিস্টে কিছু নম্বর আছে। আপনাকে সেগুলো (পাইথনে) list of lists আকারে ইনপুট দেয়া হবে। আরেকটা সংখ্যা, p দেয়া হবে। আপনার কাজ হবে, p লেংথ-এর একটা লিস্ট রিটার্ন করা,  যেখানে ইনপুটের n লিস্টের সবগুলো থেকে প্রায় সমান সংখক এলিমেন্ট নিতে হবে। আর ডুপ্লিকেট থাকতে পারবে না। দুইটা উদাহরণ দেই:

কেস ১:
list_of_lists = [[1, 2, 3], [3, 4, 5], [6, 7]], p = 6;
expected output = [1, 3, 6, 2, 4, 7] 

কেস ২
list_of_lists = [[1, 2, 3], [3, 4, 5], [6, 7]], p = 7;
expected output = [1, 3, 6, 2, 4, 7, 5]

প্রব্লেমটা আশাকরি বোঝা গেছে। কেস-১ সিম্পল। সবগুলা ইনপুট লিস্ট থেকে ২ টা করে নিয়ে ৬ সাইজের আউটপুট লিস্ট তৈরী করলেই হলো। কেস-২ একটু জটিল,  যেহেতু আউটপুট লিস্টে ডুপ্লিকেট থাকতে পারবে না, ইনপুটের দ্বিত্বীয় লিস্ট থেকে 5 নিয়ে ৭ সাইজের লিস্ট তৈরী করা লাগলো। 

সল্যুশনটা কী হবে? আমার সলুশনটা বলার আগে বলে নেই: সেটাতে আমি ধাপে ধাপে পৌছাইসি। আমার  প্রথমদিনের সলুশনটা জটিল ছিল, পরে একটা ইমপ্রুভমেন্ট মাথায় আসলে ইমপ্লিমেন্ট করি। পরের দিন আরেকটু ভালো সল্যুশন মাথায় আসলে সেটা ইমপ্লিমেন্ট করে আলটিমেট সলুশনে পৌছাইসি। যদিও আগের সল্যুশন গুলো ঠিকই ছিল।  

সল্যুশন: প্রথমেই খেয়াল করে দেখি যে একটা পরিচিত আলগোরিদমের সাথে প্রব্লেমটার মিল আছে। merge sort আলগোরিথমের মার্জ অংশে আমরা দুইটা সর্টেড লিস্ট থেকে একটা আউটপুট লিস্ট বানাই। আর এখানেও অনেকটা তাই, শুধু দুইটার বদলে n-সংখ্যাক লিস্ট, আর সর্টেডর বদলে শর্ত হচ্ছে  আউটপুট লিস্ট ইউনিক হতে হবে। অর্থাৎ, যতক্ষণ p সাইজের লিস্ট হচ্ছে না, ততক্ষন এক এক করে প্রতিটা n -লিস্টের এলিমেন্ট নিবো, একটা set ব্যবহার করে ইউনিক কিনা টেস্ট করে আউটপুট লিস্টে এপেন্ড করতে থাকবো। আর যদি ইউনিক না হয়, তাহলে লিস্টের পরের এলিমেন্টটা নিবো, যতক্ষণ লিস্টে এলিমেন্ট থাকে। কিছু কর্নার কেস বাদে, এইটাই বেসিক সল্যুশন।

কর্নার কেস গুলো কি? কয়েকটা হতে পারে, যেমন: হাতের লিস্টে যদি এলিমেন্ট না থাকে? যদি আউটপুট p -র থেকে ইনপুট n লিস্টের সাইজ কম: (n < p) হয়।  যদি লিস্ট গুলোতে ডুপ্লিকেট সংখ্যা বেশি থাকে  - মূলত এই কয়টাই। কিছু চেক অ্যাড করে সেটাও হ্যান্ডেল করা যাবে। 

বাকিটা না পড়ে, আপনি কি একটু কোডটা ইমপ্লিমেন্ট করার চেষ্টা করবেন? আমার ধারণা করলেই কিছু ইম্প্রোভমেন্ট আপনার মাথায় আসবে। যেটা আমি নিচে দিচ্ছি।

প্রতিটা লিস্টের কোন ইনডেক্স-এ আছি, সেটা ম্যানেজ করা একটু ঝামেলা হবে। একটু চিন্তা করতেই  মাথায় আসলো যে আমি পাইথনের generator ব্যবহার করে সেটা সল্ভ করতে পারি। ইনপুট n -লিস্টের প্রতিটাকে যদি আমি শুরুতেই  generator -এ কনভার্ট করি, আর next() কল করে এলিমেন্ট বের করে আনি, তাহলে পাইথনই ইনডেক্স ম্যানেজ করবে, আমার আর সেটা হ্যান্ডেল করতে হবে না। একটা ঝামেলা হয়তো হবে, যদি জেনারেটরে এলিমেন্ট না থাকে, তাহলে exception থ্রো করবে। ভাবলাম, সেটা নাহয় try-except এ ঢুকিয়ে হ্যান্ডেল করবো। কোডের চেহারা অনেকটা এইরকম হলো:

কোডের লিংক : https://replit.com/join/vhqitodokp-ishtiaquehussai

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

 

আইডিয়াটা হচ্ছে, জেনেরেটরগুলোকে শুরুতে একটা কিউতে ঢুকিয়ে রাখলাম। এরপর যতক্ষণ output লিস্টের সাইজ p  না হয় এবং কিউয়ে এলিমেন্ট থাকে, ততক্ষন ডিকিউ করে কিউ থেকে জেনেরেটর বের করে নিলাম। এরপর জেনারেটর থেকে এলিমেন্ট next() কল করে নিলাম, এলিমেন্ট ইউনিক হলে output লিস্টে, set -এ এপেন্ড, অ্যাড করে নিলাম। তারপর হাতের জেনেরেটরকে আবারো কিউ-এ ঢুকিয়ে দিলাম। আর যদি, এলিমেন্ট ইউনিক না হয়, তাহলে জেনেরেটর থেকে next ()- কল করে আবারো একই কাজ করতে থাকলাম (while True) । যদি কখনো next() কল করে জেনারেটরে এলিমেন্ট না পাই, তখন জেনারেটর StopIteration এক্সেপশন থ্রো করবে। সেই এক্সেপশন হ্যান্ডেল করার জন্য কিছুই না, শুধু হাতের জেনেরেটরকে পুনরায় আর কিউতে অ্যাড না করলেই হবে - অর্থাৎ, এলিমেন্ট যখন আর নাই-ই তাহলে সেটা কিউ থেকে ফেলে দিতে হবে।    

আমরা চাইলে except Exception লিখেও কাজটা করতে পারতাম। তবে ভালো কোডিং প্রাকটিস হচ্ছে, too-broad-exception হ্যান্ডেল না করে স্পেসিফিক এক্সেপশন হ্যান্ডেল করা। জেনেরেটরে এলিমেন্ট না থাকলে next() যেহেতু StopIteration এক্সেপশন থ্রো করে, কাজেই সেটা হ্যান্ডেল করাই ভালো। 

সবশেষ: গতরাতে আমার বন্ধু মিথুনের সাথে প্রব্লেমটা নিয়ে আলাপ করছিলাম। মিথুন ইউনিভার্সিটি অফ মেমফিস, টেনেসিতে পিএইচডি করছে। আলাপ করতে গিয়ে আরেকটা আইডিয়া আমাদের মাথায় আসলো। জেনারেটার ছাড়াই শুধু কিউ দিয়েই তো প্রব্লেমটা আসলে সল্ভ করা যায়! ইনপুট list_of_lists 'র প্রতিটা লিস্টের এলিমেন্টগুলোকে কিউয়ে ঢুকিয়ে, পরে সেই কিউ গুলোকে আরেকটা কিউ-এ ঢুকিয়ে queue of queues বা nested queue  করেও তো প্রব্লেমটা সল্ভ করা যায়। চমৎকার আইডিয়া! কারো পাইথনে জেনেরেটর'র আইডিয়া না থাকলে, এভাবেও প্রব্লেমটা সল্ভ করা যাবে। নিচে কোডের স্ক্রিনশট দিচ্ছি:

আর সবগুলো ভার্শনের কোডের লিংক নিচের লিংকে পাওয়া যাবে:
https://replit.com/join/vhqitodokp-ishtiaquehussai

সবাইকে ধন্যবাদ!
--ইশতিয়াক, ৭ ব্যাচ, সিএসই, ডিইউ