דף 1 מתוך 1

טבלאות גיבוב - שאלה

נשלח: 22:18 15/07/2010
על ידי ec1
עניין שלא יושב לי כל כך טוב בראש - מדוע כשמחפשים איבר בטבלת גיבוב העלות במקרה הממוצע היא O)1( ?

אני מפספס משהו בהבנה אבל לא בדיוק מבין מה...


תודה!

Re: טבלאות גיבוב - שאלה

נשלח: 22:45 15/07/2010
על ידי ronenhe
תחשוב בתכלס מה עושה טבלת גיבוב (האש) יש לך איבר וב או של 1 אתה מכניס אותו לטבלה (במקרה המושלם) אם זה מקרה לא מושלם אז יש לך עוד האש או שיש לך ציינינג או וואט אבר אבל.. הפונקציה שלך בגדול (פונקציית האש) ממש טוב ובד"כ כל שני איברים שונים יקבלו מקום אחר בתא (באופן ממוצע) במקרה הגרוע יהיו לך מספר קבוע של איברים שילכו לאותו התא ואז יהיה לך עוד כמה פעולות בדידות להגיע לאיבר..
קפיש?

Re: טבלאות גיבוב - שאלה

נשלח: 23:36 15/07/2010
על ידי ec1
זה בהנחה ויש לי פונקציה שמוגדרת "טובה", כלומר - אני מגיע לתא הרלוונטי שאני מחפש בזמן יחסית קבוע ע"י שימוש בפונקציה?

זה התחיל להתבהר לי אחרי שקראתי איזשהו סיכום לפני כמה דקות.

למשל בשאלה 3 שהופיעה במבחן - אני מגדיר טבלת האש בגודל N בריבוע ופונקציה האש שמקשרת בין כל מספר שהיא מקבלת לכתובת הזיכרון שלו במטריצה. אמנם - לא היה צורך לכתוב את זה בפועל, אבל איך למשל תפעל פונקציה כזו?

תודה :)

Re: טבלאות גיבוב - שאלה

נשלח: 23:59 15/07/2010
על ידי Brk
ec1 כתב:זה בהנחה ויש לי פונקציה שמוגדרת "טובה", כלומר - אני מגיע לתא הרלוונטי שאני מחפש בזמן יחסית קבוע ע"י שימוש בפונקציה?

זה התחיל להתבהר לי אחרי שקראתי איזשהו סיכום לפני כמה דקות.

למשל בשאלה 3 שהופיעה במבחן - אני מגדיר טבלת האש בגודל N בריבוע ופונקציה האש שמקשרת בין כל מספר שהיא מקבלת לכתובת הזיכרון שלו במטריצה. אמנם - לא היה צורך לכתוב את זה בפועל, אבל איך למשל תפעל פונקציה כזו?

תודה :)
שים לב שזמני הריצה של טבלת hash נמדדים בזמן ממוצע ולא במקרה הכי גרוע!

Re: טבלאות גיבוב - שאלה

נשלח: 00:01 16/07/2010
על ידי ronenhe
כל העניין בהאש זה שיש לך פונקצייה טובה יש גם את העסק של מקדם העומס (תקרא כבר בספרות)
אני אביא לך דוגמא לפונקציה לא טובה
יש לך מליון מספרים והפונקציה שלך היא פונקציית האפס כלומר לא משנה איזה מספר תכניס לתוכה היא תחזיר 0 עכשיו נגיד הטבלה שלך בגודל מליון אז תחשוב במקרה הכי גרוע כמה זמן ייקח לך להגיע לכל איבר ברור שייקח לך N
עכשיו בוא ניקח את המקרה הקצה השני נניח יש לך מליון מספרים מ1 עד מליון אז תעשה לצורך העניין טבלה בגודל מליון שתשלח כל איבר לעצמו
נכון מבחינת מקום זה לא יעיל אבל זה יבטיח לך שמציאת האיבר תעלה לך או של 1 במקרה הגרוע
הקטע פה הוא שאנחנו עושים משחקים כדי להגיע למינימום מקום ומינימום זמן לחפש
בגדול עבור טבלת האש טובה ייקח לך בממוצע או של אחד זמן להגיע לאיבר.
לגבי שאלה 3
אתה יכול לחשוב על כל פונקציה שהיא שתתן לך בממוצע משהו שונה
אני אישית רשמתי במבחן שהפונקציה תהיה המספר מוד אן בריבוע לא יודע כמה זה יעיל או אם יש משהו עדיף אבל תמיד אפשר לשחק עם זה.
המטרה להגיע למצב כמו שאמרתי מקודם.
בהצלחה במועד ב!

Re: טבלאות גיבוב - שאלה

נשלח: 00:07 16/07/2010
על ידי ec1
אחלה, תודה רבה רונן, אם זה היה תלוי בי - הייתי שולח אותך לתואר שני ובמקביל מצרף אותך לצוות המתרגלים שלנו :)

Brk, סבבה, כלומר - פשוט לא לשכוח שכששואלים על O של 1 בממוצע - לחשוב מיד על טבלת האש. ככה, לא? תודה :)

Re: טבלאות גיבוב - שאלה

נשלח: 00:31 16/07/2010
על ידי Brk
ec1 כתב:אחלה, תודה רבה רונן, אם זה היה תלוי בי - הייתי שולח אותך לתואר שני ובמקביל מצרף אותך לצוות המתרגלים שלנו :)

Brk, סבבה, כלומר - פשוט לא לשכוח שכששואלים על O של 1 בממוצע - לחשוב מיד על טבלת האש. ככה, לא? תודה :)
כן!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! :P
:)
בהצלחה לכולם במועד ב'

Re: טבלאות גיבוב - שאלה

נשלח: 08:28 16/07/2010
על ידי rubichi
ronenhe כתב: הקטע פה הוא שאנחנו עושים משחקים כדי להגיע למינימום מקום ומינימום זמן לחפש
בהצלחה במועד ב!
אין בכלל קשר,
אין פה שום ניסיון להגיע למינימום מקום. אם היו לנו מיליון רשומות ממוספרות מ1 עד מיליון שלא מוסיפים להם עוד רשומות (כלומר מספר קבוע) לא היית משתמש בכלל בטבלת האש. מכיוון שבתכלס אף אחד לא מבטיח לך שהמפתחות שלך יהיו בסדר רץ שמתחיל ב 1 ובלי דילוגים על מספרים, ומכיוון שאתה רוצה גם להוסיף עוד רשומות, טבלת האש היא טובה כי שם אתה יכול להוסיף רשומות בלי להקצות מקום חדש ולהעתיק את כל המבנה.
ולצורך העניין אם היו לי מיליון רשומות, תהיה בטוח שהיית יוצר טבלת גיבוב של לפחות מיליון מקומות (עבור צ'יינינג, עבור אופן-אדרסינג היית צריך הרבה יותר ממיליון בשביל שזה יצדיק את עצמו).

Re: טבלאות גיבוב - שאלה

נשלח: 12:08 16/07/2010
על ידי ronenhe
rubichi כתב:
ronenhe כתב: הקטע פה הוא שאנחנו עושים משחקים כדי להגיע למינימום מקום ומינימום זמן לחפש
בהצלחה במועד ב!
אין בכלל קשר,
אין פה שום ניסיון להגיע למינימום מקום. אם היו לנו מיליון רשומות ממוספרות מ1 עד מיליון שלא מוסיפים להם עוד רשומות (כלומר מספר קבוע) לא היית משתמש בכלל בטבלת האש. מכיוון שבתכלס אף אחד לא מבטיח לך שהמפתחות שלך יהיו בסדר רץ שמתחיל ב 1 ובלי דילוגים על מספרים, ומכיוון שאתה רוצה גם להוסיף עוד רשומות, טבלת האש היא טובה כי שם אתה יכול להוסיף רשומות בלי להקצות מקום חדש ולהעתיק את כל המבנה.
ולצורך העניין אם היו לי מיליון רשומות, תהיה בטוח שהיית יוצר טבלת גיבוב של לפחות מיליון מקומות (עבור צ'יינינג, עבור אופן-אדרסינג היית צריך הרבה יותר ממיליון בשביל שזה יצדיק את עצמו).
כמו שכבר רשמתי... נתתי דוגמאות קיצוניות.. אחת לפונקציה ממש גרועה והשני לפונקצייה ממש טובה.
אם יש לך דוגמאות אחרות אני אשמח לשמוע.
בשורה התחתונה כדאי לך להגיע למינימום מקום ולמינימום זמן (לפי מקדם העומס בלה בלה) אם לא באופן פורמלי מבחינת הקורס אז באופן מעשי..
כמו שאתה שם לב הדוגמאות שלי לא פורמליות.. אני מנסה להסביר לבן אדם כדי שיבין את העיקרון ולא שיזכור כמו תוכי.

בדוגמא השנייה אם לא רשמתי מדובר במליון מספרים עוקבים .. (בשביל הפשטות של הדוגמא ) מה שכן.. שאפו על הניתוח של הבעיה שהבאתי :)
בהצלחה!