124. SortedDictionary

שבוע בר-השוואה וממוין טוב
Comparisons, Dictionaries

בהמשך לטיפ היומי של אתמול,

ראינו שהכנסה לSortedList היא מאוד לא יעילה, מאחר ובכל הכנסה מתבצעת העתקה של שני המערכים השמורים.

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

השימוש זהה לחלוטין כמו לSortedList שראינו אתמול:

1
2
3
4
5
6
7
8
9
SortedDictionary<string, int> fruitNameToAmount =
    new SortedDictionary<string, int>();
fruitNameToAmount["Banana"] = 4;
fruitNameToAmount["Apple"] = 8;
fruitNameToAmount["Mango"] = 15;
fruitNameToAmount["Grapes"] = 16;
fruitNameToAmount["Orange"] = 23;
fruitNameToAmount["Peache"] = 42;

אבל הכנסות הן יותר מהירות. בעצם מה שקורה זה שמאחורי הקלעים נשמר עץ אדום שחור כך שהכנסות הן די מהירות $ O\left(\log n \right) $.

כמובן, יש אפשרות גם להשתמש בComparer לפיו להשוות איברים

אז למה שבכלל תרצו להשתמש בSortedList?

יש מספר סיבות:

  • SortedDictionary מחזיק מבנה של עץ אדום שחור. זהו מבנה יותר מסובך ולכן יותר כבד מ"סתם" שני מערכים ולכן מצריך יותר זכרון
  • לSortedList יש יתרון אדיר על פני SortedDictionary – הוא מאפשר גישה גם לפי אינדקס: מאחר ואנחנו מחזיקים בסה"כ שני מערכים, אנחנו מסוגלים לגשת לאיבר שנמצא, למשל, במקום 31 בסידור הממוין, ב$ O \left(1 \right)$

המשך יום ממוין (שמשתנה יחסית הרבה)

שתף