Tag: অ্যালগরিদম

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

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

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

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

সমস্যাটি নিশ্চয় বুঝতে পারছো। এই সমস্যাকে বলা হয় কলিশন (collision)। এখন তুমি যদি অ্যারের ১ নম্বর ইনডেক্সে আমের দাম রাখো, তাহলে আগের আদার দামের সাথে এটি রিপ্লেস হয়ে যাবে। এতে করে তুমি যদি পরবর্তীতে আদার দাম দাও, তোমার হ্যাশটেবিল আমের দাম দিয়ে দিবে যা হওয়া উচিৎ নয়।

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

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

তবে এতেও একটি সমস্যা আছে। তোমার মুদির দোকানের সবগুলো পণ্য যদি একটি নির্দিষ্ট বর্ণ দিয়ে শুরু হয় তাহলে প্রথম স্লটে একটি বিশাল চেইন হবে। এক্ষেত্রে হ্যাশ টেবিল থেকে কোন পণ্যের দাম খুঁজে আনার সময় আর O(1) থাকবে না বরং সেটি হয়ে যাবে O(n)। কারণ তখন তোমাকে লিংকডলিস্ট থেকে উপাদানটি খুঁজতে হবে। লিংকডলিস্ট থেকে কোন উপাদান খুঁজে বের করতে সময় লাগে O(n)।

উপরের ছবি থেকে নিশ্চয় দেখতে পাচ্ছো সমস্যাটি কোথায়? তোমার অ্যারের বাকি স্লটগুলো প্রায় খালি রয়ে গেছে।
তাহলে এখান থেকে দুটি বিষয় জানা গেলো –
১. হ্যাশ ফাংশন অনেক গুরুত্বপুর্ণ। এটি খুব সিম্পল হলে সমস্যা।
২. প্রত্যেকটি স্লটেই যদি অনেক বড় লিংকলিস্ট থাকে, তাহলে কনস্ট্যান্ট টাইম অর্থাৎ O(‌1) সময়ে তুমি উপাদান খুঁজে বের করতে পারছো না।
এখন যদি তুমি একটি ভালো হ্যাশ ফাংশন লিখতে পারো, এবং প্রত্যেক স্লটেই যাতে বিশাল লিংকডলিস্টের চেইন না হয় তা নিশ্চিত করতে পারো তাহলেই O(‌1) সময়ে হ্যাশ টেবিল থেকে ভ্যালু পড়তে পারবে।

এবার Load Factor বলে একটা টার্ম আছে, এটি নিয়ে একটু বলি তোমাদের। একটি হ্যাশটেবিলের লোড ফ্যাক্টর খুব সহজেই বের করা যায়।

Load Factor = Number of items in the hash table / Total slot in the array
তাহলে তোমার অ্যারেতে যদি স্লট হয় 10 এবং উপাদানের সংখ্যা যদি হয় ৭ তাহলে লোড ফ্যাক্টর হবে- 0.7। এটি দিয়ে একটি হ্যাশটেবলি কতগুলো স্লট ফাকা আছে তা বের করা যায়। একটি হ্যাশটেবিলের লোড ফ্যাক্টর যদি 1 হয় তাহলে এর বোঝায়, এর প্রত্যেকটি স্লটে একটি করে উপাদান রয়েছে। লোড ফ্যাক্টর একের অধিক থাকার অর্থ হলো, টেবিলের কোন স্লটে একাধিক উপাদান রয়েছে।

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

তাহলে উপরের আলোচনা থেকে নিশ্চয় বুঝতে পারছো যে, যদিও কনস্ট্যান্ট টাইমে আমরা উপাদান খুঁজে বের করতে চাচ্ছি, কিন্তু সবসময় তা সম্ভব নয়। তবে best case এটি অবশ্যই O(1) হবে এবং worst case-এ এটি O(n) হতে পারে।

মনে করো, তুমি একটি মুদি দোকান দিয়েছো। তোমার দোকানে হরেকরকম পণ্যদ্রব্য রয়েছে। এই পণ্যগুলোর নাম ও দাম আলাদা আলাদা। এগুলো মনে রাখতে গিয়ে তুমি হিমশিম খাচ্ছো। তুমি সবগুলো খাতায় লিখে রেখেছো। যখনই তুমি একটি পণ্য বিক্রি করো, তোমাকে সেই খাতা দেখতে হয়। খাতা থেকে খুঁজে বের করতে হয়।

খাতাতে যদি নামগুলো বর্ণানুক্রমে রাখা না থাকে, তাহলে তোমার প্রতিবার খুঁজে বের করতে অনেক সময় লাগে। অ্যালগরিমদ ক্লাসে নিশ্চয় শিখেছো যে এক্ষেত্রে খুঁজে বের করার সময় O(n) । তবে নামগুলো যদি বর্ণানুক্রমে রাখা থাকে তাহলে বাইনারি সার্চ ব্যবহার করা যায় আর তখন সময় লাগবে O(log n)। তুমি নিশ্চয় জানো যে O(n) চেয়ে O(log n) কম সময় লাগে।

যদিও O(log n) কম সময় লাগছে, তবুও কিছুটা সময় লাগছে। সবচেয়ে ভাল হতো যদি কোন সময়ই না লাগতো। তুমি সবগুলো পণ্যের নাম এবং দাম মুখস্থ করে ফেলতে পারতে এবং ক্রেতা কোন পণ্যের নাম বলার সঙ্গে সঙ্গেই তুমি দাম বলে দিতে পারতে।

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

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

মনে করো, তোমার ১০ সাইজের একটি অ্যারে রয়েছে। এখন, ধরো, পেঁপের দাম ২০ টাকা। পেঁপে নামটি যদি হ্যাশ ফাংশনে দাও, তাহলে এটি যদি ৪ রিটার্ন করে, তাহলে অ্যারের চতুর্থ নম্বর ইনডেক্সে পেঁপের দামর রেখে দেবে। এভাবে আদার নাম হ্যাশ ফাংশনে দিলে যদি ৩ রিটার্ন করে, তাহলে তাকে তিন নম্বর ইনডেক্সে রেখে দিলে। এভাবে কলা, মরিচ ইত্যাদি রেখে দিলে। এখন যখন তোমার এগুলো দাম জানার দরকার হয়, তাহলে চট করে হ্যাশ ফাংশনে নামটি দিয়ে তার ইনডেক্সটি বের করে নিলে। অ্যারতে ইনডেক্স জানলে ভ্যালু পড়ে আনা খুব সহজ। অ্যারে থেকে ভ্যালু পরে আনার সময় আসলে O(1) ।

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

উপরের যে উদাহরণটি দিয়েছি তাতে একটি সমস্যা রয়েছে। সেটি নিয়ে পরবর্তীতে আলোচনা করবো। তবে সমস্যাটি তুমি চিন্তা করে যদি খুঁজে বের করতে পারো তাহলে নিচে কমেন্ট করে জানাও।

পরের পর্বঃ হ্যাশ ফাংশন ২।

পাদটিকা: বাইনারি সার্চের টাইম কমপ্লেক্সিটি কিভাবে O(log n) হলো, সেটা না বুঝলে দ্বিমিকের ডিসক্রিট ম্যাথমেটিক্স কোর্সের তৃতীয় ইউনিটের লেকচার দেখে নাও।

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

ইউক্লিডের অ্যালগোরিদম বা গ.সা.গু নির্ণয়ের অ্যালগোরিদমটি নিম্নরূপঃ

অ্যালগরিদম দেখে ঘাবড়ানোর কিছু নেই। আমরা অ্যালগরিদমটি বুঝতে চেষ্টা করি।

প্রথমেই দেয়া আছে একটি ফাংশন যার নাম gcd() এবং এই ফাংশনটির দুইটি প্যারামিটার a,b। এখানে, a এবং b হচ্ছে সেই দুইটি সংখ্যা আমরা যেগুলোর গসাগু বের করতে চাচ্ছি। ফাংশনটিতে প্রথমেই রয়েছে একটি while লুপ যেটি b-এর মান শূন্য না হওয়া পর্যন্ত চলবে। এখানে, একটি টেম্পোরারি ভ্যারিয়েবল t ব্যবহার করা হয়েছে। প্রথমে b-কে টেম্পোরারিতে রাখা হয়েছে। এরপর b-এর মান আপডেট হয়েছে a mod b দিয়ে। এখানে, mod হচ্ছে মডুল্যাস। অর্থাৎ, a-কে b দিয়ে ভাগ করে যেটি ভাগশেষ থাকবে সেটি হবে b-এর পরিবর্তিত মান। পরের লাইনে আছে a := t; এখানে a-এর নতুন মান হবে t-এর মান। লুপের প্রথম লাইনে আমরা t-এর মান পাচ্ছি b। তাহলে, a-এর মান হবে b-এর পুরনো মানটি (আপডেটেট মানটি নয়)। এভাবে লুপের ভিতরের কাজগুলো হতে থাকবে যতক্ষণ না b-এর মান শূন্য না হয়। লুপের কাজ শেষ হওয়ার পর ফাংশনটি a-এর মান রিটার্ন করবে, যেটি আমাদের কাঙ্ক্ষিত gcd()-এর মান বা গ.সা.গু।

একটি উদাহরণ দিলে ফাংশনটির কার্যক্রম আমাদের কাছে পরিষ্কার হবে। ধরা যাক, a= 12 এবং b = 16 , এদের গ.সা.গু বের করতে হবে। অ্যালগরিদম অনুযায়িঃ

1. a=12 , b = 16
2. while(b!=0) এভাবে b এর মান যতক্ষণ 0 না হবে লুপটি ততক্ষণ চলবে। অর্থাৎ লুপের ভিতরের তিনটি স্টেপ আমরা b এর মান 0 না হওয়া পর্যন্ত করবো।
3. t = 16; b = 12%16  এখানে যেহেতু 12 কে 16 দ্বারা ভাগ করা যায় না, তাই ভাগশেষ হবে 12, সুতরাং b = 12 , a = t = 16 (যেহেতু, প্রথমেই আমরা t এর মান 16 দিয়েছি যেটি b-এর প্রাথমিক মান।)
4. তিন নাম্বার স্টেপে আমরা a এবং b এর আপডেটেট ভ্যালু পেয়েছি। a = 16 এবং b= 12 . এখন আমাদের t = b = 12; b = a%b = 16%12 = 4; a =t = 12।
5. এখন a = 12, b = 4 এখন t = b = 4;  b = a%b = 12%4 = 0; a = 4; এখানে আমরা b এর মান জিরো পেয়ে গেলাম তাই এই লুপটি আর execute করবে না। এটি a-এর ভ্যালু return করবে 4।

আমরা যদি এখন এটি সি প্রোগ্রামিং এর সাহায্যে কোড করি, আমাদের কোডটি হবে এমনঃ

এই ফাংশনটির সাহায্যে খুব সহজেই গ.সা.গু নির্ণয়ের কাজটি করা যাবে। এবার দেখা যাক ইউক্লিড সাহেবের এই অ্যালগরিদমটি দিয়ে আমরা ল.সা.গু নির্ণয় করতে পারি কি না। ল.সা.গু নির্ণয় করার একটি সহজ সূত্র আছে। সূত্রটি এমনঃ

দুটি সংখ্যার ল.সা.গু = দুটি সংখ্যার গুণফল / দুটি সংখ্যার গ.সা.গু

দুটি সংখ্যার গ.সা.গু বের করার নিয়ম এবং দুটি সংখ্যার গুণফল নির্ণয় করার প্রক্রিয়া আমরা জানি। সেখান থেকে খুব সহজেই আমরা ল.সা.গু বের করতে পারবো।

লেখক : তামান্না নিশাত রিনি।