لینک کوتاه مطلب : https://hsgar.com/?p=5930

از HN بپرسید: برخی از ساختارهای داده “باحال” اما مبهم که درباره آنها می دانید چیست؟

من بسیار علاقه مند هستم بدانم که چه نوع ساختارهای داده جالبی وجود دارد.ا

شروع می کنم:  bloom filters. به شما امکان می دهد آزمایش کنید که آیا یک مقدار قطعاً در لیست مقادیر از پیش ذخیره شده نیست (یا احتمالاً در یک لیست – با احتمال قابل تنظیم که بر ذخیره مقادیر تأثیر می گذارد.)

مورد استفاده خوب: routing. فرض کنید لیستی از 1 میلیون IP دارید که در لیست سیاه قرار دارند. یک الگوریتم بی اهمیت این است که هر عنصر مجموعه را با یک IP معین مقایسه کنید. پیچیدگی زمانی با تعداد عناصر افزایش می یابد. در مورد فیلتر شکوفه اینطور نیست! فیلتر شکوفایی یکی از معدود ساختارهای داده‌ای است که پیچیدگی زمانی آن با تعداد عناصر افزایش نمی‌یابد زیرا «کلیدها» نیازی به ذخیره ندارند («جستجو» و «درج» بر اساس تعداد توابع هش است.)

بخش پاداش: مجموعه های کدگذاری شده گلومب شبیه فیلترهای شکوفه هستند اما فضای ذخیره سازی بسیار کوچکتر است. هر چند عملکرد بدتر.

لینک منبع

ارسال یک پاسخ

آدرس ایمیل شما منتشر نخواهد شد.