מערך דינמי מהיר ב-C++

[לשם שינוי בשם בדוי]

מערך דינמי מהיר ב-C++

יש דרך להקצות מערך דינמי ששינוי הגודל שלו לא דורש פעולה ארוכה ? (כלומר ששינוי גודל לא ידרוש למשל העתקת כל המערך למיקום חדש).

 

[לשם שינוי בשם בדוי]

הבהרה

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

?! )

 

[ה עוד אחד]

לא.

 

[ה עוד אחד]

כן.

 

[Metheny]

אתה יכול לבנות לעצמך

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

 

[vinney]

בדקת את vector?

אני חושב שהיישום שלו מאוד יעיל מהבחינה הזאת

 

[the new L]

וקטור אבל כן

מעתיק את כל המערך כשנגמר המקום (ואפילו מקצה פי שתיים מקום ממה שהיה קודם)

 

[annefan]

מה שאומר

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

 

[vinney]

כן,

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

 

[DadleFish]

הקצאה פי שתיים

נותנת את יחס האלפא-תחרותיות הטוב ביותר שאפשר לעשות באלגוריתם און-ליין כזה (היחס הוא 4Opt, למי שזה מעניין אותו).

 

[HaRmosh]

בקשר ליחס אלפא-תחרותיות,

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

 

[DadleFish]

הממממ

זה alpha-competitiveness, כשה-alpha הוא האות עצמה (כמובן שאם תגגל כנראה שזה יהיה alpha בכל זאת). בכל מקרה מדובר בחלק מנושא רחב שנקרא אלגוריתמי אונליין (online algorithms). הנה לינק לקורס בברקלי בנושא.

 

[DadleFish]

וספציפית לגבי מערך,

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

 

[DadleFish]

יש דרך לשפר את הביצועים,

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

 

[dharmax]

אוספים

מערך הוא אחד מני סוגים רבים של אוספים. לסוג הבסיסי של המערך, ישנם היתרונות הבאים: צריכת זכרון נמוכה (יש לך רק את הזכרון שתופסים האלמנטים), וזמן גישה-על-פי-אינדקס אפסי. הוא גם מאוד פשוט לישום ושימוש. ישנם סוגים רבים אחרים של אוספים, שיש להם יתרונות אחרים. למערך (הכי) בסיסי, אגב, מוקצה זכרון על פי מספר אלמנטים ידוע מראש, וכל תוספת, מחייבת עדכון של גודל ההקצאה. מערך טיפה יותר משוכלל, יכלול אלגוריתם של גדילה על פי דלתה, כמו שהוזכר כאן על ידי אחרים. אתה רוצה משהו, שתהיה לו תכונה שאין למערך בסיסי: יעילות גדולה בהגדלה של מספר האלמנטים. יש שיטות לעשות את זה, כמו למשל sparsed arrays, אבל השאלה היא, מה כל הדרישות מאותו אוסף? צריך להסגר על הדרישות, ואז לבחור משלל האפשרויות שישנן, שכוללות גם דברים פשוטים, כמו רשימה מקושרת, או דו-מקושרת, hash tables, btree, binary-tree, red-black tree...

 

[לשם שינוי בשם בדוי]

תודה

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

 

[codec]

הוצאת לי את המערך מהפה...../images/Emo67.gif

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

 

[לשם שינוי בשם בדוי]

נסיון למימוש

#include "stddef.h" class ArrHeader { public: int *pArr; int max_items; int counter; ArrHeader *next; ArrHeader *prev; //optional ArrHeader(int arr_size); ~ArrHeader(); }; const START_SIZE = 1000; ArrHeader *curr_arr; ArrHeader *head_all; void main(){ curr_arr = new ArrHeader(START_SIZE); head_all = curr_arr; } ArrHeader::ArrHeader(int arr_size) { pArr = new int[arr_size]; max_items = arr_size; counter = 0; prev = NULL; next = NULL; } ArrHeader::~ArrHeader() { delete pArr; } void add_item(int item) { if (curr_arr->counter++ == curr_arr->max_items) { ArrHeader* new_arr = new ArrHeader(curr_arr->max_items * 2); //todo: add exception handling if max_items get overflow curr_arr->next = new_arr; new_arr->prev = curr_arr; curr_arr = new_arr; } *(curr_arr + curr_arr->counter) = item; } int read_item(int item_number) { ArrHeader* arry = head_all; int total = arry->counter; while (total<item_number) { arry = arry->next; //todo: add exception if arry->next = NULL total += arry->counter; } return *(arry->pArr + item_number - (total - arry->counter)); }​

 

[selalerer]

../images/Emo6.gif איזה מצחיקים אתם, זה vector ../images/Emo13.gif

 

[vinney]

כבר היה פה דיון על שיפור הSTLים ../images/Emo13.gif

תן להם שינסו