בהמשך לטיפים הקודמים –

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

לצורך פתרון זה, ניתן להשתמש בOverload של OrderBy שמקבל IComparer לפיו נבצע את ההשוואה.

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

נוכל לעשות זאת בצורה הבאה:

נממש IComparer:

1
2
3
4
5
6
7

public class FolderLocationComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        // Use Path class to implement this.
    }
}

כעת נבצע מיון באמצעותו:

1
2

IEnumerable<string> orderedByHierarchy =
    folders.OrderBy(x => x, new FolderLocationComparer());

זהו, זה עשוי להתאים במקרים מסוימים.

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

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

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

למשל:

1
2
3
4

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

או:

1
2
3
4
5

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

הן מאפשרות לבצע את המיון בכיוון ההפוך.

סופ"ש ממוין ומצוין

לפעמים אנחנו מעוניינים למיין אוסף של איברים באיזושהי צורה.

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

למרבה המזל, קיים Extension Method של Linq בשם OrderBy המאפשר לנו למיין אוסף.

לדוגמה:

1
2

IOrderedEnumerable<Person> orderedByAge =
    people.OrderBy(person => person.Age);

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

דוגמה נוספת: נניח שיש לנו רשימה של שמות של פירות. אנחנו יכולים למיין אותם אלפא-ביתית (לפי סדר הופעתם במילון):

1
2
3
4
5

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

אבל אנחנו יכולים גם למיין אותם לפי אורך השמות:

1
2

IOrderedEnumerable<string> orderedByLength = fruits.OrderBy(fruit => fruit.Length);
// "Apple","Mango","Lemon","Banana", "Orange","Grapes","Strawberry"

אתם יכולים לתהות מה זה IOrderedEnumerable? ובכן, זהו ממשק שמאפשר לנו לבצע מיון משני.

מה זאת אומרת? למה זה טוב?

נסביר קודם איך עובד OrderBy:

מה שקורה זה שברגע שאנחנו קוראים לGetEnumerator (למשל בforeach), מתבצעת ריצה על כל האיברים של הIEnumerable, ומתבצע quick sort שלהם.

זה קצת בעייתי, אבל כדי למיין אוסף, צריך לדעת את כל האיברים שלו…

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

1
2

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

מתבצעים שני מיונים. כלומר שני Quick Sortים. זהו תהליך יקר יחסית.

במקום זאת, הExtension Method ששמו ThenBy מאפשר לנו להתלבש על מיון שעדיין לא התבצע, ולומר לו שבמיון שהוא הולך לבצע, שימיין משנית לפי איזשהו שדה אחר:

1
2

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

כאן מה שקורה זה שמתבצע Quick Sort יחיד כדי לבצע את המיון + המיון השני…

שימו לב שכל זה אפשרי בגלל שOrderBy זה lazy – עד שלא נקרא לGetEnumerator, המיון לא יתבצע ולכן נוכל להוסיף עוד קריטריונים למיון…

(ראו גם טיפים מספר 51 – 55)

הערה: לוגית, גם לא נכון למיין פעמיים, במידה ואלגוריתם המיון אינו יציב.

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

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

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

באופן אנלוגי לIEqualityComparer (טיפ מספר 111) המאפשר לנו להשוות איברים בצורה מלאכותית, ולאו דווקא באמצעות פונקצית הEquals של האובייקט, קיים פתרון מקביל גם עבור IComparable.

הפתרון הוא ממשק ששמו IComparer המאפשר לנו להגדיר כיצד להשוות איברים מבחוץ. יש לו פונקציה אחת:

1

public int Compare(T x, T y)

אותה אנחנו צריכים לממש, ולהחליט כיצד להשוות איברים.

קיימת גם גרסה לא גנרית של ממשק זה המשווה objectים. במידה ואנחנו מעוניינים לממש את שני הממשקים, נוכל לרשת מהטיפוס Comparer<T>. כך נצטרך רק לממש את הפונקציה הגנרית, ונקבל מימוש Out of the boxשל המימוש של objectים.

למשל, בדוגמה של השוואת מחרוזות לפי האורך שלהן:

1
2
3
4
5
6
7

public class StringLengthComparer : Comparer<string>
{
    public override int Compare(string x, string y)
    {
        return (x.Length - y.Length);
    }
}

השוואה מתבצעת באמצעות:

1
2
3
4
5
6

StringLengthComparer comparer = new StringLengthComparer();
if (comparer.Compare("Hellllo", "world") > 0)
{
    // True
}

בנוסף, אם אנחנו מעוניינים מאיזושהי סיבה לקבל Comparer שמשתמש בפונקציה CompareTo, במידה והטיפוס שלנו מממש IComparable<T>, נוכל להשתמש בComparer הסטטי הבא:

1

Comparer<T>.Default

כמובן, לרוב הפונקציות שמשתמשות בממשק IComparable<T> בשביל להשוות איברים, קיים overload שמאפשר לציין באמצעות איזה Comparer להשוות.

אולי עוד נראה לזה דוגמאות.

המשך יום בר השוואה טוב

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

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

בשביל זה הומצא ממשק ששמו IComparable<T> המאפשר לנו להשוות איברים.

לממשק זה יש פונקציה אחת:

1

public int CompareTo(T other)

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

צריכות להתקיים האקסיומות הבאות:

• לכל x מתקיים x.CompareTo(x) הוא 0. כלומר כל איבר "שווה" לעצמו
• לכל x,y,z המקיימים x.CompareTo(y) ו y.CompareTo(z), מאותו סימן, גם x.CompareTo(z) מאותו סימן (טרנזיטיביות)
• הסימן של x.CompareTo(y) הפוך לסימן של y.CompareTo(x)

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

למשל, בטיפוס string, מממשים את IComparable<string>, ומשווים מחרוזות לפי המקום שלהם במילון. למיון כזה קוראים מיון לקסיקאלי.

כעת נוכל להשתמש בזה במספר מקומות. למשל, בטיפ מספר 102 ציינו כי קיים Extension Method שלIEnumerable<T>, שנקרא Max המאפשר לנו למצוא מקסימום של אוסף.

לפי מה מתבצעת ההשוואה? לפי הפונקציה CompareTo, במידה והטיפוס מממש את הממשק IComparable<T>.

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

המשך יום בר השוואה טוב

בהמשך לטיפ היומי הקודם,

קיימת גם אפשרות לשימוש בgroup by באמצעות query syntax של LINQ.

1
2
3

IEnumerable<IGrouping<int, Person>> peopleByAge =
    from person in people
    group person by person.Age;

הsyntax שקול לכתיבה:

1
2

IEnumerable<IGrouping<int, Person>> peopleByAge =
    people.GroupBy(person => person.Age);

שזה ממש אחלה..

שימו לב שאין שום select. במידה ונרצה להמשיך ולעשות דברים יותר מסובכים, נצטרך להשתמש במילת הקסם into (טיפ מספר 98):

1
2
3
4
5

IEnumerable<IGrouping<int, Person>> rareAgesGroups =
    from person in people
    group person by person.Age into ageGroup
    where ageGroup.Count() <= 10
    select ageGroup;

זה מוצא לנו את כל האנשים מקובצים לפי גילאים, כאשר בכל קבוצת גיל יש לכל היותר 10 אנשים..

החיסרון, כמובן, בכתיבה זו, הוא שאין ביכולתנו לציין את הIEqualityComparer שאיתו אנחנו רוצים להשוות את הגילאים.

המשך יום מקובץ טוב

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

לפעמים במקום למצוא רק לסנן את האיברים שלנו, כך שכל איבר יופיע רק פעם אחת, אנחנו מעוניינים לעשות משהו אחר – לקבץ את האיברים לפי איזושהי תכונה שלהם

למשל, נניח שיש לנו רשימה של אנשים ואנחנו מעוניינים לקבץ אותם לפי הגיל שלהם, כך שלכל גיל נוכל לראות את כל האנשים בגיל זה.

במקום להשתמש בDistinct ולשלב את זה עם שאילתא אחרת, אפשר להשתמש בExtension Method של LINQ ששמו GroupBy:

1
2

IEnumerable<IGrouping<int, Person>> peopleByAge =
    people.GroupBy(person => person.Age);

הפונקציה מקבלת delegate שמייצג לפי מה אנחנו מעוניינים לקבץ.

אתם בוודאי שואלים את עצמכם מהו IGrouping<int, Person>? זהוIEnumerable<Person> שיש לו Key שמייצג את מה שהקיבוץ נעשה לפיו.

נוכל לעשות משהו כזה:

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

foreach (IGrouping<int, Person> currentGroup in peopleByAge)
{
    Console.WriteLine("The following are {0} years old:",
                      currentGroup.Key);
    foreach (Person person in currentGroup)
    {
        Console.WriteLine("{0} {1}",
                          person.FirstName,
                          person.LastName);
    }
}

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

משהו מגניב שאפשר לעשות: למשל, אנחנו מעוניינים לקטלג אנשים לפי טווח גילאים: 0-12 ילדים, 13-18 נוער, 19 ומעלה מבוגרים. נוכל ליצור IEqualityComparer<int> שמשווה את הגילאים לפי הקריטריונים שכתבתי פה, ולהעביר אותו לקיבוץ:

1
2
3
4

IEqualityComparer<int> ageComparer = new AgeComparer();
IEnumerable<IGrouping<int, Person>> peopleByAge =
    people.GroupBy(person => person.Age, ageComparer);

סופ"ש שווה!

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

קיימת Extension Method בשם Distinct של Linq שמה שהיא עושה זה מסננת את התוצאות כך שכל תוצאה לא תופיע יותר מפעם אחת

1
2
3
4
5

IEnumerable<string> fruits =
    new[] {"Banana", "Orange", "Apple", "BANANA", "Banana", "Mango", "Apple"};
IEnumerable<string> distinctFruits = fruits.Distinct();
// "Banana", "Orange", "Apple", "BANANA", "Mango"

אם כך, מה הקשר לIEqualityComparer?

כפי שוודאי ניחשתם, קיים Overload לDistinct שמקבל IEqualityComparer ולפיו משווה את האיברים.

למשל:

1
2
3

IEnumerable<string> distinctFruits =
    fruits.Distinct(StringComparer.CurrentCultureIgnoreCase);
// "Banana", "Orange", "Apple", "Mango"

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

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

שימו לב שבזכות העובדה שזהו HashSet, כל פעם שאנחנו מוסיפים איבר, אנחנו לא צריכים לעבור על כל האיברים כדי לענות על השאלה האם האיבר כבר הופיע, אלא בגלל שמדובר בHashSet, זה מתבצע כמעט ב$ O\left(1\right) $. (ראו גם טיפ מספר 19)

המימוש הוא משהו בסגנון הזה:

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

public static IEnumerable<T> Distinct<T>(this IEnumerable<T> source,
                                         IEqualityComparer<T> comparer)
{
    HashSet<T> elements = new HashSet<T>(comparer);
    foreach (T current in source)
    {
        if (!elements.Contains(current))
        {
            elements.Add(current);
            yield return current;
        }
    }
}

שימו לב שגם לHashSet יש overload לConstructor שמקבל IEqualityComparer<T> שלפיו הוא משווה איברים בהכנסה ובבדיקה האם הם מופיעים כבר…

המשך יום שווה

בהמשך לשבוע השווה,

נניח שאנחנו מעוניינים בIEqualityComparer שמשווה stringים עם אפשרות להתעלם מcase sensitive או אפשרויות אחרות.

מסתבר שיש כבר מימושים כאלה בFramework, והם יותר טובים מזה שרשמתי בראשון. המימושים משתמשים במחלקה StringComparer.

נוכל להשתמש בהם בצורה הבאה: גישה לאחד מהComparerים הסטטיים הבאים:

1
2
3
4
5
6

StringComparer.CurrentCulture,
StringComparer.CurrentCultureIgnoreCase,
StringComparer.InvariantCulture,
StringComparer.InvariantCultureIgnoreCase,
StringComparer.Ordinal,
StringComparer.OrdinalIgnoreCase

או: שימוש בפונקציה

1

StringComparer.Create

המקבלת CultureInfo והאם להתעלם מcase sensitive.

כך נוכל לדוגמה ממש את הדוגמה של אתמול בצורה הבאה:

1
2

IDictionary<string, object> nameToValue =
    new Dictionary<string, object>(StringComparer.CurrentCultureIgnoreCase);

היתרון במימוש הזה כאמור, הוא שהוא לא יוצר אובייקט חדש עבור כל גישה לDictionary. (מי שרוצה מוזמן לבדוק בReflector)

המשך יום שווה

בפעם הקודמת הכרנו מעט את IEqualityComparer והבטחתי דוגמאות לשימוש בFramework.

דוגמא נחמדה היא הבאה:

נניח שאנחנו רוצים לגשת לערכים לDictionary שהמפתחות שלו הן מחרוזות, אבל ללא case sensitive.

1

IDictionary<string, object> nameToValue = new Dictionary<string, object>();

עד היום היינו עושים את זה כך:

הכנסה לDictionary:

1

nameToValue[givenName.ToUpper()] = givenValue;

הוצאה מהDictionary:

1

requestedValue = nameToValue[givenName.ToUpper()];

מה הבעיה פה? כמו בטיפ מספר 5, בכל פעם שאנחנו ניגשים לDictionary, אנחנו בעצם יוצרים אובייקט חדש (ע"י קריאה לToUpper).

כלומר כל גישה יוצרת אובייקט חדש, וזה אובייקט מבוזבז – מבזבז לנו זמן (ביצירה) וזכרון.

במקום, נוכל להיזכר בקיומם של

1
2
3
4
5
6

בזכות הטיפ היומי של אתמול נוכל לעשות משהו כזה:
```csharp
IDictionary<string, object> nameToValue =
    new Dictionary<string, object>(new StringIgnoreCaseSensitiveComparer());

וכעת נוכל לגשת לDictionary בשיטה הרגילה

1
2

nameToValue[givenName] = givenValue;
requestedValue = nameToValue[givenName];

בלי ליצור אובייקט חדש בכל גישה לDictionary.

הערה: המימוש של אתמול של StringIgnoreCaseSensitiveComparer דווקא כן יוצר אובייקט חדש בכל גישה לDictionary, כי אנחנו קוראים בGetHashCode לToUpper. נראה בהמשך דרך אחרת להשתמש בEqualityComparer שמתעלם מCase sensitive, ולא יוצר אובייקט חדש בכל גישה.

המשך שבוע שווה