שאלה בC - מישהו יודע?

[Dafna101]

שאלה בC - מישהו יודע?

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

 

[vinney]

סליחה על השאלה

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

 

[Dafna101]

זו הדרישה שבשאלה..

השאלה לקוחה מראיון עבודה. הפתרון לא עונה על הדרישות? אני לא הכי מבינ*ה* בזה וזה למה רציתי להתייעץ עם מי שכן מבין ולשמוע רעיונות אחרים בשביל ללמוד. אולי אתה יודע לעזור לי?

 

[vinney]

שונא מראיינים ששואלים שאלות כאלה...

כשמבקשים משהו "יעיל ביותר", איך בדיוק הם מצפים שתוכיחי שהפתרון שלך הוא אכן יעיל ביותר

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

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

 

[Dafna101]

תודה רבה =) יצא לך אולי לחשוב על פתרון אחר?

 

[vinney]

לא