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

מנהל: TA_Isana

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

הודעהעל ידי ec1 » 21:18 15/07/2010

עניין שלא יושב לי כל כך טוב בראש - מדוע כשמחפשים איבר בטבלת גיבוב העלות במקרה הממוצע היא O)1( ?

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


תודה!
ec1
 
הודעות: 11
הצטרף: 18:16 22/12/2009

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

הודעהעל ידי ronenhe » 21:45 15/07/2010

תחשוב בתכלס מה עושה טבלת גיבוב (האש) יש לך איבר וב או של 1 אתה מכניס אותו לטבלה (במקרה המושלם) אם זה מקרה לא מושלם אז יש לך עוד האש או שיש לך ציינינג או וואט אבר אבל.. הפונקציה שלך בגדול (פונקציית האש) ממש טוב ובד"כ כל שני איברים שונים יקבלו מקום אחר בתא (באופן ממוצע) במקרה הגרוע יהיו לך מספר קבוע של איברים שילכו לאותו התא ואז יהיה לך עוד כמה פעולות בדידות להגיע לאיבר..
קפיש?
ronenhe
 
הודעות: 182
הצטרף: 10:27 28/10/2009

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

הודעהעל ידי ec1 » 22:36 15/07/2010

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

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

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

תודה :)
ec1
 
הודעות: 11
הצטרף: 18:16 22/12/2009

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

הודעהעל ידי Brk » 22:59 15/07/2010

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

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

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

תודה :)


שים לב שזמני הריצה של טבלת hash נמדדים בזמן ממוצע ולא במקרה הכי גרוע!
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי ronenhe » 23:01 15/07/2010

כל העניין בהאש זה שיש לך פונקצייה טובה יש גם את העסק של מקדם העומס (תקרא כבר בספרות)
אני אביא לך דוגמא לפונקציה לא טובה
יש לך מליון מספרים והפונקציה שלך היא פונקציית האפס כלומר לא משנה איזה מספר תכניס לתוכה היא תחזיר 0 עכשיו נגיד הטבלה שלך בגודל מליון אז תחשוב במקרה הכי גרוע כמה זמן ייקח לך להגיע לכל איבר ברור שייקח לך N
עכשיו בוא ניקח את המקרה הקצה השני נניח יש לך מליון מספרים מ1 עד מליון אז תעשה לצורך העניין טבלה בגודל מליון שתשלח כל איבר לעצמו
נכון מבחינת מקום זה לא יעיל אבל זה יבטיח לך שמציאת האיבר תעלה לך או של 1 במקרה הגרוע
הקטע פה הוא שאנחנו עושים משחקים כדי להגיע למינימום מקום ומינימום זמן לחפש
בגדול עבור טבלת האש טובה ייקח לך בממוצע או של אחד זמן להגיע לאיבר.
לגבי שאלה 3
אתה יכול לחשוב על כל פונקציה שהיא שתתן לך בממוצע משהו שונה
אני אישית רשמתי במבחן שהפונקציה תהיה המספר מוד אן בריבוע לא יודע כמה זה יעיל או אם יש משהו עדיף אבל תמיד אפשר לשחק עם זה.
המטרה להגיע למצב כמו שאמרתי מקודם.
בהצלחה במועד ב!
ronenhe
 
הודעות: 182
הצטרף: 10:27 28/10/2009

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

הודעהעל ידי ec1 » 23:07 15/07/2010

אחלה, תודה רבה רונן, אם זה היה תלוי בי - הייתי שולח אותך לתואר שני ובמקביל מצרף אותך לצוות המתרגלים שלנו :)

Brk, סבבה, כלומר - פשוט לא לשכוח שכששואלים על O של 1 בממוצע - לחשוב מיד על טבלת האש. ככה, לא? תודה :)
ec1
 
הודעות: 11
הצטרף: 18:16 22/12/2009

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

הודעהעל ידי Brk » 23:31 15/07/2010

ec1 כתב:אחלה, תודה רבה רונן, אם זה היה תלוי בי - הייתי שולח אותך לתואר שני ובמקביל מצרף אותך לצוות המתרגלים שלנו :)

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


כן!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! :P
:)
בהצלחה לכולם במועד ב'
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי rubichi » 07:28 16/07/2010

ronenhe כתב:הקטע פה הוא שאנחנו עושים משחקים כדי להגיע למינימום מקום ומינימום זמן לחפש
בהצלחה במועד ב!


אין בכלל קשר,
אין פה שום ניסיון להגיע למינימום מקום. אם היו לנו מיליון רשומות ממוספרות מ1 עד מיליון שלא מוסיפים להם עוד רשומות (כלומר מספר קבוע) לא היית משתמש בכלל בטבלת האש. מכיוון שבתכלס אף אחד לא מבטיח לך שהמפתחות שלך יהיו בסדר רץ שמתחיל ב 1 ובלי דילוגים על מספרים, ומכיוון שאתה רוצה גם להוסיף עוד רשומות, טבלת האש היא טובה כי שם אתה יכול להוסיף רשומות בלי להקצות מקום חדש ולהעתיק את כל המבנה.
ולצורך העניין אם היו לי מיליון רשומות, תהיה בטוח שהיית יוצר טבלת גיבוב של לפחות מיליון מקומות (עבור צ'יינינג, עבור אופן-אדרסינג היית צריך הרבה יותר ממיליון בשביל שזה יצדיק את עצמו).
rubichi
 
הודעות: 77
הצטרף: 18:50 22/10/2009

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

הודעהעל ידי ronenhe » 11:08 16/07/2010

rubichi כתב:
ronenhe כתב:הקטע פה הוא שאנחנו עושים משחקים כדי להגיע למינימום מקום ומינימום זמן לחפש
בהצלחה במועד ב!


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


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

בדוגמא השנייה אם לא רשמתי מדובר במליון מספרים עוקבים .. (בשביל הפשטות של הדוגמא ) מה שכן.. שאפו על הניתוח של הבעיה שהבאתי :)
בהצלחה!
ronenhe
 
הודעות: 182
הצטרף: 10:27 28/10/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד