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 Joachim Wuttke: ایک چھوٹی سی C لائبریری کے طور پر نفاذ۔ https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 لیام ہوانگ کا C + + https://github.com/joseftw/jos.weightedresult/blob/develop/src/JOS.WeightedResult/AliasMethodVose.cs C #میں ووز کے الگورتھم کا نفاذ۔ https://github.com/cdanek/KaimiraWeightedList C #فلوٹنگ پوائنٹ عدم استحکام کے بغیر ووز کے الگورتھم کا نفاذ۔ حوالہ جات سیوڈورانڈم نمبر جنریٹر