אלגוריתם: סינון מערך (#C)

[קומפיונט]

שלום לכולם.

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

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

[dovid]

@קומפיונט
אם אתה רוצה את האלמנט ממש, אז הייתי עושה ככה:

var testList = new[]
{
	new  { id = 1, version = 1},
	new  { id = 1, version = 5},
	new  { id = 2, version = 4},
	new  { id = 3, version = 3},
	new  { id = 3, version = 2},
	new  { id = 3, version = 1},
	new  { id = 1, version = 12},
	new  { id = 1, version = 155}
};

var distinct = testList.GroupBy(l => l.id).Select(x => x.OrderByDescending(y => y.version).First());

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

var distinct2 = testList.GroupBy(l => l.id).Select(x => new { maxVersion = x.Max(y => y.version), id = x.Key});

[קומפיונט]

@dovid זה פשוט מדהים...

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

public static class DistinctByVersionExtensions
    {
        public static IEnumerable<Lazy<TSource, TSourceMetadata>> DistinctByVersion<TSource, TSourceMetadata>(this IEnumerable<Lazy<TSource, TSourceMetadata>> source, Func<TSourceMetadata, string> idSelector, Func<TSourceMetadata, double> versionSelector)
        {
            foreach (Lazy<TSource, TSourceMetadata> item in source)
            {
                string id = idSelector(item.Metadata);

                IEnumerable<Lazy<TSource, TSourceMetadata>> same_ids = source.Where(v => idSelector(v.Metadata) == id);

                if (same_ids.Any())
                {
                    double ver = versionSelector(item.Metadata);
                    double max_ver = same_ids.Max(v => versionSelector(v.Metadata));

                    if (ver == max_ver)
                        yield return item;
                }
                else
                {
                    yield return item;
                }
            }
        }
    }

ולא חשבתי שזה כל כך פשוט..

אגב, יותר נחמד זה ככה:

.Select(x => x.OrderBy(y => y.version).Last());

במקום:

.Select(x => x.OrderByDescending(y => y.version).First());

ומגרסת 6.0 של NET. אפשר גם ככה:

.Select(x => x.MaxBy(y => y.version));

[dovid]

@קומפיונט הFirst יעיל יותר לפחות תיאורטית מהLast, כי המיון נקטע מייד בהתחלה.
הMax אמור להיות עוד יותר יעיל.

[yossiz]

@dovid איכפת לך להסביר למה לדעתך ה-max אמור להיות יותר יעיל?

[dovid]

@yossiz כי בOrderBy במקום להחזיר את הקיצון התורן, אפשר ליישם את זה עם אלגוריתם מיון טוב יותר כל שהוא של בועות או החלפה וכדומה, וזה מיותר.

[dovid]

@קומפיונט אני מתפעל (למרות שלא ירדתי לעומקה) של הפונקציה הגנרית שעשית.
אבל בד"כ זה מאמץ מיותר להשקיע על גנריות בכאלה דברים, תעשה פונקציה ממוקדת לצורך שלך עם לולאה (שזה יהיה מהר בהרבה מהLINQ למקרה ואתה משתתף בתחרות ביצועים...), ורק כשתצטרך נסה להפוך אותה לגנרית.
(כמובן שפונקציה מותאמת וספציפית תהיה בד"כ קלה יותר לכתיבה וגם כתופעת לוואי של פשטותה יותר מהירה גם למחשב).
אני חושב כיום שחלק מהזמן השרוף של פיתוח של מפתחים אידאליסטים הולך על גנריות כזו של "פונקציה שעושה כל מה שצריך לכל דבר". כיון שהייתי בדיוק כזה, אני היום מזהה כאלו סכנות.
חיפשתי בגוגל על זה ומצאתי כאלה שכותבים ממש כדברי אבל לא מצאתי מאמרים של ממש
https://softwareengineering.stackexchange.com/questions/361605/should-the-solution-be-as-generic-as-possible-or-as-specific-as-possible
עריכה: מצאתי מאמר Just don't write generic code

ובשביל הנוסטלגיה, מדריך ארכיטקטורת תוכנה - שיעור 2 גנריות לעומת ספציפיות

[yossiz]

@dovid תודה על הארת העיניים,
עוררת אותי לבדוק איך זה באמת ממומש,
מה שיוצא הוא שהפונקציה OrderByDescending בכלל לא עושה מיון, זה מחזיר אובייקט (OrderedEnumerable) שיעשה מיון אם יהיה צורך, אם אתה קורא עליו First הוא כבר מספיק חכם (או עצלן) להבין שלא צריך למיין.
הפעולות בפועל פחות או יותר זהה למה שקורה עם קריאה ל-max (חוץ מהצורך ליצור אובייקט אמצעי)

כמובן, עדיין max מומלץ על פני OrderBy + First הן מפאת קריאות וקיצור, והן משום שכך זה יקבל אוטומטי כל מיטוב עתידי

[קומפיונט]

פוסט זה נמחק!

[dovid]

@קומפיונט אמר באלגוריתם: סינון מערך (#C):

אצלי זה נצרך בגלל MEF.

לא יודע מה זה MEF, אנחנו אנשים פשוטים פה, תשתדל להתאים ל"עממי".

[קומפיונט]

@dovid אמר באלגוריתם: סינון מערך (#C):

לא יודע מה זה MEF, אנחנו אנשים פשוטים פה, תשתדל להתאים ל"עממי".

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

[Aharon 0]

@קומפיונט לא כדאי להשתמש ב max, מספיק שערך אחד null וזה מחסיר תוצאה שגויה

[קומפיונט]

יש דרך יותר נחמדה לקוד דלעיל:

var distinct = testList.GroupBy(l => l.id).Select(x => x.MaxBy(y => y.version));

אפשר לכתוב אותו גם ככה:

var distinct = from item in testList
               group item by item.id into id_grp
               select id_grp.MaxBy(x => x.version);

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

@קומפיונט לא כדאי להשתמש ב max, מספיק שערך אחד null וזה מחסיר תוצאה שגויה

@Aharon-0 באמת הארת את עיני, אבל לא חושב שלכן צריך לזרוק את Max לפח, רק צריך להשתמש בו בצורה נבונה.

לדוגמא:

list.Max(e => e is null ? 0 : e.value)

או:

list.Where(e => e is not null).Max(e => e.value)

[dovid]

פוסט זה נמחק!

[dovid]

@קומפיונט מיהרת לתת מענה לבעיה של @Aharon-0
א. אשמח אם תמצא מקרה בו יש בעיה
ב. הכתיב במענה שלך הוא של VB.

[קומפיונט]

@dovid אמר באלגוריתם: סינון מערך (#C):

@קומפיונט מיהרת לתת מענה לבעיה של @Aharon-0
א. אשמח אם תמצא מקרה בו יש בעיה
ב. הכתיב במענה שלך הוא של VB.

א. אם יש לך מערך של אובייקטים ובכל אובייקט מצוין לצורך הדוגמא איש עם פרטים כגון שם גיל וכדו'. עכשיו אתה רוצה לשלוף את הגיל של האיש המבוגר ביותר, אז אתה תעשה את זה ככה:

int max = pople.Max(p => p.Age);

ותקבל את הגיל של האיש המבוגר ביותר.
אבל מה יקרה אחד האנשים ברשימה הוא null? התשובה היא שייזרק exception! כי הוא לא יכול לגשת לגיל של אובייקט null.

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

ב. אני לא נוגע בVB ואני לא יודע למה אתה אומר שזה רק בVB, אצלי זה רץ מצוין ב#C. יתכן בהחלט שלא הבנתי למה התכוונת.

[dovid]

@קומפיונט אמר באלגוריתם: סינון מערך (#C):

אבל מה יקרה אחד האנשים ברשימה הוא null? התשובה היא שייזרק exception! כי הוא לא יכול לגשת לגיל של אובייקט null.

ומה זה קשור לMax?
ויש דרך אחרת בעולם לשיטת ה"בעיה" שלא תהיה שגיאה?
כל הדרכים שהוצגו לעיל יעשו שגיאה במקרה שאמרת, וגם זה די נדיר שיש אוסף שאחד מאיבריו הוא ריק.
ואגב בשביל בעיה זו יש ? כלומר לכתוב p?.Age.
אני הבנתי ש@Aharon-0 מתכוון לMax על ערך int? שיש בו null אבל גם שם אני לא מוצא את הבעיה בבדיקה שלי וגם זה משונה לקבוע בגלל זה שMax היא לא דרך טובה. על דרך מכונית היא כלי רכב גרוע כי הוא לא צולח נהרות.

[dovid]

@קומפיונט אמר באלגוריתם: סינון מערך (#C):

ב. אני לא נוגע בVB ואני לא יודע למה אתה אומר שזה רק בVB, אצלי זה רץ מצוין ב#C. יתכן בהחלט שלא הבנתי למה התכוונת.

אני אכן לא כותב בC# 7-9 (הnot עובד רק ב9)
אז טעיתי בזה.

[קומפיונט]

סורי, היתה לי טעות קטנה.
@dovid אתה צודק לגמרי.
@Aharon-0 אולי תסביר את דברך.

[קומפיונט]

@dovid אמר באלגוריתם: סינון מערך (#C):

ויש דרך אחרת בעולם לשיטת ה"בעיה" שלא תהיה שגיאה?

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

כל הדרכים שהוצגו לעיל יעשו שגיאה במקרה שאמרת,

שוב לא הבנתי את דבריך. אצלי בשתי הדרכים לא זורק שגיאה, ורק בקריאה לMax זה כן זורק שגיאה.