דף הבית של הווידאו שלנו מציג כעת סט טרי של 24 המלצות בכל רענון, הודות למעבר לשיטת weighted reservoir sampling (A-Res). השינוי ביטל את בעיית ה-"same-grid-forever" שעינה על הפיד הממוין לפי ציונים הקודם שלנו.

למה הגישה הישנה הרסה את חוויית המשתמש

מדי שעתיים אנו שואבים את סרטוני הטרנד האחרונים משמונה אזורים ושומרים את התוצאות בטבלת SQLite. הפתרון הנאיבי היה למיין את כל הקבוצה – לפי ציון רלוונטיות – ולקחת את 24 הראשונים. השיטה הזו מבטיחה שהפריטים בעלי הציון הגבוה ביותר יופיעו, אך היא גם מבטיחה שהם יישארו שם. סרטון ויראלי בודד יכול להשתלט על המקום הראשון במשך ימים, והמשתמשים רואים רשת זהה בכל פעם שהם מרעננים את הדף.

מעבר לחוויה המשעממת והסטטית, מיון הטבלה כולה עבור כל בקשה מאלץ את SQLite לטעון מבנה זמני גדול לזיכרון, מה שגורם לבזבוז משאבים.

מה weighted reservoir sampling מעניק לנו

weighted reservoir sampling פותר שני בעיות בבת אחת:

  1. רעננות עם הטיה (bias) – הסיכוי של כל סרטון להיבחר הוא יחסי למשקל שלו (למשל, ציון רלוונטיות). סרטון עם משקל כפול הוא בעל סיכוי כפול להופיע, אך אף פריט אינו מובטח במקום מסוים.
  2. יעילות זיכרון – האלגוריתם שומר רק "מאגר" (reservoir) בגודל קבוע של k פריטים (k = 24 עבור הפיד שלנו). הוא מעבד את הזרם (stream) במעבר יחיד, כך שהזיכרון נשאר O(k) ללא קשר למספר המועמדים שמגיעים.

הרעיון המרכזי הוא פשוט. בזמן שאנו סורקים את השורות הנכנסות, אנו מקצים לכל פריט מפתח אקראי המשלב את המשקל שלו, ולאחר מכן שומרים את k הפריטים בעלי המפתחות הגבוהים ביותר.

האלגוריתם בפועל

עבור כל סרטון אנו:

  1. שולפים מספר אקראי אחיד u ∈ (0, 1).
  2. מחשבים מפתח k = u^(1/weight).
    (ככל שהמשקל גבוה יותר, המפתח הצפוי יהיה גדול יותר.)
  3. מכניסים את הפריט ל-min-heap השומר את k המפתחות הגבוהים ביותר כרגע.
    אם ה-heap חורג מגודל k, אנו משמיטים את המפתח הקטן ביותר.

כשהזרם מסתיים, ה-heap מכיל את 24 הסרטונים שיוצגו.

התמודדות עם מגבלות נקודה צפה (floating-point)

כאשר המשקל של סרטון הוא גדול מאוד, u^(1/weight) קורס לערך שאינו ניתן להבחנה מ-1.0 בחישוב דיוק כפול (double-precision), מה שגורם לפריטים "כבדים" רבים לחלוק את אותו מפתח ולאבד את האקראיות. הפתרון הוא לעבוד במרחב לוגריתמי (log space):

  • מחשבים log_key = log(u) / weight במקום ביטוי החזקה.

מכיוון שלוגריתמים הופכים חזקה לכפל, סדר המפתחות נשמר תוך הימנעות מ"צוק הדיוק" (precision cliff). החישוב כמעט ואינו כרוך בעלות נוספת.

צ'קליסט למימוש

  • מבנה נתונים: min-heap (תור עדיפויות) בגודל k שומר את המפתחות הגדולים ביותר ביעילות (O(log k) לכל הכנסה).
  • סוג נתונים מספרי: השתמשו במספרים בנקודה צפה של 64 סיביות עבור u ועבור המפתחות המבוססים על לוגריתמים; הם מספקים דיוק מספק עבור טווחי משקלים טיפוסיים.
  • בדיקת תקינות סטטיסטית: הריצו מבחן Monte-Carlo מהיר על סט דגימה קטן. אם פריטים עם משקל 10 מופיעים בערך פי עשרה יותר מאשר פריטים עם משקל 1, המימוש תקין.
  • סטרימינג במעבר יחיד (Single-pass): האלגוריתם אינו צריך לדעת מראש את מספר המועמדים הכולל, מה שמתאים באופן טבעי לסמן (cursor) ה-SQLite שלנו שמחזיר שורות אחת אחת.

שורה תחתונה

weighted reservoir sampling מאפשר לשירות המלצות וידאו לשמור על דף הבית שלו רענן, לכבד את ציוני הרלוונטיות ולהישאר קל בשימוש בזיכרון – וכל זאת במעבר יחיד על עשרות אלפי מועמדים. על ידי העברת חישוב המפתח למרחב לוגריתמי ושימוש ב-min-heap, השיטה נשארת מדויקת ובעלת ביצועים גבוהים.