Alias method
কম্পিউটিংয়ে, উপনাম পদ্ধতিটি 1974 সালে এ. জে. ওয়াকার দ্বারা প্রকাশিত একটি বিচ্ছিন্ন সম্ভাব্যতা বিতরণ থেকে নমুনা নেওয়ার জন্য দক্ষ অ্যালগরিদমের একটি পরিবার। অর্থাৎ, এটি কিছু নির্বিচারে সম্ভাব্যতা বিতরণ অনুযায়ী পূর্ণসংখ্যার মান প্রদান করে। অ্যালগরিদমগুলি সাধারণত সময় ব্যবহার করে বা প্রাক প্রক্রিয়াকরণ করে, যার পরে সময় বিতরণ থেকে এলোমেলো মান আঁকা যেতে পারে। অপারেশন অভ্যন্তরীণভাবে, অ্যালগরিদম দুটি টেবিলের পরামর্শ দেয়, একটি সম্ভাব্যতা টেবিল এবং একটি উপনাম টেবিল (জন্য)। একটি এলোমেলো ফলাফল তৈরি করতে, দুটি টেবিলে একটি সূচক নির্ধারণের জন্য একটি ন্যায্য পাশা ঘূর্ণিত করা হয়। সেই সূচকে সঞ্চিত সম্ভাবনার উপর ভিত্তি করে, একটি পক্ষপাতদুষ্ট মুদ্রা তারপর উল্টানো হয়, এবং উল্টানোর ফলাফল এবং এর মধ্যে একটি ফলাফল বেছে নিতে ব্যবহৃত হয়। আরও সুনির্দিষ্টভাবে, অ্যালগরিদমটি নিম্নরূপ কাজ করেঃ একটি অভিন্ন র্যান্ডম ভ্যারিয়েট তৈরি করুন। যাক এবং। (এটি সমানভাবে বিতরণ করা হয় এবং সমানভাবে বিতরণ করা হয়।) যদি ফিরে আসে। এটি পক্ষপাতদুষ্ট মুদ্রা উল্টানো। অন্যথায়, ফিরে যান। মার্সাগলিয়া এবং অন্যান্যদের দ্বারা প্রস্তাবিত সম্ভাব্যতা সারণির একটি বিকল্প গঠন। "বর্গাকার হিস্টোগ্রাম" পদ্ধতি হিসাবে, গণনার পরিবর্তে তৃতীয় ধাপে (যেখানে) শর্তটি ব্যবহার করে। টেবিল জেনারেশন বিতরণটি অতিরিক্ত সম্ভাবনার সাথে একটি সুবিধাজনক মূল্যে বৃদ্ধি করা যেতে পারে, যেমন দুটির শক্তি। টেবিল তৈরি করতে, প্রথমে আরম্ভ করুন। এটি করার সময়, টেবিল এন্ট্রিগুলিকে তিনটি বিভাগে ভাগ করুনঃ "ওভারফুল" গ্রুপ, যেখানে, "আন্ডারফুল" গ্রুপ, যেখানে এবং যেখানে শুরু করা হয়নি, এবং "ঠিক পূর্ণ" গ্রুপ, যেখানে বা শুরু করা হয়েছে। যদি, সংশ্লিষ্ট মানটি কখনই বিবেচনা করা হয় না এবং গুরুত্বহীন হয়, তবে এর একটি মান বোধগম্য। যতক্ষণ পর্যন্ত সমস্ত টেবিল এন্ট্রি ঠিক পূর্ণ না হয়, ততক্ষণ নিম্নলিখিত পদক্ষেপগুলি পুনরাবৃত্তি করুনঃ নির্বিচারে একটি অতিরিক্ত পূর্ণ এন্ট্রি এবং একটি কম পূর্ণ এন্ট্রি বেছে নিন। (যদি এগুলির মধ্যে একটি বিদ্যমান থাকে তবে অন্যটিও অবশ্যই থাকতে হবে।) ফলাফলের প্রবেশের জন্য অব্যবহৃত স্থান নির্ধারণ করে বরাদ্দ করুন। পরিবর্তন করে এন্ট্রি থেকে বরাদ্দ স্থানটি সরিয়ে ফেলুন। প্রবেশ এখন ঠিক পূর্ণ। এর নতুন মানের উপর ভিত্তি করে উপযুক্ত বিভাগে প্রবেশ নির্ধারণ করুন। প্রতিটি পুনরাবৃত্তি "ঠিক পূর্ণ" বিভাগে কমপক্ষে একটি এন্ট্রি সরিয়ে দেয় (এবং শেষ পদক্ষেপ দুটি), তাই প্রক্রিয়াটি সর্বাধিক পুনরাবৃত্তির পরে শেষ হওয়ার নিশ্চয়তা দেওয়া হয়। প্রতিটি পুনরাবৃত্তি সময়মতো করা যেতে পারে, যাতে সময়মতো টেবিলটি স্থাপন করা যায়। ভোস উল্লেখ করেছেন যে ফ্লোটিং-পয়েন্ট রাউন্ডিং ত্রুটিগুলি 1ম ধাপে উল্লিখিত গ্যারান্টি লঙ্ঘন করতে পারে। যদি একটি বিভাগ অন্যটির আগে খালি হয়ে যায়, তবে অবশিষ্ট এন্ট্রিগুলি নগণ্য ত্রুটি সহ 1 এ সেট করা থাকতে পারে। ভাসমান বিন্দুর সমাধান হিসাবকে কখনও কখনও ওয়াকার-ভয়েস পদ্ধতি বা ভয়েস উপনাম পদ্ধতি বলা হয়। আলিয়াস কাঠামোটি অনন্য নয়। যেহেতু সন্ধান প্রক্রিয়াটি কিছুটা দ্রুত হয় যদি (কারণ পরামর্শের প্রয়োজন হয় না), টেবিল তৈরির সময় একটি লক্ষ্য হল সারির যোগফল সর্বাধিক করা। সর্বোত্তমভাবে এটি করা এনপি কঠিন বলে প্রমাণিত হয়, তবে একটি লোভী অ্যালগরিদম যুক্তিসঙ্গতভাবে কাছাকাছি আসেঃ ধনীদের কাছ থেকে লুঠ এবং দরিদ্রতমদের দেওয়া। অর্থাৎ, প্রতিটি পদক্ষেপে সবচেয়ে বড় এবং সবচেয়ে ছোটটি বেছে নিন। যেহেতু এর জন্য বাছাই করা প্রয়োজন, তাই এর জন্য সময় প্রয়োজন। দক্ষতা যদিও উপনাম পদ্ধতিটি খুব কার্যকর যদি একটি অভিন্ন বিচ্যুতি তৈরি করা নিজেই দ্রুত হয়, তবে এমন কিছু ক্ষেত্রে রয়েছে যেখানে এটি এলোমেলো বিট ব্যবহারের ক্ষেত্রে সর্বোত্তম থেকে অনেক দূরে। এর কারণ হল এটি প্রতিবার একটি পূর্ণ-নির্ভুলতা র্যান্ডম বৈচিত্র্য ব্যবহার করে, এমনকি যখন মাত্র কয়েকটি র্যান্ডম বিটের প্রয়োজন হয়। একটি ক্ষেত্রে দেখা যায় যখন সম্ভাবনাগুলি বিশেষভাবে ভারসাম্যপূর্ণ, এত বেশি এবং প্রয়োজন হয় না। উৎপাদন করা সময়ের অপচয়। উদাহরণস্বরূপ, যদি, তাহলে 32টি পছন্দ করার জন্য একটি 32-বিট র্যান্ডম ভ্যারিয়েট ব্যবহার করা যেতে পারে, তবে উপনাম পদ্ধতিটি শুধুমাত্র একটি তৈরি করবে। আরেকটি ঘটনা ঘটে যখন সম্ভাবনাগুলি দৃঢ়ভাবে ভারসাম্যহীন হয়, অনেকগুলি। উদাহরণস্বরূপ, যদি এবং, তবে বেশিরভাগ সময়, কেস 1 প্রযোজ্য তা নির্ধারণ করার জন্য কেবল কয়েকটি র্যান্ডম বিট প্রয়োজন। এই ধরনের ক্ষেত্রে, মার্সাগ্লিয়া এট আল দ্বারা বর্ণিত টেবিল পদ্ধতি। আরও কার্যকরী। যদি আমরা একই সম্ভাবনার সাথে অনেকগুলি পছন্দ করি তবে আমাদের গড়ে একটি নিরপেক্ষ র্যান্ডম বিটের চেয়ে অনেক কম প্রয়োজন হতে পারে। গাণিতিক কোডিং কৌশল ব্যবহার করে আমরা বাইনারি এনট্রপি ফাংশন দ্বারা প্রদত্ত সীমার কাছে যেতে পারি। সাহিত্য ডোনাল্ড নুথ, দ্য আর্ট অফ কম্পিউটার প্রোগ্রামিং, খণ্ড 2: সেমিনিউমেরিকাল অ্যালগরিদম, বিভাগ 3.4.1। বাস্তবায়ন http://www.keithschwarz.com/darts-dice-coins কিথ শোয়ার্জঃ বিশদ ব্যাখ্যা, ভোসের অ্যালগরিদমের সংখ্যাসূচক স্থিতিশীল সংস্করণ, এবং জাভা বাস্তবায়নের লিঙ্ক https://jugit.fz-juelich.de/mlz/ransampl জোয়াকিম উটকেঃ একটি ছোট সি লাইব্রেরি হিসাবে বাস্তবায়ন। https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 লিয়াম হুয়াং-এর সি + + https://github.com/joseftw/jos.weightedresult/blob/develop/src/JOS.WeightedResult/AliasMethodVose.cs সি #বাস্তবায়নে ভোসের অ্যালগরিদম। https://github.com/cdanek/KaimiraWeightedList সি #ফ্লোটিং পয়েন্ট অস্থিরতা ছাড়াই ভোসের অ্যালগরিদমের বাস্তবায়ন। তথ্যসূত্র সিউডোরান্ডম নম্বর জেনারেটর