שאלה במבני נתונים

[metilen]

שאלה במבני נתונים

אני צריך לבנות מבנה נתונים שמסמלץ מערך כך שלכל אחד מהפעולות להלן: אתחול מערך בגודל n (בכל המקומות יהיו אפסים). הכנסת איבר לסוף המערך (הכנסת איבר למקום הראשון שפנוי במערך) הוצאת איבר מאינדקס i בדיקה האם קיים איבר באינקס i יקח (O (1 זמן. יש למישהו מושג איך להתחיל?

 

[arik23m]

איך להתחיל

- להתחיל לקרוא על מבנה נתונים שמתיימרים לספק כזו יעילות: Hash table Dictionary ודומיהן... ולחשוב איך לממש אותם. אגב, לא ציינת את שפת הפיתוח.

 

[vinney]

שפת הפיתוח לא משנה לצורך העניין

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

 

[arik23m]

למה לקשקש סתם?

אני ממש לא מחבב (בלשון המעטה) את הזחיחות שלך והשחצנות.. http://en.wikipedia.org/wiki/Hash_table#Time_complexity_and_common_uses_of_hash_tables

 

[vinney]

שחצנות זה להגיד "למה לקשקש סתם" למי שיודע

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

 

[arik23m]

ורשימה מקושרת

זה O)n). http://en.wikipedia.org/wiki/Linked_list

 

[vinney]

בקיצור

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

רמז - לא צריך שום מבנה נתונים יוצא דופן, חוץ מהמערך עצמו ועוד קצת. שים לב - המערך לא חייב להיות ממוין. אני מניח שזה מה שמבלבל אותך.

 

[arik23m]

יפה

שירדת מהעץ של רשימה מקושרת... וטבלת האש זה באמת דומה למערך רק שיש בה פונקצית Hash ולא מספרים רצים 0...n ופונקצית ההאש הזו היא זו יוצרת את הקישור בין הנתונים ל"מפתחות". אבל זה לא אמור להיות מערך כי בקשו לבנות מבנה נתונים.. ואני את התרגילים שלי כבר עשיתי.. תודה.

 

[vinney]

תגיד, אתה רוצה לנהל את הפורום הזה?

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

 

[immortalus]

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

כי אם באמת היית עושה את התרגילים שלך אולי היית יודע שטבלת ערבול (hash table) לא תעמוד בדרישות הסיבוכיות שכן היא עובדת בסיבוכיות ממוצעת שהיא שונה במהות מסיבוכיות המקרה הגרוע ובקשר לרשימה מקושרת, קל מאד להכנס ל-Wiki, לראות שלעבור על רשימה מקושרת לוקח (O(n ולהחליט שגילית את אמריקה, אלא שאתה לא חייב להשתמש במבנה נתונים בצורה הטריביאלית שלו. לצורך העניין אפשר לקחת רשימה מקושרת דו-כיוונית, עם מצביעים לאיברים שלה ממערך ולממש מחיקה ומציאת האיבר הבא בסיבוכיות נמוכה משמעותית מ-(O(n... אולי לך כדאי לרדת מהעץ, כי למרות שחיפוש מידע באינטרנט היא ללא ספק יכולת חשובה (מאד) לעיתים צריך לדעת גם לנתח את המידע שאתה מוצא בו...

 

[arik23m]

ממש לא לענין התגובה שלך....

אני לא חושב שמישהו בקש תגבורת.... לא אני ולא ויני. ואם שנים דנים על משהו (כן יש לנו "עבר" כנראה..) אז מה לך להכניס את הראש בין לבין..? לגופו של ענין, אכן הפתרון שלך משפר את היעילות של הרשימה המקושרת. ואגב גם זה נמצא בויקי: http://en.wikipedia.org/wiki/Linked_list#Linked_lists_using_arrays_of_nodes ורצוי לעיין בכל המאמר שם (יש חסרונות לשיטה). ולדעתי יש יותר מפתרון אחד לשאלה ובהחלט טבלת האש היא פתרון ואפילו אומר פתרון טוב יותר. ראשית, שמחתי לגלות שנכנסת ללינק שהגשתי לעיל אבל כנראה שהבנת אותו לא נכון.... אין המדובר בסיבוכיות ממוצעת (טטא), אלא בממוצע בין כל מליוני המליונים הטבלאות האש שבעולם הסיבוכיות תהיה O של 1. תמיד הסיבוכיות נבחנת לפי O ולא לפי טטא ותמיד נלקח ה-worst-case scenario לצורך חישוב הסיבוכיות. ואביא פה את הלשון המדויקת: " hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. While theoretically the worst-case lookup time can be as bad as O, this is, for practical purposes, statistically unlikely unless the hash function is poorly designed or unless ... " לויני - אני אענה לך פה - לגבי ניהול הפורום אני רואה שאתה ממש קשור לפורום הזה בנימי נפשך... זה מופיע לך בדיי הרבה שרשורים.. אתה דוגר על הביצים אני רואה.. בודק שאף תרנגול לא מתקרב?

ותודה על ההצעה בכל מקרה. גם על השליחת קוד אני מוותר. בקיצור מה שחשוב זה שמהשרשורים הללו מתבררת התשובה\ות האמיתית והמדויקת..

 

[vinney]

שמע...ראה...

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

 

[arik23m]

ok

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

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

 

[vinney]

מטרת השאלה זה להכריח אותך לחשוב מחוץ לקופסא

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

 

[tamarhp]

זה תרגיל ראשון בקורס!

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

 

[vinney]

ככה

<קליק>

 

[tamarhp]

וואו. מגעיל.

 

[vinney]

השואל דווקא פתר את השאלה עם רשימה מקושרת

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

 

[tamarhp]

איך אפשר עם רשימה מקושרת?

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

 

[vinney]

המשפט האחרון

"נצטרך לעדכן את כל המצביעים במערך מאותו i והלאה" - לא נכון.