হ্যাশ ফাংশন -২

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

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

আরো গভীরে যাওয়ার আগে সমস্যাটা নিয়ে আরো একটু আলোচনা করি। মনে করো, তোমার হ্যাশ ফাংশনটি খুবই সাধারণ। এটি অ্যারেতে উপাদানগুলো বর্ণানুক্রমে স্থান দেয়। তোমার পণ্যগুলো যথাক্রমে আদা, রসুন, পেঁপে, কলা ইত্যাদি হয় এবং তোমার অ্যারের সাইজ যদি 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(n) vs O(log n) 

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

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

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

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

চিত্র: হ্যাশ ফাংশন

চিত্র: হ্যাশ টেবিল

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

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

পরের অংশ:  লিংক

জাভা ইন্টারফেস এর ক্ষেত্রে multiple inheritance সাপোর্ট করলেও ক্লাসের ক্ষেত্রে কেনো করে না ?

জাভা প্রোগ্রামিং ল্যাংগুয়েজের ডিজাইনাররা কয়েকটি গুরুত্বপূর্ণ বিষয় মাথায় রেখে এই ল্যাংগুয়েজকে ডিজাইন করে। এগুলো হলো-

1. এটি হতে হবে খুবই সিম্পল, অবজেক্ট ওরিয়েন্টেড এবং পরিচিত, অর্থাৎ যারা তখন সি বা সি++ জানতো তারা যাতে করে সহজেই বুঝতে পারে।
2. এটিকে অবশ্যই অনেক শক্তসমর্থ এবং নিরাপদ (robust and secure) হতে হবে।
3. এটি যেকোন অপারেটিং সিস্টেমে চলবে।
4. এর পারফর্মেন্স অনেক ভাল হতে হবে ।
5. এটি ইন্টারপ্রেটেড, থ্রেডেড এবং ডাইনামিক হতে হবে। (এখানে বলে রাখি, জাভা যদিও কম্পাইল্ড ল্যাংগুয়েজ, কিন্তু জাভা ভার্চুয়াল মেশিন মূলত বাইটকোড ইন্টারপ্রেট করে আর জেভিএম একটা ডাইনামিক মেশিন)।

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

মাল্টিপল ইনহেরিটেন্সের ক্ষেত্রে একটি বড় সমস্যা হলো ডাইমন্ড সমস্যা। একটি উদাহরণ দেওয়া যাক- মনে কর, একটি ক্লাস A, একে B ও C এক্সটেন্ড করে। আবার আরেকটি ক্লাস D যা কিনা B ও C কে এক্সটেন্ড করে। এখন ধরো, যদি A এর কোনো একটি মেথডকে B ও C দুটিই ওভারাইড করে। এখন যদি D থেকে সেই মেথডটি কল করতে চাও, তাহলে সেটি কোন ক্লাসের মেথডকে কল করবে ? B না C ? সমস্যাটি নিশ্চয় বোঝা যাচ্ছে? 

ইন্টারফেসের ক্ষেত্রে এই সমস্যা হওয়ার কোন উপায় নেই, কারণ প্রত্যেকটি ক্লাস যেহেতু মেথডগুলো ইম্প্লিমেন্ট করবে, তাই সবাই আসলে নিজের মেথডকেই কল করবে।

জাভা ডিজাইনাররা এরকম সমস্যার মধ্য দিয়ে যেতে চায় নি। তাই জাভাতে মাল্টিপল ইনহেরিটেন্স নেই।

Ref: http://programabad.com/questions/5613/multiple-inheritence/5614

কীভাবে ভাল প্রোগ্রামার হওয়া যায়

এই প্রশ্নটি অনেকেই করে থাকে। এর একটি নির্দিষ্ট উত্তর নেই। তবে আমার মনে হয় প্রোগ্রামিং মূলত দুটি বিষয়ের সংমিশ্রণ। 

এক, চিন্তা করার ক্ষমতা ।

দুই, অনুশীলণ। 

এই দুটিই লাগে প্রোগ্রামিং করার জন্যে। এই দুটির একটি বাদ পরলে ভাল প্রোগ্রামার হওয়ার কোন উপায় নেই।

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

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

এই দুটি একটা লম্বা সময় ধরে করতে থাকলে একসময় আপনি নিজেই বুঝতে পারবেন যে আপনি একজন ভাল প্রোগ্রামার হয়ে গেছেন।

ম্যালকম গ্ল্যাডওয়েলের একটি বই- Outliers-এ তিনি উল্লেখ করেছেন যে, যে কোন বিষয়ে মাস্টার হতে হলে রাফলি ১০ হাজার ঘণ্টা অণুশীলন করতে হয়। সে অনুযায়ী আপনি যদি সপ্তাহে ৫ দিন ৪ ঘণ্টা করে অনুশীলন করেন, আপানর লাগবে প্রায় ১০ বছর।

নিচে একটি লিংক দিয়ে দিলাম। এটি ব্যবহার করে আপনি নিজেই ঠিক করে নিন প্রতিদিন কত ঘণ্টা এবং সপ্তাহে কতদিন অণুশীলন করবেন-http://ryac.ca/10000-hours-how-long-is-that/