انتخاب تصادفی وزندار
Weighted Randomانتخاب تصادفی وزندار یک الگوریتم از دسته آمار است. این روش آماری weightها را به احتمال تبدیل می‌کند و نمونه‌گیری را متناسب با همان احتمال انجام می‌دهد.
اول این مفهوم را در ذهن نگه دار
انتخاب تصادفی وزندار یک الگوریتم از دسته آمار است. این روش آماری weightها را به احتمال تبدیل می‌کند و نمونه‌گیری را متناسب با همان احتمال انجام می‌دهد.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم انتخاب تصادفی وزندار ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع Varies by implementation / input constraints است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
weightهای غیرمنفی را validate کن.
وزن تجمعی/احتمال را بساز.
یک عدد random بساز و interval آن را پیدا کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای انتخاب تصادفی وزندار هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی احتمال انتخاب آیتم‌ها برابر نیست مناسب است.
کجا معمولاً اشتباه می‌کنیم؟
- weight نامعتبر.
- random generator biased.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای انتخاب تصادفی وزندار در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی Varies by implementation / input constraints و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
انتخاب تصادفی وزندار چه مسئله‌ای را حل می‌کند؟
انتخاب تصادفی وزندار یک الگوریتم از دسته آمار است. این روش آماری weightها را به احتمال تبدیل می‌کند و نمونه‌گیری را متناسب با همان احتمال انجام می‌دهد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
weight نامعتبر.