שיחה:מילון (מבנה נתונים)

מערך כמימוש של מילון

ביטלתי את העריכה של elaz58. מערך הוא מימוש אפשרי של מילון, שכן הוא מתאים מפתחות (אינדקסים במערך) לערכים (האיברים עצמם במערך). גם בויקיפדיה באנגלית מציינים זאת: Another very simple implementation technique, usable when the keys are restricted to a narrow range of integers, is direct addressing into an array: the value for a given key k is stored at the array cell A[k], or if there is no binding for k then the cell stores a special sentinel value that indicates the absence of a binding. As well as being simple, this technique is fast: each dictionary operation takes constant time. However, the space requirement for this structure is the size of the entire keyspace, making it impractical unless the keyspace is small.[3]

ליאור ג - שיחה 11:23, 16 באוקטובר 2013 (IDT)

אני שוקל לשנות את זה ל:

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

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

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

המילה "מערך" מציינת שני דברים (שיש ביניהם קשר הדוק): מיקום רצוף של איברים שווי-טיפוס בזיכרון, ומבנה נתונים בשפת תכנות. השני הוא מקרה פרטי של מילון, והראשון הוא מימוש יעיל של המקרה הפרטי הזה. --אלעזר - שיחה 12:44, 16 באוקטובר 2013 (IDT)

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

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

ח"ע לעומת חח"ע

הסרתי את הקישור מ"חד-ערכי" לפונקציה חד-חד-ערכית משום שהוא פשוט לא נכון. מילון הוא חד-ערכי (כלומר הוא פונקציה - לכל מפתח יש ערך יחיד), אבל הוא לא בהכרח חד-חד-ערכי. אם מילון היה חד-חד-ערכי, לא ניתן היה להתאים את אותו ערך למספר מפתחות שונים, מה שכמובן אפשרי במילון (זה חוקי להתאים לשני אנשים שונים את אותו מספר הטלפון). ליאור ג - שיחה 16:08, 9 ביולי 2010 (IDT)