فیلتر Bloom
Bloom FilterBloom Filter یک ساختار احتمالاتی کم‌حافظه برای بررسی عضویت است. می‌تواند بگوید «قطعاً وجود ندارد» یا «احتمالاً وجود دارد»؛ پس false positive ممکن است ولی در مدل استاندارد false negative نداریم.
اول این مفهوم را در ذهن نگه دار
Bloom Filter یک ساختار احتمالاتی کم‌حافظه برای بررسی عضویت است. می‌تواند بگوید «قطعاً وجود ندارد» یا «احتمالاً وجود دارد»؛ پس false positive ممکن است ولی در مدل استاندارد false negative نداریم.
چطور کار می‌کند؟ ساده و مرحله‌ای
هر item با چند Hash به چند موقعیت bit نگاشت می‌شود و آن bitها 1 می‌شوند.
در lookup همان bitها بررسی می‌شوند؛ اگر حتی یکی 0 باشد داده قطعاً نیست، ولی اگر همه 1 باشند فقط احتمال وجود داریم.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
Invariant اصلی ساختار را مشخص کن.
مسیر read/update را در ساختار دنبال کن.
بعد از mutation قبل از return invariant را دوباره برقرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای فیلتر Bloom هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
- علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
trade-off را روشن بگو: حافظه بسیار کم و lookup سریع، در عوض false positive و حذف دشوار در نسخه پایه.
فیلتر Bloom چه مسئله‌ای را حل می‌کند؟
Bloom Filter یک ساختار احتمالاتی کم‌حافظه برای بررسی عضویت است. می‌تواند بگوید «قطعاً وجود ندارد» یا «احتمالاً وجود دارد»؛ پس false positive ممکن است ولی در مدل استاندارد false negative نداریم.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.