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

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

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

כשנגמר המקום למערך חדש. המימוש הזה שומר על המערך הישן וממשיך למערך חדש.

 

[selalerer]

אבל אז הזיכרון לא רציף וזה כבר לא

מערך. זאת רשימה מקושרת של מערכים ואתה מאבד את הייתרונות של מערך.

 

[selalerer]

וד"א גם את זה תוכל לממש בקלות בּSTL

עם list ו vector בשילוב.

 

[vinney]

אתה לא תוכל לגשת בO של 1 ככה

אז כבר תקח עץ מאוזן וזהו, מה אתה שובר את הראש?

 

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

אולי תקראו את האילוצים ?

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

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

 

[vinney]

הדרישות לא אומרות מערך

הדרישות אומרות רשימה מקושרת. זה בגדול גם מה שעשית, רק שסיבכת אותה. אם אתה רוצה לייעל - תעשה רשימה עם מצביע לאמצע, לא רק התחלה וסוף, תכל'ס - אין הבדל גדול. למה מלכתחילה אתה מתעקש על מערך?

 

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

סליחה

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

 

[vinney]

תשובה

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

 

[מאה קולפה]

וקטור וקטור וקטור

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