আপনার পারসোনাল কম্পিউটারে (পিসি) কোন একটি প্রোগ্রাম এর কর্মদক্ষতা (performance) বৃদ্ধির জন্য কোন্ কাজটি করা সর্বোত্তম হবে বলে আপনি মনে করেন?
সঠিক উত্তর
কপ্রোগ্রামটির জন্য এমন একটা এলগরিদম তৈরি করা যা asymptotically faster
ব্যাখ্যা
প্রশ্নটি জানতে চেয়েছে একটি প্রোগ্রামের কর্মদক্ষতা বাড়ানোর সবচেয়ে কার্যকর উপায় কী। উত্তর এমন অ্যালগরিদম তৈরি করা, যা অ্যাসিম্পটোটিক্যালি দ্রুত, মানে ইনপুট বড় হলে যার সময় অনেক কম হারে বাড়ে।
হার্ডওয়্যার উন্নত করলে গতি বাড়ে একটি নির্দিষ্ট গুণক পরিমাণ, ধরুন দুই বা চার গুণ, এবং তা ইনপুট যত বড়ই হোক মোটামুটি একই থাকে। কিন্তু ভালো অ্যালগরিদম সমস্যার মূল হিসাবটাই কমিয়ে দেয়, তাই ইনপুট যত বড়, লাভ তত বেশি।
উদাহরণ দিই। দশ লাখ সংখ্যা সাজাতে এন বর্গ ধাপের পদ্ধতি নেয় প্রায় এক লক্ষ কোটি ধাপ, আর এন লগ এন পদ্ধতি নেয় মাত্র দুই কোটির মতো ধাপ; পার্থক্য প্রায় পঞ্চাশ হাজার গুণ। কোনো কম্পিউটার আপগ্রেডে এত গতি বাড়ানো সম্ভব নয়।
ফাঁদ হলো ‘খ এবং গ উভয়েই’। কনফিগারেশন বা দ্রুত ইনপুট-আউটপুট যন্ত্র কিছুটা সাহায্য করে ঠিকই, কিন্তু সর্বোত্তম উপায় জানতে চাইলে উত্তর অ্যালগরিদম।
- n = ১০,০০,০০০ (১০ লাখ)
- n² = ১০¹² = ১ লক্ষ কোটি ধাপ
- n log₂n ≈ ১০⁶ × ২০ = ২ × ১০⁷ = ২ কোটি ধাপ
- পার্থক্য ≈ ১০¹² ÷ (২ × ১০⁷) ≈ ৫০,০০০ গুণ
- হার্ডওয়্যার আপগ্রেড ≈ কয়েক গুণ → অ্যালগরিদমই সর্বোত্তম
স্টেপ বাই স্টেপ শিখুন
৪/৪- ধরি ১০ লাখ সংখ্যা সাজাতে হবে।
- n² পদ্ধতি: প্রায় ১০¹², মানে ১ লক্ষ কোটি ধাপ।
- n log n পদ্ধতি: প্রায় ২ কোটি ধাপ, মানে প্রায় ৫০ হাজার গুণ কম।
- হার্ডওয়্যার আপগ্রেড মাত্র কয়েক গুণ দেয়; তাই সর্বোত্তম উপায় ভালো অ্যালগরিদম।
খ. পিসির Configuration উন্নত করা: কনফিগারেশন বাড়ালে গতি বাড়ে কেবল একটি স্থির গুণকে; বড় ইনপুটে খারাপ অ্যালগরিদমের সমস্যা থেকেই যায়।
গ. খুব দ্রুত গতির I/O devices লাগানো: দ্রুত I/O কেবল ইনপুট-আউটপুটনির্ভর অংশে সাহায্য করে; মূল হিসাবের ধাপ কমায় না।
ঘ. খ এবং গ উভয়েই: খ ও গ দুটোই আংশিক সমাধান; সর্বোত্তম উপায় অ্যালগরিদম উন্নয়ন।
সফটওয়্যারের গতির প্রশ্নে ‘asymptotically faster algorithm’ থাকলে সেটিই সাধারণত সর্বোত্তম উত্তর।
যন্ত্র বদলালে গুণে বাড়ে, অ্যালগরিদম বদলালে ধাপই কমে।