114. Distinct extension method

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

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

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 ולפיו משווה את האיברים.

למשל:

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

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

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

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

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

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> שלפיו הוא משווה איברים בהכנסה ובבדיקה האם הם מופיעים כבר…

המשך יום שווה