שיחה:מערך (מבנה נתונים)

"אין הבדל של ממש בין השיטות: הביטוי מתרגם בפועל לכתובת הזיכרון בה מאוכסן הנתון. עם זאת ב#ממטריצות שימוש כזה עשוי להיות יעיל משמעותית."

למה? עד כמה שידוע לי, אין הבדל בזמני הגישה כאשר משתמשים בסוגריים מרובעים או כאשר מתייחסים למערך כאל מצביע. (ואגב, אם מתקנים את זה, לתקן גם את ה# במטריצות). מה זה "משמעותית" בכלל? שיפור בסדרי גודל? גדי אלכסנדרוביץ' 19:53, 8 מרץ 2005 (UTC)

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

צודק, יש בזה משהו, אבל זה לא כל כך ברור (אם אני לא טועה יש מחשבים שבהם דווקא פעולת כפל יותר מהירה מחיבור). בכל מקרה, למה לא לכתוב את זה בערך עצמו? זה לא מסרבל במיוחד, ואין סיבה להסתיר מידע מאנשים שאחרי זה יתהו למה זה בדיוק טוב. גדי אלכסנדרוביץ' 20:02, 8 מרץ 2005 (UTC)

אין דבר כזה פעולות כפל מהירות מפעולות חיבור. יש מקרים (למשל אם אתה מכפיל ב-2 ב-Hard code) בהם הקומפלייר מצליח להמיר את פעולות הכפל להסטה של ביטים שהן יותר מהירות.

אני לא הוספתי כי לא הצלחתי לנסח את זה בצורה שתהיה מובנת לבני אדם נורמאליים... טרול רפאים 20:10, 8 מרץ 2005 (UTC)

מה הקטע עם המאמר הזה?

יותר מסבך את העניין מאשר מפשט. --נתנאל בר-אור ל. 20:40, 10 בספטמבר 2007 (IDT)

הערך מסורבל, לא מדויק וחסר פרטים

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

אנא תעירו, אני אעבוד על כך בהמשך.--ויני 02:28, 2 ביוני 2008 (IDT)

סיבוכיות הגדלת המערך

"(על פי רוב, הכפלת המערך פי שניים בכל פעם שנדרשים להגדיל אותו) לא תעלה על $\ O(1)$"? זה לא טעות? הגדלת המערך עלולה להיות הרבה יותר מאשר רק הכפלה של שטח הזיכרון המוקצה, ומה עם העתקת נתונים? למיטב ידיעתי במימושים מעשיים של מערכים כגון מחלקות של מחרוזות, אם מרחיבים או מגדילים את המערך זה כרוך לעיתים גם בהעתקה פיזית של הנתונים. או שלא הבנתי את הפסקה הזו, אשמח אם מישהו יאיר את עיני. --יוסי א. - שיחה 14:20, 11 ביוני 2008 (IDT)

שים לב שמדובר שם על עלות משוערכת. הרעיון הוא שפעולת ההגדלה עצמה היא יקרה, אבל זה מתאזן עם העובדה שכדי להביא את המערך למצב שבו יש להגדיל אותו, ביצעת הרבה פעולות שדרשו זמן קבוע כל אחת, ולכן הממוצע על סך הזמן של כל הפעולות גם יחד (הוספת האיברים+הגדלת המערך) הוא של זמן קבוע לפעולה. גדי אלכסנדרוביץ' - שיחה 15:02, 11 ביוני 2008 (IDT)

תן לי להבין משהו, מה הפירוש "ביצעת הרבה פעולות שדרשו זמן קבוע כל אחת", הפעולות הללו עצמם לא באים בחשבון כשמשערכים סיבוכיות? נניח כי יש לנו מערך של 1000 איברים וביצעתי אלף פעולות, לאחר מכן הגדלתי אותו ל-1001 איברים ונאלצתי להעתיק את כל ה-1001 איברים למקום אחר בזיכרון איפה אתה מאזן את זה? הבנתי שסיבוכיות $\ O(1)$ אומרת פעולה של זמן קבוע כלשהו. האם פעולת העתקה של n איברים נחשבת בהקשר זה כפעולה שזמנה קבוע? הרי הסיבוכיות כאן נמדדת לפי n לא? --יוסי א. - שיחה 11:03, 12 ביוני 2008 (IDT)

יש לי מערך ריק שיכול להכיל n איברים. הכנסתי לתוכו עוד ועוד דברים - סה"כ ביצעתי n פעולות בעלות של $\ O(1)$. אחר כך ניסיתי להכניס עוד איבר, ואז "ניפחתי" את המערך פי 2, והעתקתי את כל האיברים הקיימים - עלות של $\ O(n)$. מה העלות המשוערכת של כל הפעולות הללו? הרעיון בשיערוך הוא לסכום את העלות של כל הפעולות עד לפעולה האחרונה שביצענו, ולחלק במספר הפעולות. לכן, כל עוד לא ביצעתי את פעולת ההכנסה יש לי $\ {\frac {1}{k}}\sum _{i=1}^{k}O(1)={\frac {O(k)}{k}}=O(1)$ פעולות; אחריה, יש לי $\ {\frac {1}{n}}(\sum _{i=1}^{n}O(1)+O(n))={\frac {1}{n}}(O(n)+O(n))={\frac {O(n)}{n}}=O(1)$ פעולות. החשבון קצת מקושקש, אבל הכוונה ברורה. גדי אלכסנדרוביץ' - שיחה 16:31, 12 ביוני 2008 (IDT)

גדי אלכסנדרוביץ' ויוסי א. בטח יש לכם עכשיו כבר נינים אבל בכל אופן כיוון שחידשתי משהו בערך אז אני כותב: לפי ההיגיון הנ"ל, זה יהיה אותו דבר גם במחיקה ממערך - $\ O(1)$. נראה לי שזאת גם כוונת הדברים בטבלה הצבעונית בערך האנגלי Dynamic array בטור Dynamic array ובשורה Insert/delete at end. אגב החישוב שעשית (גדי) לא מדויק כיוון שעבור n מסוים אתה צריך לחשב את ההקצאות שנעשו עד אותו n. לצורך הדוגמה אם אתה מכפיל את גודל המערך החל מ1, עבור n=1024 הכפלת את המערך כשהכנסת את האיבר ה1,2,4,8,16,32 וכו' אבל זה עדיין לא משנה את הניתוח לשיעורין בסוף. Badidipedia - שיחה 18:46, 17 ביוני 2015 (IDT)

שימו לב מה קורה באנגלית

יש באנגלית שני ערכים שונים, Array data type ו Array data structure, ובכותרת הערך הבהרה שאין להתבלבל ביניהם. כמובן ששני הערכים האלה מפנים אל הערך הזה... יש מבנה נתונים מופשט, מערך, שהוא בעצם מילון אבל עם כמה אילוצים נוספים. לעומתו, יש טיפוס נתונים מערך בשפות התכנות השונות, כולל שפת המחשב ושפת אסמבלי. אלה שני דברים שונים - השני הוא מימוש של הראשון. צריך להפריד את הערך הזה לשני ערכים שונים, כמו באנגלית. אלעזר - שיחה 22:49, 26 באוקטובר 2010 (IST)