רוטר - שאלה בלתי פתירה שקבלנו במבנה נתונים, אשמח לעזרתכם

האשכול	מחבר	תאריך כתיבה	מספר
תנסה לחשוב על מערך דינמי	Dark-Wish	08.05.15 00:40	1
שמע לצערי לא הבנתי לגמרי על מה אתה מדבר אבל זה נשמע הכי קרוב	כמה עוד	08.05.15 01:24	4
גר ב-ד' שכן שלך.	Zeet3x	10.05.15 11:05	22
ותודה רבה על העזרה	כמה עוד	08.05.15 08:57	6
לא כל כך הבנתי מה הקאץ' פה	simond15	08.05.15 01:09	2
מה שאתה מדבר עליו מסתמך על חישוב של עלות לשיעורין של O(1	כמה עוד	08.05.15 01:23	3
לא זה לא. אתה מבצע אלוקציה בהתחלה של נניח N איברים	ldan192	08.05.15 01:43	5
ממה שהבנתי מהמתרגלים, הם רוצים להימנע מהפעולה בעלות N בפעם ב..	כמה עוד	08.05.15 08:57	7
אני לא רואה שום עדות לזה. להפך, בפירוש אומרים לך שתניח שמחיקת מערך	ldan192	08.05.15 10:20	8
אגב, האופציה האחרת היא רשימה מקושרת + hashtable + אופסט	ldan192	08.05.15 10:24	9
אסור לנו להשתמש ב hashtable בפתרון של השאלה הזאת	כמה עוד	08.05.15 12:06	10
אז אין פתרון אחר חוץ מהמערך וה-realloc פעם ב	Alonso	08.05.15 17:51	11
זה בדיוק מה שרשמתי, ואז אין פתרון אחר, במיוחד כשמחיקות (וכנראה אלוקציות)	ldan192	08.05.15 19:49	12
אם תתעמקו תראו שבפתרון שרשמתי מתבצעת עבודה ב-O1 ולא בניתוח armortized	Dark-Wish	08.05.15 23:59	13
ה-amortized היה כי התייחסתי לזה בטעות כ-queue ולא stack	ldan192	09.05.15 11:49	15
Alonso ו Idan אני מסכים איתכם שהשאלה מפגרת.. אך מה נעשה שזו	כמה עוד	09.05.15 09:15	14
כי צריך לדעת את השאלה הנכונה. תשאל אם סיבוכיות אלוקציה בגודל N היא (O(1	ldan192	09.05.15 11:51	16
מישהו אחר שאל ואלקוציה לוקחת O(1	כמה עוד	09.05.15 12:55	17
כמו שתיארתי לעצמי. לא צריך להסתבך, הרעיון מאוד פשוט	ldan192	09.05.15 21:02	18
תודה רבה, אם הבנתי נכון מדובר במערך של מצביעים	כמה עוד	09.05.15 22:57	19
חשבתי אולי במידה ונגמר לי המקום במערך המצביעים אז לפתוח מערך חדש של מצביעים	כמה עוד	09.05.15 22:58	20
הבעיה בשימוש בהקצאה דינמית (linked list)	ldan192	09.05.15 23:09	21
אם יש לך הנחה על מספר האיברים אז סיימת את השאלה.	ShocKi	10.05.15 23:57	23
פתרון (דומה לתגובה 1)	Deuce	11.05.15 23:07	24
עכשיו הבנתי את מה שהתכוון Dark-Wish במימוש. אלגנטי ונכון (עד כדי כפולה בקבוע :))	ldan192	11.05.15 23:18	25
אבל איך אתה מבצע את אותה העתקה?	ShocKi	11.05.15 23:36	26
היית צודק אם זה היה וקטור, אבל אתה צריך לזכור שמדובר ב-Stack	ldan192	11.05.15 23:59	27
זה לא מה שהתכוונתי אליו...	ShocKi	12.05.15 01:56	28
המנגנון די פשוט.	Zippo	12.05.15 21:58	29
God is in the details.	Deuce	12.05.15 23:24	30
תודה רבה לכולם, גאה באשכול הזה	כמה עוד	13.05.15 00:40	31

Dark-Wish
חבר מתאריך 25.5.05
12585 הודעות, דרג אמינות חבר זה

00:40 08.05.15

1. תנסה לחשוב על מערך דינמי
בתגובה להודעה מספר 0

זה לא אמור להיות דווקא קשור לניתוח לשיעורין
לדוגמה:
נניח שאתה מתחיל עם מערך 1 בגודל 10
צור מערך 2 בגודל 20
על כול הכנסה למערך 1, הכנס את הערך לאותו האינדקס במערך 2
כשמערך 1 מלא - עבור למערך 2, וצור מערך 3 בגודל 40
על כול הכנסה של איבר למערך 2, העתק 2 איברים ראשונים למערך 3
אחרי 10 הכנסות, מערך 2 מלא. אבל: למערך 3 יש 20 תאים פנויים
באותו אופן תמשיך עם מערך 4 גודל 80 וכן האלה (שים לב שהפעם הראשונה היא יוצאת דופן)
צור מונה על מנת לעקוב אחרי מספר האיברים במערך, וככה למעשה תעקוב אחר האינדקס בו אתה תצטרך להכניס איבר ותוכל לדעת האם המחסנית ריקה
כמובן גישה לכול איבר במערך הינה O1
הבעיה: פעולת POP, הפתרון הוא דומה.. צריך להשקיע עוד חשיבה אבל זה פתיר בגישה הזאת
יכול להיות שתצטרך לתמוך בגישה של מערך מעגלי בגלל הפעולות POP, או שאולי תוכל להתעלם מהם
תצטרך להוסיף תמיכה לחזור אחורה: לדוגמה לאחר N הכנסות שבוצעו, ואתה עושה N הוצאות, אתה מקבל לפי התיאור למעלה מערך גודל N למרות שהמערך מכיל איבר אחד
הפתרון לזה הוא ביצוע מערך נוסף, נקרא לו מערך 0 שגודלו כחצי מהמערך הראשון, ובו עבור כול 2 הכנסות למערך 1 אתה מבצע הכנסה אחת למערך 0

@כמה עוד@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

01:24 08.05.15

4. שמע לצערי לא הבנתי לגמרי על מה אתה מדבר אבל זה נשמע הכי קרוב
בתגובה להודעה מספר 1

שראיתי עד עכשיו לפתרון
איך אני יכול לדבר איתך שתסביר לי קצת יותר בפרוט?זה לעבודת הגשה וכל העבודה מוכנה חוץ מזה ואני מת להביא פה 100
@Dark-Wish@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zeet3x

חבר מתאריך 14.2.12
10370 הודעות, 24 פידבק, 18 נקודות

11:05 10.05.15

22. גר ב-ד' שכן שלך.
בתגובה להודעה מספר 4

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

08:57 08.05.15

6. ותודה רבה על העזרה
בתגובה להודעה מספר 1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

simond15

חבר מתאריך 21.8.10
1152 הודעות, 3 פידבק, 6 נקודות

01:09 08.05.15

2. לא כל כך הבנתי מה הקאץ' פה
בתגובה להודעה מספר 0

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

01:23 08.05.15

3. מה שאתה מדבר עליו מסתמך על חישוב של עלות לשיעורין של O(1
בתגובה להודעה מספר 2

חלק מהפעולות הן יהיו ב O(n (הפעולות של הכנסה והכפלה של המערך

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

01:43 08.05.15

5. לא זה לא. אתה מבצע אלוקציה בהתחלה של נניח N איברים
בתגובה להודעה מספר 3

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

אבל מכיוון שאתה עושה את זה בצורה דיי נדירה (נניח פעם ב-N פעולות),
בממוצע תבצע ((O(1)*N + 1*O(N) חלקי N + 1 שנותן לך פעולה משוערכת ב-(O(1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

08:57 08.05.15

7. ממה שהבנתי מהמתרגלים, הם רוצים להימנע מהפעולה בעלות N בפעם ב..
בתגובה להודעה מספר 5

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

10:20 08.05.15

8. אני לא רואה שום עדות לזה. להפך, בפירוש אומרים לך שתניח שמחיקת מערך
בתגובה להודעה מספר 7

לוקחת (O(1 - שכמובן נכון בלי קשר, כלומר אתה צריך להשתמש בזה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

10:24 08.05.15

9. אגב, האופציה האחרת היא רשימה מקושרת + hashtable + אופסט
בתגובה להודעה מספר 8

אבל אז ה-amortized time של ה-hashtable יתן בדיוק מה שאני הצעתי בכל מקרה...
אין לך דרך להתחמק מזה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

12:06 08.05.15

10. אסור לנו להשתמש ב hashtable בפתרון של השאלה הזאת
בתגובה להודעה מספר 9

מה דעתך על הפתרון שהוצא על ידי dark-wish?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Alonso

חבר מתאריך 20.9.12
4048 הודעות, 5 פידבק, 5 נקודות

17:51 08.05.15

11. אז אין פתרון אחר חוץ מהמערך וה-realloc פעם ב
בתגובה להודעה מספר 10

נשלח ע"י הסלולרי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

19:49 08.05.15

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

צריך להניח שניתן לקבל בחינם.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dark-Wish
חבר מתאריך 25.5.05
12585 הודעות, דרג אמינות חבר זה

23:59 08.05.15

13. אם תתעמקו תראו שבפתרון שרשמתי מתבצעת עבודה ב-O1 ולא בניתוח armortized
בתגובה להודעה מספר 12

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

11:49 09.05.15

15. ה-amortized היה כי התייחסתי לזה בטעות כ-queue ולא stack
בתגובה להודעה מספר 13

הפתרון זהה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

09:15 09.05.15

14. Alonso ו Idan אני מסכים איתכם שהשאלה מפגרת.. אך מה נעשה שזו
בתגובה להודעה מספר 0

דרישת המתרגל?
תמונת מסך מתוך הפורום של הקורס אחרי ששאלתי אותו על פתרון שלמערך דינמי
http://rotter.name/User_files/nor/554da694398c3e12.jpg

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

11:51 09.05.15

16. כי צריך לדעת את השאלה הנכונה. תשאל אם סיבוכיות אלוקציה בגודל N היא (O(1
בתגובה להודעה מספר 14

אם לא, אתה חייב להקצות באתחול מערך עצום ולהגביל את גודל ה-stack

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

12:55 09.05.15

17. מישהו אחר שאל ואלקוציה לוקחת O(1
בתגובה להודעה מספר 16

ערכתי לאחרונה בתאריך 09.05.15 בשעה 13:01 בברכה, כמה עוד

@ldan192@

אשמח לעזרה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

21:02 09.05.15

18. כמו שתיארתי לעצמי. לא צריך להסתבך, הרעיון מאוד פשוט
בתגובה להודעה מספר 17

יש לך מערך אינדקסים (פויינטרים) ראשון בגודל 4096, ואינדקסים למשחק.
בפעם הראשונה שאתה דוחף איבר, אתה בודק את התא של האינדקס הנוכחי,
אם הוא Null, תקצה זכרון בגודל 1MB ותפנה את הפויינטר אליו.
ברגע שאתה דוחף וממלא 1MB, אתה מעלה את האינדקס הנוכחי ב-1 וממשיך ככה.
ברגע שאתה עושה pop ומרוקן את ה-1MB אתה יכול למחוק את האלוקציה ולהוריד את האינדקס הנוכחי.
כדי לגשת לאיבר k, אתה מבצע k % 1MB indexes ומשם קופץ לאופסט באלוקציה של ה-1MB.
כמובן זה מימוש שמגביל אותך ל-4GB אלוקציות, אבל באותה מידה אפשר גם להקצות מערך עם יותר פויינטרים עד לכמות "בלתי מוגבלת" של זכרון.

בגדול הקונספט הזה לא חדש, ככה ה-metadata ב-FAT32 עובד (פחות או יותר).

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

22:57 09.05.15

19. תודה רבה, אם הבנתי נכון מדובר במערך של מצביעים
בתגובה להודעה מספר 18

שכל מצביע יכול להצביע למערך בגודל 1024 תאים (נניח וכל תא בן 1KB)
אני אשמח אם תוכל לחדד איך אני עושה את הפתרון הזה לא מוגבל
יש איזה דרך דינאמית? מרגיש לי כאילו לפתוח מערך בגודל intMax זה טיפה שכונה
תודה רבה עידן
@ldan192@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

22:58 09.05.15

20. חשבתי אולי במידה ונגמר לי המקום במערך המצביעים אז לפתוח מערך חדש של מצביעים
בתגובה להודעה מספר 19

אבל אז אני בבעיה עם הפעולה find S[i כי כדי לעבור אל המערכי מצביעים הבאים אני בבעיונת מבחינת זמני ריצה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

23:09 09.05.15

21. הבעיה בשימוש בהקצאה דינמית (linked list)
בתגובה להודעה מספר 19

היא שחיפוש שהוא לא (amortized O(1 יקח זמן לפחות לוגריתמי, אחרת היינו יכולים לפתור את בעיית החיפוש בזמן לינארי.
אתה לא צריך intMax כי אז זה באמת בזבוז זכרון.
הרעיון הוא להקצות "בלוקים" עד כדי שימוש מקסימלי בזכרון.

תשאל אותו אם ניתן לבצע הנחה על מספר מקסימלי של איברים / שימוש בזכרון.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20215 הודעות, 10 פידבק, 17 נקודות

23:57 10.05.15

23. אם יש לך הנחה על מספר האיברים אז סיימת את השאלה.
בתגובה להודעה מספר 21

כי אז מספר האיברים לא תלוי בקלט.

אם אתה יודע שיש לך במקסימום 5000 איברים אז הכל הופך להיות זמן קבוע.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

23:07 11.05.15

24. פתרון (דומה לתגובה 1)
בתגובה להודעה מספר 0

אם תשתמש במימוש הקלאסי של מערך דינמי, אז ב-Worst Case תצטרך לשלים על העתקת n איברי מערך למערך חדש בגודל 2n - במקרה זה עלות ההכנסה תהיה O(n) בסתירה לתנאי השאלה.
הפתרון הוא לתחזק בכל רגע נתון 2 מערכים, אחד בגודל k ואחד בגודל 2k, כך שעלות הזיכרון ב-WC כאשר המחסנית מכילה k איברים הינה O(k+2k) = O(k) כנדרש.

איך זה עובד?
נניח יש לך ביד מערך בגודל k שהכנסת לתוכו k/2 איברים. ברגע שנוסיף איבר חדש, נייצר מערך בגודל 2k, ובכל פעם שנבצע Push למחסנית בגודל k, ננצל את הפעולה כדי להעתיק שני איברים מהמערך בגודל k למערך בגודל 2k שיצרנו (כלומר פעולת Push מבצעת 3 פעולות). במצב כזה ברגע שהמערך בגודל k התמלא, יש לך העתק מלא שלו בתוך מערך בגודל 2k, שיש לו מקום לעוד k איברים. אתה ממשיך ככה באופן אינדוקטיבי, כלומר ברגע שאתה עובר למערך בגודל 2k, אתה מייצר מערך חדש בגודל 4k וכו'.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

23:18 11.05.15

25. עכשיו הבנתי את מה שהתכוון Dark-Wish במימוש. אלגנטי ונכון (עד כדי כפולה בקבוע :))
בתגובה להודעה מספר 24

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20215 הודעות, 10 פידבק, 17 נקודות

23:36 11.05.15

26. אבל איך אתה מבצע את אותה העתקה?
בתגובה להודעה מספר 24

אתה כתבת "להעתיק שני איברים מהמערך בגודל k למערך בגודל 2k שיצרנו" שזה משפט מאוד קצר קולע ונחמד אבל בכלל לא טרוויאלי ולא ברור איך אתה מבצע את ההעתקה הזאת.
את מי אתה מעתיק ובאיזה דרך אתה מעתיק?
אתה מעתיק את האיבר שעשו לו עכשיו PUSH ואתה מקדם אינדקס על המערך המקורי שקובע איזה איבר אתה מעתיק?
ונניח יש לך את הסיטואציה הבאה:
אתה עכשיו בדיוק מבצע את ההכנסה ה K/2+1 כלומר במערך החדש יש לך רק 2 איברים.

עשית עכשיו 3 POP ברצף. מה בדיוק קורה? לפי הלוגיקה שהצגת אתה אמור להוציא 6 איברים... אבל אין לך 6 איברים במערך של ה 2K... וגם הK הנוכחי שלך הוא לא כמו ה K הקודם, לא ברור איך עובדת ההקצאה אחורנית כשהבעיה שלך נהיית קטנה יותר עם הזמן ולא רק גודלת.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95853 הודעות

23:59 11.05.15

27. היית צודק אם זה היה וקטור, אבל אתה צריך לזכור שמדובר ב-Stack
בתגובה להודעה מספר 26

כלומר אתה יודע בדיוק מה סדר ההכנסה והמחיקה של איברים.
ל-2 המערכים יהיה bottom ו-upper bounds, אז קל לעדכן בכל שלב upper מה-k ל-2k ו-botton מה-2k ל-k, בנוסף לפעולת ה-push/pop עצמה.
זה גם מה שבלבל אותי בהתחלה כשחשבתי על Queue.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20215 הודעות, 10 פידבק, 17 נקודות

01:56 12.05.15

28. זה לא מה שהתכוונתי אליו...
בתגובה להודעה מספר 27

הרי החל מנקודה מסוימת K/2 אתה מקצה מבנה נוסף ואז אתה צריך לתחזק שני מבנים במקביל.. מהשלב הזה פעולת PUSH לפי מה שהוא כתב הופכת להיות אחרת.. היא מתחזקת כמה פעולות - בין היתר את פעולת העתקת האיבר הנוסף "על הדרך".
אני לא הבנתי את המנגנון שמעתיק את האיבר הנוסף.
כתלות במנגנון הזה יעלו גם שאלות על POP.

אני חייב לומר שזה די משעשע כי למעשה הפתרון האלגנטי הזה הוא פריצה של מבנה המחסנית. הרי אתה לא מעתיק את האיברים למחסנית החדשה על סמך פעולות מותרות של מחסנית... תחשוב על זה, הרי עשית PUSH במקרה ה K/2+1 והוא נכנס לראש המחסנית החדשה. עכשיו אתה צריך על הדרך להעתיק איבר נוסף מהמחסנית הישנה. האיבר היחיד שאתה רואה במחסנית הישנה הוא ה TOP שלה.. אז כשתיקח אותו אתה יכול להכניס אותו רק ל TOP של המחסנית החדשה. וגם אם נניח תעשה את הכנסה בסדר הפוך אז פתרת את זה עבור מקרה של 2 איברים, בPUSH הבא זה כבר לא יעבוד...
אז בעצם אתה אומר מחסנית אבל מה שיש לך כאן זה בכלל לא מחסנית.
זה כמו השאלות של "תן לי את האיבר בעומק K במחסנית ב O(1)". יופי בוא נעשה את זה במערך ואז ניגש לאינדקס n-k. גאונות. התשובה האמיתית לכזאת שאלה צריכה להיות : בלתי אפשרי.

אולי אבל לזה הם התכוונו ב"מחסנית עם גישה ישירה" :|
יותר פשוט היה לקרוא לזה מחסנית שאינה מחסנית

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zippo
חבר מתאריך 26.5.02
7921 הודעות, דרג אמינות חבר זה

21:58 12.05.15

29. המנגנון די פשוט.
בתגובה להודעה מספר 28

כמו שאייל אמר, אתה פשוט דואג להעתיק למבנה החדש 2 איברים על כל הוספה מהמבנה הישן.
תחשוב על זה בשלבים.
מקרה יותר פשוט: לעולם לא משחררים מערך קטן, רק מערכים גדולים.
כלומר יהיה לך מערך בגודל 4 בהתחלה (למשל. וממילא אין טעם להתחיל מקטן יותר)
אחרי הכנסת 2 איברים, המערך יהיה חצי מלא.
הכנסת האיבר השלישי תגרום ליצירת מערך חדש בגודל 8.
ויהיו 3 כתיבות. למערך הקטן באינדקס 3, למערך הגדול באינדקס 3,
והעתקה של האיבר הראשון מהמערך הקטן לגדול.
הכנסת האיבר הרביעי תגרום ליצירת מערך חדש בגודל 16,
ויהיו 5 כתיבות:
לאינדקס 4 ב-3 המערכים + העתקה של האיבר באינדקס 1 למערך בגודל 16 + העתקה של האיבר באינקס 2 למערך בגודל 8.
זה המקסימום פעולות שיקרו.
הכנסת 3 האיברים הבאים יהיו 3 כתיבות:
הכנסה למערך בגודל 8 ו-16 באינדקס של ההכנסה (5,6,7 בהתאמה)
והעתקה של האיברים באינדקסים 2,3,4 (בהתאמה) למערך בגודל 16.
הכנסת האיבר השמיני שוב תגרום ליצירת מערך נוסף בגודל 32, ול-5 כתיבות,
וכך הלאה.
לגבי מחיקה, כל פעם מוחקים את ה-TOP מ-2 המערכים הגדולים. ברגע שמגיעים לגודל של רבע מהמערך הגדול ביותר, אז משחררים את הקצאת הזיכרון של המערך הגדול, וממשיכים במחיקות של שני איברים מה-TOP של המערכים הגדולים שנשארו.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

23:24 12.05.15

30. God is in the details.
בתגובה להודעה מספר 28

גלעד תיאר בפרוטרוט אבל אני מניח שסה"כ הבנת כיצד להתמודד עם pop ו-push.
אני מגיב כדי לתת את דעתי לגבי הרמאות לכאורה בפתרון. מבנה הנתונים שאתה משתמש מאחורי הקלעים הוא אכן מערך (ואפילו מספר כאלו) ואתה נהנה כמובן מכל היתרונות של המערך. זו איננה רמאות. מבנה הנתונים האבסטרקטי חושף למשתמש שלוש מתודות עיקריות שהן push, pop, top והתחייבות שלו היא לעבוד בשיטת LIFO; מותר לך לממש אותו בכל צורה שהיא ולגשת אליו מאחורי הקלעים בכל צורה שהיא כל עוד אתה מקיים את המודל האבסטרקטי. זו נקודה חשובה מאד להמשך הלימודים שלכם מכיוון שתראו בעתיד איך אפשר לקחת את מבני הנתונים האבסטרקטים האלו ולשחק המון על space/time tradeoffs, תראו איך הדברים האלה פוגשים את עולם ה-concurrent, חישוב מבוזר ועוד.
כל עוד מבנה הנתונים מקיים את האינווריאנט של מחסנית וחושף את המתודות שלה, הוא מהווה מחסנית לכל דבר ועניין.
בהצלחה!

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
483 הודעות, 11 פידבק, 19 נקודות

00:40 13.05.15

31. תודה רבה לכולם, גאה באשכול הזה
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד