專案出現的小需求:想在陣列挑出連續重複出現的項目,例如要從陣列 [A, B, B, C, X, C, C, B, B, D, D, D] 挑出 [B, B]、[C, C]、[B, B]、[D, D, D] 四個群組。

這題目的難易度用來暖身剛好,適合用 yield return 來解。

最後琢磨成品如下:
(補充:所謂的「好程式」有許多不同的衡量標準,我的這個版本追求簡潔好寫易讀,專案要處理陣列長度不超過 20,故未將效能作為首要考量,但應能滿足絕大部分的情境。如要進一步提升效能,有幾個建議方向:避用 List 改用更輕巧的資料結構、讓 Iterator 從到尾只跑一次... 等等。)

IEnumerable<IEnumerable<T>> FindRepeatItemGroups<T>(IEnumerable<T> list, Func<T, T, bool> areEqual)
{
    if (list.Any())
    {
        var grp = new List<T>() { list.First() };
        foreach (var item in list.Skip(1))
        {
            if (areEqual(grp.Last(), item))
            {
                grp.Add(item);
            }
            else
            {
                if (grp.Count() > 1)
                    yield return grp;
                grp = new List<T>() { item };
            }
        }
        if (grp.Count() > 1)
            yield return grp;
    }
}

函式接收 IEnumerable<T> 作為搜尋對象,是否重複出現由 Func<T, T, bool> 決定,呼叫時傳入 (a, b) => a.SomeProp == b.SomeProp 自訂比對條件。函式使用 List<T> 蒐集重複出現的物件,以 foreach 巡覽所有元素,遇到目前物件與 List<T> 保存物件不相等時,檢查 List<T> 個數若大於一,表示連續出現,yield return 傳回 List<T> 清空 List<T> 重新統計。

測試範例如下:

var raw = "A,B,B,C,X,C,C,B,B,D,D,D".Split(',');
var i = 1;
var items = raw.Select(o => new
{
    Id = i++,
    Code = o
}).ToArray();
Console.ForegroundColor = ConsoleColor.White;
Console.WriteLine("Source: ");
foreach (var item in items)
{
    Console.ForegroundColor = ConsoleColor.DarkGray;
    Console.Write($"{item.Id}.");
    Console.ForegroundColor = ConsoleColor.Yellow;
    Console.Write($"{item.Code} ");
}
Console.WriteLine();
Console.ForegroundColor = ConsoleColor.Cyan;
var grps = FindRepeatItemGroups(items, (a, b) => a.Code == b.Code);
foreach (var grp in grps)
{
    Console.Write($"Group of {grp.First().Code} :");
    Console.WriteLine($" {string.Join(", ", grp.Select(o => o.Id))}");
}
Console.ResetColor();

IEnumerable<IEnumerable<T>> FindRepeatItemGroups<T>(IEnumerable<T> list, 
        Func<T, T, bool> areEqual)
{
    if (list.Any())
    {
        var grp = new List<T>() { list.First() };
        foreach (var item in list.Skip(1))
        {
            if (areEqual(grp.Last(), item))
            {
                grp.Add(item);
            }
            else
            {
                if (grp.Count() > 1)
                    yield return grp;
                grp = new List<T>() { item };
            }
        }
        if (grp.Count() > 1)
            yield return grp;
    }
}

Example of finding groups of repeated items from an array with LINQ and yield return.


Comments

# by CIHsieh

另一思路可使用Dependency Injection,且避免使用Linq、盡量重複使用物件,應可再壓榨出一些效能。 https://dotnetfiddle.net/IPnbpX

# by 路人甲

寫這種題目最以儘量以 time complexity, space complexity 為出發,不然的話,你以為你解了題目,但效能和記憶體卻是很慘的. 若你不覺得慘,原因是 input 太小了. 在 loop ,不斷地產生 List (array) 物件,這是完全沒必要的.

# by Jeffrey

to 路人甲,所謂的「好程式」有許多不同的衡量標準,我這個版本追求簡潔好寫易讀,專案要處理陣列長度不超過 20,故未將效能作為首要考量,但應能滿足絕大部分的情境。但很謝謝你的提醒,我已在文章補上考量前題及效能議題,讓視角更周全。 另外分享,兩年前讀完「重構」,讓我對於寫程式是否該永遠把效能、記憶體用量放在第一位產生不同想法。 閒聊 - 「好程式」跟你想的不一樣! 初讀「重構」有感 https://blog.darkthread.net/blog/refactoring-and-performance/

Post a comment