רובנו נתקלנו בשני המושגים struct וclass מתוך העולם ה.netי

אך האם אי פעם הצלחתם לעמוד על ההבדלים בין class וstruct?

ובכן, ננסה להסביר את ההבדלים ביניהם.

מבחינה קונספטואלית, צריך לחשוב על struct בתור מבנה סטטי (immutable) המייצג מידע פשוט. (למשל, מספרים)

על class לעומת זאת צריך לחשוב בצורה object oriented – כלומר, בתור מבנה המייצג יישות לוגית, שבין השאר אפשר לרשת ממנה, ולשנות פונקציונאליות בעזרת חוקי הפולימורפיזם וכו’. (לדוגמה, מחלקה המייצגת צורה, שממנה יורשים משולש, מרובע ועיגול)

במה מתבטא הדבר מבחינה טכנית?

• לstruct תמיד יהיה Constructor דיפולטי. לא נוכל לבטל את הConstructor הדיפולטי או לשנות את ההתנהגות שלו, לעומת class שנוכל גם לבטל את הConstructor הדיפולטי שלו, וגם לשנות את ההתנהגות שלו
• הConstructor הדיפולטי של struct מאתחל את כל השדות שלו בערכים הדיפולטיים שלהם (ראו גם טיפ מספר 32)
• אם לא נאתחל משתנה מסוג struct, תתבצע אוטומטית קריאה לConstructor הדיפולטי שלו, לעומת classש אם לא נאתחל משתנה מהסוג שלו, נקבל את הערך null
• באופן כללי structים לא יכולים לקבל את הערך null (חוץ מהמקרה המיוחד שלNullable, ראו גם טיפ מספר 35)
• בConstructor לא דיפולטי של struct, אנחנו מחויבים לאתחל את כל השדות שלו (אחרת הוא לא יתקמפל), בניגוד לclass בו אם לא נאתחל שדה בConstructor, הוא יאותחל בערך הדיפולטי שלו.
• classים יכולים לרשת classים אחרים. לעומת זאת, לא ניתן לרשת מstruct.
• עם זאת, גם classים וגם structים יכולים לממש ממשקים.
• לclass בד”כ מוקצה זכרון על הHeap, ואילו לstruct בד”כ על הStack.
• לכן structים ינוקו בד”כ החל מהמקום בו הם יצאו מהScope (למשל, החל מהמקום בו המשתנה הלוקאלי כבר לא מוגדר), לעומת classים שינוקו ברגע שהGarbage Collector יחליט שהגיע זמנם לעזוב.
• מסיבה זו, לא יכולה להיות לstruct פונקצית Finalizer.
• בנוסף, מאחר וstruct מוקצה בד”כ על הStack, מתקיים כי השמה של object לערכו גוררת Boxing. כנ”ל לגבי השמה של ממשק לערך של struct.
• השמה של struct לתוך struct אחר, מכניסה אליו העתק של הstruct המקורי. כלומר, כתיבת השורה

1

MyStruct first = second;

תכניס לתוך first שכפול של second, אבל בפועל, שניהם לא יצביעו לאותו מקום בזכרון (כלומר, אם נשנה את first, זה לא ישנה את second)

• כנ"ל לגבי קריאה לפונקציה: אם נעביר לפונקציה struct בתור פרמטר, הפונקציה למעשה תקבל העתק של הstruct (כלומר, אם נשנה את הפרמטר, זה לא ישנה את הstruct המקורי)

שימו לב להבדלים: הדברים החשובים לדעתי הם שערך של struct משוכפל בהשמה ובקריאה לפונקציה, הוא לא יכול לקבל את הערך null ולא ניתן לרשת ממנו.

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

איזה דוגמאות אפשר לציין? ערכים נומריים (קואורדינאטות של נקודות, אובייקטים המייצגים זוויות), זוגות של איברים (KeyValuePair למשל) ועוד.

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

(יש שיגידו שכלל אצבע הוא עד 16 בתים לstruct)

מקווה שהצלחתי לפתח אינטואיציה על ההבדלים בין struct לclass.

שבוע מובנה טוב

הכרנו בעבר את הפונקציה Select היוצרת אוסף חדש של אובייקטים ע”י “הטלה” כלשהי על האובייקטים הקיימים:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

IEnumerable<Person> people =
    new []
        {
            new Person("John", "Lennon"),
            new Person("Ringo", "Starr"),
            new Person("Paul", "McCartney"),
            new Person("George", "Harrison")
        };
IEnumerable<string> firstNames =
    people.Select(x => x.FirstName);
// John, Ringo, Paul, George
IEnumerable<string> lastNames =
    people.Select(x => x.LastName);
// Lennon, Starr, McCartney, Harrison

לפעמים יש לנו את המצב ההפוך: נתונות לנו ההטלות (במקרה שלנו השמות הפרטיים והמשפחה), ואנחנו מעוניינים לבנות אובייקט על פיהן.

כלומר יש לנו רק את firstNames ואת lastNames ולפי זה אנחנו מעוניינים ליצור את people.

(תחשבו שמצב כזה יכול לקרות כאשר אנחנו קוראים את firstNames ואת lastNames ממקור חיצוני, למשל מקובץ או שליפה מDB)

לפי Framework 4.0 היינו צריכים לעשות משהו כזה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

List<Person> people  = new List<Person>();
using (IEnumerator<string> firstNamesIterator =
    firstNames.GetEnumerator())
{
    using (IEnumerator<string> lastNamesIterator =
        lastNames.GetEnumerator())
    {
        while (firstNamesIterator.MoveNext() &&
               lastNamesIterator.MoveNext())
        {
            people.Add
                (new Person(firstNamesIterator.Current,
                            lastNamesIterator.Current));
        }
    }                
}

עובד, אבל לא אלגנטי! (מישהו באמת משתמש בGetEnumerator????)

החל מFramework 4.0 נוכל לעשות זאת באופן יותר פשוט באמצעות הExtension Method שנוסף לSystem.Linq שנקרא Zip:

1
2
3

IEnumerable<Person> people  =
    firstNames.Zip(lastNames,
                   (first, last) => new Person(first, last));

הExtension Method מקבל עוד IEnumerable ומאפשר לנו ליצור מכל זוג של איברים (לפי המיקום שלהם), איבר שלישי באמצעות delegate שאנחנו מציינים.

כלומר הוא רץ סימולטנית על שני האוספים שלנו, ומביא לנו בכל איטרציה את האיבר הנוכחי של כל אוסף, ובאמצעות הDelegate מאפשר לנו ליצור איבר חדש. מהאיברים החדשים שנוצרו, מורכב הEnumerable החדש.

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

סופ"ש טוב (בלי הרבה זיפזופים)

מדי פעם אנחנו יוצרים Properties שהם Lazy – כלומר, הם לא מאותחלים עד הגישה הראשונה שלהם.

קיימות שתי דרכים נפוצות לעשות זאת:

עבור Reference types: השוואה לnull:

1
2
3
4
5
6
7
8
9
10
11
12
13

public MyClass HeavyProperty
{
    get
    {
        if (m_HeavyProperty == null)
        {
            // Init m_HeavyProperty
            m_HeavyProperty = InitHeavyProperty();
        }
        return m_HeavyProperty;
    }
}

דרך שנייה להשגת מטרה זו היא באמצעות בוליאני המעיד האם הProperty כבר אותחל:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public MyClass HeavyProperty
{
    get
    {
        if (!m_HeavyPropertyInitialized)
        {
            // Init m_HeavyProperty
            m_HeavyProperty = InitHeavyProperty();
            m_HeavyPropertyInitialized = true;
        }
        return m_HeavyProperty;
    }
}

כך אנחנו מאתחלים את הProperty רק בגישה הראשונה אליו.

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

בFramework 4.0 הוסיפו לנו טיפוס שמסייע לנו בפתרון בעיה זו, והוא Lazy<T>. איך זה עובד?

זהו טיפוס שמקבל delegate, שבאמצעותו אנחנו נאתחל אובייקט. בגישה הראשונה לProperty ששמו Value יתבצע הdelegate והאובייקט המאותחל ישמר. בשאר הגישות, נפנה לאובייקט שכבר אותחל.

כך נוכל להחליף את המימוש של הProperty בדרך הבאה: ניצור member בשם m_HeavyProperty מסוג Lazy<MyClass>. בConstructor נאתחל אותו:

1

m_HeavyProperty = new Lazy<MyClass>( () => InitHeavyProperty() );

בגישה לProperty פשוט ניגש לValue שלו:

1
2
3
4
5
6
7

public MyClass HeavyProperty
{
    get
    {
        return m_HeavyProperty.Value;
    }
}

וזהו!

שימו לב שהConstructor של Lazy<T> מקבל delegate, כך שנוכל להכניס lambda expression נחמד לפעמים לאתחול הProperty ולא סתם קריאה לפונקציה.

(הערה: יתרון נוסף של שימוש בLazy הוא התמיכה של המחלקה בנעילות המונעות אתחול של Member במספר Threadים במקביל. ראו גם טיפ מספר 283)

המשך יום טוב ועצלן

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

טיפוס נוסף שהתווסף בFramework 4.0 לSystem.Numerics הוא הטיפוס Complex. זהו struct המייצג מספר מרוכב. הדבר נועד לחסוך מאיתנו מימוש עבודה עם מספרים מרוכבים בעצמנו.

קיימים implicit casts מהטיפוסים הנומריים הפרימיטיביים לComplex:

1

Complex myNumber = 3;

אם אנחנו בכל זאת רוצים לאתחל מספר מרוכב שאינו ממשי, נוכל להשתמש בConstructor המתאים:

1
2

Complex myNumber = new Complex(1, 1);
Console.WriteLine(myNumber); // Prints (1, 1)

שימו לב שדרסו את ToString כך שהוא ידפיס את הקואורדינאטות של המספר.

באופן צפוי, כל האופרטורים הסטנדרטיים ממומשים:

1
2
3

Complex firstNumber = new Complex(1, 2);
Complex secondNumber = firstNumber * firstNumber;
Console.WriteLine(secondNumber); // Prints (-3, 4)

שהרי $ (1 + 2i) \cdot (1 + 2i) = 1^2 + 2 \cdot 2 \cdot i + 2^2 \cdot i^2 = 1 + 4 \cdot i - 4 = -3 + 4 \cdot i $
עוד דוגמה:

1
2
3
4

Complex firstNumber = 2;
Complex secondNumber = new Complex(1, 1);
Complex quotient = firstNumber / secondNumber;
Console.WriteLine(quotient); // (1, -1)

שהרי $ \displaystyle{\frac{2}{1 + i} = 1 - i} $

נוכל גם לאתחל מספר מרוכב באמצעות הרכבת אופרטורים:

1
2

Complex number = 1 + 2 * Complex.ImaginaryOne;
Console.WriteLine(number); // (1, 2)

שימו לב שComplex.ImaginaryOne מייצג את המספר המרוכב $ i $ (היחידה המדומה).

בנוסף, נוכל לעבור הצגה פולרית בקלות:

1
2
3

Complex number = new Complex(1, 1);
Console.WriteLine("Radius: {0}, Angle: {1}", number.Magnitude, number.Phase);
// Radius: 1.4142135623731, Angle: 0.785398163397448

גם כל הפונקציות האלמנטאריות (פונקציות טריגונומטריות ואקספוננט של מספרים מרוכבים) ממומשות לנו בתור פונקציות סטטיות של המחלקה:

למשל, חישוב צמוד של מרוכב:

1
2

Complex number = new Complex(3, 4);
Console.WriteLine(Complex.Conjugate(number)); // (3, -4)

נוכל גם לבדוק את זהות אוילר:

1
2
3
4

Complex number =
    Complex.Exp(Complex.ImaginaryOne * Math.PI) + 1;
Console.WriteLine(number); // Almost 0 :)

דברים שימושיים (או סתם מגניבים) שאפשר לעשות עם זה:

• חישוב פונקציות טריגונומטריות בעזרת שיטת CORDIC - ראו טיפ מספר 343.
• חישוב שורשים מרוכבים של פונקציות באמצעות שיטת ניוטון רפסון - ראו גם טיפ מספר 341.
• ציור פרקטלים, למשל קבוצת מנדלברוט ו פרקטלי ניוטון

המשך יום מרוכב

מדי פעם אנחנו נתקלים בחישובים עם מספרים גדולים. למרבה הצער, הטיפוסים הפרימיטיביים של C# מוגבלים בטווח שלהם.

למשל, אם ננסה לחשב עצרת של 100:

1
2
3
4
5
6
7
8
9
10
11

public static long Factorial(long n)
{
    long result = 1;
      
    for (long i = 1; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

עד כמה שlong הוא גדול, נקבל את התוצאה הבאה בחישוב עצרת של 100: 0.

הסיבה היא שlong מוגבל עד $ 2^{63}$, אבל 100 עצרת יותר גדול מ$ 2^{524} $.

כדי לפתור בעיה זו בכל זאת, הומצא לנו בC# 4.0 טיפוס חדש ששמו BigInteger (יושב בSystem.Numerics בSystem.Numerics.dll). הטיפוס מאפשר לנו להגדיר מספר שלם גדול כרצוננו בזכרון. (הדבר עובד מאחורי הקלעים עם מערך של uint המייצג את המספר).

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

1
2
3
4
5
6
7
8
9
10
11

public static BigInteger Factorial(int n)
{
    BigInteger result = 1;
    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

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

כמה דברים נחמדים: למי שתהה:

עצרת של מאה זה בסה"כ

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

שימו לב שיש הרבה פונקציות סטטיות של BigInteger המאפשרים לנו לחשב חזקה וכו’.

ואיך אפשר לכתוב טיפ יומי על BigInteger ביום שכזה בלי לציין את הדוגמה הבאה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public static BigInteger FirstDigits(int numOfDigits)
{
    int loopIterations = (int)(numOfDigits * Math.Log(10, 4)) + 2;
    BigInteger result = 0;
    int odd = 1;
    int minus = 1;
    BigInteger two = 2;
    BigInteger three = 3;
    BigInteger current = 4 * BigInteger.Pow(10, numOfDigits);
    for (int i = 1; i <= loopIterations; i++)
    {
        result += minus * current / (two * odd) + 
                  minus * current / (three * odd);
        minus *= -1;
        odd += 2;
        two *= 2 * 2;
        three *= 3 * 3;
    }
    return result;
}

תוכלו לנחש מה זה עושה? רמז: אם נעביר 100 לפונקציה נקבל את התוצאה הבאה:

31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170683

(אם יש למישהו כוח לבדוק למה יש טעות ב3 ספרות האחרונות (אמור להיות 798 במקום 683), אני אשמח שישתף אותי)

המשך יום פאי שמח

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

לפעמים אנחנו בכלל רוצים לעבוד עם שלשות/רביעיות וכלה בnיות (הכינוי המתמטי לאוסף סדור של n איברים, באנגלית נקרא Tuple)

עד לFramework 4.0 היינו יכולים לעשות מניפולציה כזאת:

1
2
3
4
5
6
7
8
9

public static KeyValuePair<int, int> FindMaxAndMin(IEnumerable<int> numbers)
{
    int max;
    int min;
    // TODO: Find the max and min of the set
    return new KeyValuePair<int, int>(min, max);
}

(תעזבו האם נכון שתהיה פונקציה כזאת או לא)

כלומר לעשות שימוש מעוות בKeyValuePair כדי לשמור שני ערכים – אלא שאין לנו באמת מפתח וערך כאן.

(למי שלא מכיר את KeyValuePair, ראו גם טיפ 17)

דוגמא נוספת היא כזאת: נניח שאנחנו מעוניינים למצוא את כל השלשות של מספרים שלמים (a,b,c) בתחום מסוים כך שמתקיים השוויון

$ a^2+ b^2 = c^2 $

(לשלשות כאלה קוראים שלשות פיתגוריות)

כאן יהיה לנו יותר קשה להשתמש בKeyValuePair, כיוון שאנחנו מעוניינים לשמור שלשות.

בFramework 4.0 קיים פתרון יותר אלגנטי – קיימת מחלקה בשם Tuple המייצגת n-יה. למען הדיוק, קיימות מספר מחלקות גנריות כאלה, מאיבר יחיד עד שמינייה:

1
2
3
4
5
6
7
8

public class Tuple<T1>
public class Tuple<T1, T2>
public class Tuple<T1, T2, T3>
public class Tuple<T1, T2, T3, T4>
public class Tuple<T1, T2, T3, T4, T5>
public class Tuple<T1, T2, T3, T4, T5, T6>
public class Tuple<T1, T2, T3, T4, T5, T6, T7>
public class Tuple<T1, T2, T3, T4, T5, T6, T7, TRest>

קיימות שתי דרכים להשתמש בזה:

הראשונה היא באופן דומה למה שראינו KeyValuePair:

1
2
3
4
5
6
7
8
9

public static Tuple<int, int> FindMaxAndMin(IEnumerable<int> numbers)
{
    int max;
    int min;
    // TODO: Find the max and min of the set
    return new Tuple<int, int>(min, max);
}

וגישה תתבצע כך:

1
2
3

Tuple<int, int> minAndMax = FindMaxAndMin(numbers);
Console.WriteLine("Min is {0}", minAndMax.Item1);
Console.WriteLine("Max is {0}", minAndMax.Item2);

קיימת דרך אחרת לאתחל, והיא באמצעות הoverloadים של הפונקציה הסטטית Tuple.Create:

1
2
3
4
5
6
7
8

public static Tuple<int, int> FindMaxAndMin(IEnumerable<int> numbers)
{
    int max;
    int min;
    // TODO: Find the max and min of the set
    return Tuple.Create<int, int>(min, max);
}

למי שזוכר את טיפ מספר 28, אפשר לתת לקומפיילר לזהות לבד את הטיפוסים הגנריים:

1
2
3
4
5
6
7
8

public static Tuple<int, int> FindMaxAndMin(IEnumerable<int> numbers)
{
    int max;
    int min;
    // TODO: Find the max and min of the set
    return Tuple.Create(min, max);
}

כך שיש פה יתרון בכתיבה 😃.

בדוגמה של שלשות פיתגוריות:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static IEnumerable<Tuple<int, int, int>> PythagoreanTriplets(int range)
{
    for (int a = 0; a < range; a++)
    {
        for (int b = 0; b < range; b++)
        {
            for (int c = 0; c < range; c++)
            {
                if (a * a + b * b == c * c)
                {
                    yield return Tuple.Create(a, b, c);
                }
            }
        }
    }
}

ואם אנחנו רוצים יותר מ8 איברים? חשבו על זה ומציעים לנו את הפתרון הבא:

1
2
3
4
5
6
7

var tenNumbers =
    new Tuple<int, int, int, int, int, int, int, Tuple<int, int,int>>
        (1, 2, 3, 4, 5, 6, 7, Tuple.Create(8, 9, 10));
Console.WriteLine(tenNumbers.Item6); // 6
Console.WriteLine(tenNumbers.Rest.Item2); // 9

האמת שלא הכי אלגנטי, אבל עשוי להתאים.

שבוע טיזרים טוב

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

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

דרך אחת אפשרית לעשות זאת היא להשתמש בSortedDictionary (או בSortedList) בצורה מעוותת – כלומר להשתמש רק בKey שלהם, ולשים בValue, למשל bool.

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

בדומה לטיפ מספר 19, בו פגשנו HashSet שתפקידו היה לשמור כל איבר בדיוק פעם אחת, הוסיפו בFramework 4.0 טיפוס חדש ששמו SortedSet המאפשר לנו לשמור כל איבר בדיוק פעם אחת, ושהאיברים יהיו ממויינים.

בפועל, המבנה ממומש באמצעות עץ אדום-שחור, כמו SortedDictionary, אלא שהפעם אנחנו שומרים רק את הKeys.

קיים גם פה overload לConstructor המאפשר לנו להגדיר את הIComparer איתו אנחנו רוצים שהSortedSet ימיין איברים.

HashSet וSortedSet מממשים ממשק משותף ששמו ISet.

בנוסף, קיימים שני Properties מיוחדים שיש רק לSortedSet והם:

1
2

public T Min { get; }
public T Max { get; }

המאפשרים לנו למצוא את המינימום ומקסימום בצורה פשוטה.

קיימות גם עוד שתי פונקציות ייחודיות לSortedSet<T> והן:

1
2

public virtual SortedSet<T> GetViewBetween(T lowerValue, T upperValue)
public IEnumerable<T> Reverse()

הראשונה מאפשרת לנו למצוא את כל האיברים בתחום מסוים.

השנייה מאפשרת לנו להפוך את הסדר של האיברים בSortedSet<T> בצורה פשוטה.

סופ"ש ממוין! (ולא חסר ערך)

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

ראינו שהכנסה ל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)$

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

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

לדוגמה, מיון נתונים לפי תאריך, או מיון של שמות אלפא-ביתית, או מיון עובדים לפי השכר שלהם.

אחת האפשרויות היא להשתמש במבנה נתונים שנקרא

SortedList המאפשר לנו לדאוג שהאיברים יהיו בסדר הנכון כבר בהכנסתם.

מבנה זה מזכיר Dictionary (ולכן גם מממש IDictionary):

1
2
3
4
5
6
7
8
9

SortedList<string, int> fruitNameToAmount =
    new SortedList<string, int>();
fruitNameToAmount["Banana"] = 4;
fruitNameToAmount["Apple"] = 8;
fruitNameToAmount["Mango"] = 15;
fruitNameToAmount["Grapes"] = 16;
fruitNameToAmount["Orange"] = 23;
fruitNameToAmount["Peache"] = 42;

המיון מתבצע לפי הKey. כעת כשנרוץ על הSortedList נקבל:

1
2
3
4
5
6

foreach (KeyValuePair<string, int> fruitToAmount infruitNameToAmount)
{
    Console.WriteLine("{0} - {1}",
                      fruitToAmount.Key,
                      fruitToAmount.Value);
}

Apple - 8
Banana - 4
Grapes - 16
Mango - 15
Orange - 23
Peache - 42

כמובן, איך אפשר בלי, קיים גם Overload לConstructor שמקבל Comparer לפיו נשווה את המפתחות:

1
2

SortedList<string, int> fileToSize =
    new SortedList<string, int>(new FolderLocationComparer());

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

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

המשך יום ממוין (אבל שלא משתנה יותר מדי)

בפעמים הקודמות פגשנו בExtension Methods ששמן OrderBy, ThenBy:

1
2
3
4
5

IEnumerable<string> fruits =
    new[] {"Banana", "Orange", "Strawberry", "Apple", "Mango", "Grapes", "Lemon"};
IOrderedEnumerable<string> orderedFruits = 
    fruits.OrderBy(fruit => fruit.Length).ThenBy(fruit => fruit);

קיימת גם אפשרות לכתוב כתיבה זו בצורה LINQית באמצעות הkeyword ששמו orderby:

1
2
3
4

IOrderedEnumerable<string> orderedFruits =
    from fruit in fruits
    orderby fruit.Length, fruit
    select fruit;

שימו לב שאנחנו מפרידים בין הדברים שאנחנו מעוניינים לבצע את המיון לפיהם בפסיקים.

קיימת אפשרות גם להצהיר האם המיון הוא עולה או יורד באמצעות הKeywordים descending וascending:

1
2
3
4

IOrderedEnumerable<string> orderedFruits =
    from fruit in fruits
    orderby fruit.Length descending, fruit ascending
    select fruit;

זה מתרגם באופן מאוד צפוי לקוד הבא:

1
2

IOrderedEnumerable<string> orderedFruits =
    fruits.OrderByDescending(fruit => fruit.Length).ThenBy(fruit => fruit);

המשך יום ממוין