ארזים

סלוגן חזק ומגניב

Cuckoo hashing

שאלות:

• מהי פריצת הדרך הגדולה שהמאמר הציג?

אבסטרקט

• האם זה החסם הנמוך התיאורטי? מה אפשר לומר על זה?
• כמה כבד מבחינץ מקום זה עצי חיפוש בינארים (הרבה או מעט) (2n לעומת 35n בקלאסי של הגרמני)
• מה זה perfect, open address hashin
• מהו היישום הפחות טוב אך שימושי? (כנראה זה שלא באמת מקסלופ-יונברסלית, לבדוק איפה זה)
• מבטיח וורסט-קייס, ומתחרה בממוצע (מה זה אומר? שלא ממש לא פרקטי)

1. הקדמה

• מה ההבדל מבחינת יעילות ממה שלמדנו במבני נתונים? (מקום, זמן) [זה אני משווה מול chained]
• מה זה Classic Dictionary of Dietzfelbinger [אני צריך לבדוק אם אני רוצה]

1.1 מוקדמות

• להתעמק בהגדרה של משפחות אוניברסליות (להשוות למבני נתונים)
• איך מסמלצים k קטן עם K גדול

2 קוקו האשינג

• מחקר רציני מה זה [26] (פרפקט?)
• להתעמק

2.1 פונקציות האש

• מה סגל אמר
• מה מהות הסיכוי של בנייה של משפחת פונקציות עבור r בריבוע
• למה לבנות עם סיכוי? למה לא לבנות מראש? (כי זה יקר)
• מהו description of function (קוד הפונקציה, הוא דואג)

2.3 ניתוח

• מה המשמעות המשפט האחרון לפני הלמה? (האם הלולאה זה לולאת הקוד או לולאה של תאים) - לולאה של הלוך וחזור
• למה 1 - האם מעגלים למטה או למעלה בחילוק? (למעלה כי אם למטה לא יהיה לפחות שליש)
• איך קובעים את הגודל של MaxLoop? (סוף עמוד 8 הפתרון)
• מה המטרה של לעשות ריהאש אחרי R בריבוע פעולות? מה מנסים למנוע?
• לשחק עם דוגמאות של הכנסות עם לופים שמסתדרים ושלא
• להבין את שלושת המקרים שבהם עושה יותר מ-T איטרציות (ספציפית מקרה 2 - מה ההסבר עם ה-L אומר?)

אנחנו מכניסים הרבה איברים חדשים

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

מסקנות מהניתוח

• להבין את התוצאה
• מה זה אומר O(1/n), ומה זה יותר טוב מקבוע?

4. ניסויים

• מה טוב בדאבל צ'יינינג (אולי לשפר את זמן החיפוש של ערכים אחרים ולא של עצמו) - אני אקרא על זה
• להבין את DIMACS - שנינו להבין

5. סיכום

שאלות:

• משיכה מבנק
• השראות
• חולי סוכרת