מסנן בלום בג'אווה באמצעות גויאבה
1. סקירה כללית
במאמר זה נבחן את מבנה המסנן בלום מה- גויאבה סִפְרִיָה. מסנן בלום הוא מבנה נתונים יעיל וזיכרון, בו נוכל לענות על השאלה האם אלמנט נתון נמצא בקבוצה או לא.
אין שליליות שקריות עם פילטר בלום, אז כשהוא חוזר שֶׁקֶר, אנחנו יכולים להיות בטוחים ב 100% שהאלמנט לא נמצא בערכה.
עם זאת, פילטר בלום יכול להחזיר תוצאות חיוביות כוזבות, אז כשהוא חוזר נָכוֹן, יש סבירות גבוהה שהאלמנט נמצא בערכה, אבל אנחנו לא יכולים להיות בטוחים ב 100%.
לניתוח מעמיק יותר של אופן פעולתו של פילטר בלום, תוכלו לעבור על הדרכה זו.
2. תלות של Maven
נשתמש ביישום של פילטר בלום של גויאבה, אז בואו נוסיף את ה- גויאבה תלות:
com.google.guava גויאבה 29.0-jre ניתן למצוא את הגרסה האחרונה ב- Maven Central.
3. מדוע להשתמש במסנן בלום?
מסנן בלום הוא תוכנן להיות חסכוני בחלל ומהיר. כאשר אנו משתמשים בו, אנו יכולים ציין את ההסתברות לתגובות חיוביות כוזבות שנוכל לקבל ועל פי תצורה זו, מסנן בלום יתפוס מעט זיכרון ככל שיוכל.
בשל יעילות שטח זו, מסנן בלום ישתלב בקלות בזיכרון אפילו עבור מספר עצום של אלמנטים. מסדי נתונים מסוימים, כולל קסנדרה ואורקל, משתמשים במסנן זה כבדיקה ראשונה לפני שהם עוברים לדיסק או למטמון, למשל כאשר נכנסת בקשה למזהה ספציפי.
אם המסנן מחזיר שהמזהה אינו קיים, מסד הנתונים יכול לעצור את המשך עיבוד הבקשה ולחזור ללקוח. אחרת, הוא עובר לדיסק ומחזיר את האלמנט אם הוא נמצא בדיסק.
4. יצירת פילטר בלום
נניח שאנחנו רוצים ליצור מסנן בלום עד 500 שלמים ושאנחנו יכולים לסבול אחוז אחד (0.01) של תוצאות חיוביות שגויות.
אנחנו יכולים להשתמש ב- BloomFilter כיתה מה גויאבה הספרייה כדי להשיג זאת. עלינו להעביר את מספר האלמנטים שאנו מצפים להכניס למסנן ואת ההסתברות החיובית הכוזבת הרצויה:
מסנן BloomFilter = BloomFilter.create (Funnels.integerFunnel (), 500, 0.01);עכשיו בואו נוסיף מספרים למסנן:
filter.put (1); filter.put (2); filter.put (3);הוספנו רק שלושה אלמנטים, והגדרנו שמספר ההכנסות המרבי יהיה 500, אז מסנן הבלום שלנו אמורה להניב תוצאות מדויקות מאוד. בואו לבדוק את זה באמצעות mightContain () שיטה:
assertThat (filter.mightContain (1)). isTrue (); assertThat (filter.mightContain (2)). isTrue (); assertThat (filter.mightContain (3)). isTrue (); assertThat (filter.mightContain (100)). isFalse ();כפי שהשם מרמז, איננו יכולים להיות בטוחים ב 100% שאלמנט נתון אכן נמצא במסנן כאשר השיטה חוזרת נָכוֹן.
מתי mightContain () החזרות נָכוֹן בדוגמה שלנו, אנו יכולים להיות בטוחים ב 99% שהאלמנט נמצא בפילטר, ויש סבירות של אחוז אחד שהתוצאה חיובית כוזבת. כאשר המסנן חוזר שֶׁקֶראנו יכולים להיות בטוחים ב 100% שהאלמנט אינו קיים.
5. פילטר בלום רווי יתר על המידה
כשאנחנו מעצבים את מסנן הבלום שלנו, חשוב לספק ערך מדויק למדי למספר האלמנטים הצפוי. אחרת, המסנן שלנו יחזיר תוצאות חיוביות שגויות בקצב גבוה בהרבה מהרצוי. בואו נראה דוגמא.
נניח שיצרנו פילטר עם הסתברות חיובית כוזבת רצויה של אחוז אחד וצפוי כמה אלמנטים שווים לחמישה, אבל אז הכנסנו 100,000 אלמנטים:
מסנן BloomFilter = BloomFilter.create (Funnels.integerFunnel (), 5, 0.01); IntStream.range (0, 100_000) .forEach (filter :: put); מכיוון שמספר האלמנטים הצפוי הוא כה קטן, המסנן יתפוס מעט מאוד זיכרון.
עם זאת, ככל שאנו מוסיפים יותר פריטים מהצפוי, המסנן הופך לרווי יתר על המידה ויש לו סבירות גבוהה בהרבה להחזיר תוצאות חיוביות כוזבות מהאחוז הרצוי:
assertThat (filter.mightContain (1)). isTrue (); assertThat (filter.mightContain (2)). isTrue (); assertThat (filter.mightContain (3)). isTrue (); assertThat (filter.mightContain (1_000_000)). isTrue ();שים לב שה- mightContatin () שיטה חזר נָכוֹן אפילו עבור ערך שלא הכנסנו לתוך המסנן בעבר.
6. מסקנה
במדריך מהיר זה, בדקנו את האופי ההסתברותי של מבנה נתוני מסנן בלום - תוך שימוש במערכת גויאבה יישום.
תוכל למצוא את היישום של כל הדוגמאות וקטעי הקוד בפרויקט GitHub.
זהו פרויקט של Maven, כך שיהיה קל לייבא ולהפעיל אותו כפי שהוא.
