LINQ - 11道 LINQ題目 (解答版)

  說好要解答的,所以就來吧,這是當下最佳解,以後搞不好我有新的解法也不一定。

 

  在開始之前,我們需要一個類別(Person)及一個函式 (GenerateFixedPersons),為了量測效能,這裡還有一個Benchmark函式。

//help functions
public class Person
{
    private static Person _empty = new Person();
    public static Person Empty => _empty;

    public string Name { get; set; }
    public int Age { get; set; }
    public int Salary { get; set; }
    public int DepartmentID { get; set; }
}

static List<Person> GenerateFixedPersons(int max)
{
    const string characters = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string[] citys =
       {
         "Taipei",
         "NewYork",
         "London",
         "Tokyo"
    };
    var random = new Random();
    return Enumerable.Repeat<Person>(Person.Empty, max).Select(s =>
           {
             return new Person()
             {
               Name = new string(Enumerable.Repeat(characters, 10).Select(a => a[random.Next(a.Length)]).ToArray()),
               Age = random.Next(100)
             };
           }).ToList();
}

static void Benchmark(Action action, string label)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    action();
    sw.Stop();
    Console.WriteLine($"benchmark for {label}");
    Console.WriteLine($"{sw.ElapsedMilliseconds} ms");
}

 

1. LINQ Where與foreach

   如下圖,哪個比較快?

  這是一個觀念題,適用於大多數情況,有了GenerateFixedPersons跟Benchmark兩個函式,我們可以輕易地解出答案。

 //item 1
static void SearchWithForeach(List<Person> data)
{
    foreach (var item in data)
    {
         if (item.Age > 100)
         {
             Console.WriteLine($"{item.Name}, Age:{item.Age}");
             return;
         }
    }
    Console.WriteLine("not found");
}

static void SearchWithLINQ(List<Person> data)
{
    var item = data.FirstOrDefault(a => a.Age > 100);
    if (item != null)
        Console.WriteLine($"{item.Name}, Age:{item.Age}");
    else
        Console.WriteLine("not found");
}

static void Main(string[] args)
{
    var list = GenerateFixedPersons(1500000);
    list.Add(new Person() { Name = "c", Age = 101 });;

    Benchmark(() => SearchWithForeach(list), "foreach");
    Benchmark(() => SearchWithLINQ(list), "linq");

    Console.ReadLine();
}

結果如下圖。

問題不在結果,結果大概可以猜出來,問題是為什麼?很簡單,LINQ基礎是delegate,也就是委派,呼叫委派就跟呼叫另一個函式一樣,在C#,委派的成本多數情況下會比函式高一些,因為C#編譯器會對函式進行inline,而委派的inline複雜度很高,所以幾乎不會進行inline,

那這是不要用LINQ的意思嗎?當然不是,用LINQ可以幫助減少程式碼,在框架下甚至可以減少錯誤發生的機會,這樣的交換是值得的,這題的目的只是要提醒委派成本的存在,如果日後這個差距成為負擔,有個方向可以走。

委派有成本,LINQ也有

 

 

2.   在下圖的GenerateFixedPersons產生出500000筆資料,Age會是1-100之間的亂數,在 //calll 處分別呼叫兩個函式,哪個比較快?為什麼?

這是個行為題,呈現FirstOrDefault與LastOrDefault的行為,要驗證很簡單,丟進Benchmark函式即可。

static void Main(string[] args)
{
    var list = GenerateFixedPersons(1500000);
    list.Add(new Person() { Name = "c", Age = 101 });;

    Benchmark(() => SearchWithLINQ(list), "firstordefault");
    Benchmark(() => SearchWithLastOrDefault(list), "lastordefault");

    Console.ReadLine();
}

差距的原因是LINQ基於Enumerator設計,只往前不往後,因此LastOrDefault的行為必然是從頭開始找,儲存符合條件的元素,再繼續往下比對,如果再發現符合條件的,就保存並丟棄上一個符合條件的,所以一定是跑到最後一個元素,相較於FirstOrDefault在第一個符合條件元素就回傳並結束的行為,自然是慢多了。

但這有一個例外,當LastOrDefault沒有條件時,會先判斷傳入的元素集是否支援IList,是的話會用Index跟Length來取值,下例可證明這點。

 Benchmark(() => SearchWithLINQ(list), "firstordefault");
 Benchmark(() =>
          {
            var item = list.LastOrDefault();
            Console.WriteLine($"{item.Name}, Age:{item.Age}");
          }
   , "lastordefault");

LastOrDefault有條件時,會從頭找到尾端

 

3.有方法可以加快這個程式的搜尋效能嗎?

這是應用題,Where跟FirstOrDefault帶條件時,都是從頭一個個找,當需要更快的搜尋方式時,演算法是必要的,如果不是很注重效能的,至少要把Dictionary擺出來。

static void SearchWithDictionary(ILookup<int, Person> data, int age)
{
    var item = data[age / 10].FirstOrDefault(a => a.Age > age);
    if (item != null)
        Console.WriteLine($"{item.Name}, Age:{item.Age}");
    else
        Console.WriteLine("not found");
}

static void Main(string[] args)
{
    var list = GenerateFixedPersons(1500000);
    list.Add(new Person() { Name = "c", Age = 101 });
    var lookup = list.ToLookup(a => a.Age / 10);
    int index = 1;
    do
    {
        if (int.TryParse(Console.ReadLine(), out int val))
        {
            SearchWithDictionary(lookup, val);
            index++;
        }
        else
            Console.WriteLine("wrong input");
    }
    while (index < 3);            

    Console.ReadLine();
 }
LINQ很方便,但不能成為不鳥演算法的理由

 

4. 假設傳入值是同一個,這兩個函式的結果一樣嗎?效能一樣嗎?為什麼?

測一下就知道了。

static void Main(string[] args)
{
   var list = GenerateFixedPersons(500000);
   list.Add(new Person() { Name = "c", Age = 101 });
   Benchmark(() => UseOrderByChain(list), "chain");
   Benchmark(() => UseOrderByThenBy(list), "thenby");

   Console.ReadLine();
}

結果。

一樣是行為題,結果一定不一樣,問題在效能,一般都知道OrderBy後面要接ThenBy,但雙層OrderBy的例子會帶出一個問題,那就是OrderBy如何實作的? 很簡單,就是當LINQ運算式的結果需要被取出第一個值時,就會進行排序,形成一個暫存陣列,然後吐出值來,在雙層OrderBy的情況下,foreach是由最後的OrderBy取值,此時最後的OrderBy要向前面的運算式取值,也就是上一個OrderBy,上一個OrderBy進行排序後吐值給最後一個OrderBy再進行排序,所以自然是比較慢,要證明這點,只要在後方的OrderBy下中斷點就可以了,其值一定是前面那個OrderBy排好的。

LINQ運算式會在取值開始執行,也就是Delay Execution,最後的要向前面取值,以此類推直到起點。

 

5.Min跟Max每次都是重頭跑過,所以若要取得一個元素集的Min跟Max,那麼就得跑兩次,如下

有沒有方法可以只跑一次迴圈?效能會比較好嗎?為什麼?

這個題目有兩個點,一個是觀念題,迴圈跑一次會比跑兩次快嗎?如果迴圈內的程式碼相同,自然是無庸置疑一次比較快,但LINQ是基於Delegate設計,把委派成本考慮進去就不一定了,另一個點是怎麼只跑一次,LINQ中的Aggregate函式可以幫忙。

static void UseMinMax(List<Person> data)
{
    var min = data.Min(a => a.Age);
    var max = data.Max(a => a.Age);
    Console.WriteLine($"Min: {min} Max: {max}");
}

static void CombinMinMaxWithAggregate(List<Person> data)
{
    var result = data.Select(a => a.Age).Aggregate(new
    {
         Min = int.MaxValue,
         Max = int.MinValue
    },
    (x, y) => new
    {
         Min = Math.Min(x.Min, y),
         Max = Math.Max(x.Max, y)
    });
    Console.WriteLine($"Min : {result.Min}, Max: {result.Max}");
 }

       

 static void Main(string[] args)
 {
    var list = GenerateFixedPersons(500000);
    list.Add(new Person() { Name = "c", Age = 101 });
    Benchmark(() => UseMinMax(list), "Min&Max");
    Benchmark(() => CombinMinMaxWithAggregate(list), "Aggregate");

    Console.ReadLine();
}

 

結果。

看完第一題後,應該對這個結果不意外,就是委派成本,如果真的需要拿回這些效能,foreach是最簡單直覺的實作方式。

不要錯誤解讀,LINQ是減少程式碼,進一步以框架來減少犯錯機會。

委派要成本,委派要成本,委派要成本

 

 

6.這兩個函式的結果一樣嗎?行為一樣嗎? 為什麼?

觀念題,結果是一樣的,過程不是,用反組譯工具看一下。

C#編譯器面對Queryable時,會把所有的LINQ 函式呼叫轉成Expression,然後丟給LINQ Query Provider解譯及執行,以此例來說,這個LINQ Query Provider就是EnumerableQuery,這是內建的LINQ Query Provider,執行目標則是Enumerable<T>,就過程而言,轉譯為Expression的動作是在編譯器完成,所以理論上不會造成負擔,但解譯是Runtime處理,會造成一些負擔。

你應該不會這樣寫吧?其實我有這樣寫過,當碰觸LINQ Query Provider時候,什麼事都有可能發生。

Queryable是另一個世界,會改變所有LINQ行為。

 

7. 用LINQ實作Find Text in Files(在目錄中尋找包含指定字串的檔案,例如.txt、.ini)的功能

 這是應用題。

static void FindTextInFiles()
{
    var result = from s1 in Directory.GetFiles(@"C:\Windows", "*.ini")
                 let content = File.ReadAllText(s1)
                 where content.Contains("drivers")
                 select s1;
    foreach (var item in result)
    {
        Console.WriteLine(item);
    }
}
任何Enumerable都可以用LINQ處理。

 

8. 這個函式可以正常執行,但有更好的做法嗎?

這是個發想題,如果你只是想知道元素集有沒有符合條件的,沒有進一步動作,用Any。

static void CheckExistsUseAny(List<Person> data)
{
    if (data.Any(a => a.Age > 100))
        Console.WriteLine("found");
    else
        Console.WriteLine("not found");
}

就概念上來說,它跟FirstOrDefault效能差不多,但進一步思考,如果面對的是structure,FirstOrDefault是會回傳預設值的,用它來對structure類的元素集判斷特定元素存不存在是有風險的。

 

不要把Count()拿出來用,它跟LastOrDefault一樣,帶條件時會跑到尾端。

 

9. 有沒有方法可以簡化雙層foreach成為一層?

 如果沒看清楚題目的話,這是陷阱題(說好不放陷阱的),因為WriteLine會印出部門及成員名稱,所以要用到SelectMany的另一個重載函式。

public class Department
{
    public int ID { get; set; }
    public string Name { get; set; }
    public List<Person> Members { get; set; }
}

static void SelectManyForHierarchy()
{
    Department[] list =
    {
        new Department()
        {
             Name = "RD",
             Members = new List<Person>()
             {
                 new Person() { Name = "mary"},
                 new Person() { Name = "mark"}
             }
        },
        new Department()
        {
             Name = "Sales",
             Members = new List<Person>()
             {
                new Person() { Name = "brain"},
                new Person() { Name = "tobe"}
             }
        }
    };

    foreach (var item in list.SelectMany(a => a.Members,
             (dep, member) =>
               new
               {
                  Dep = dep,
                  Member = member
               })) 
    {
        Console.WriteLine($"Dep: {item.Dep.Name}, Member: {item.Member.Name}");
    }
}

如果不想看到這麼科技感的寫法,用LINQ Expression寫法可以寫嗎?出奇的簡單哦。

 

 

 

 

 

 

我是空格

 

 

 

 

 

 

 

 

 

 

 

 

foreach (var item in from s1 in list
                     from s2 in s1.Members
              select new
              {
                    Dep = s1,
                    Member = s2
              })
{
      Console.WriteLine($"Dep: {item.Dep.Name}, Member: {item.Member.Name}");
}

 

LINQ有很多重載函式,不要忘記它們。

 

10. 這個例子中,在印出RD部門的薪資總額時,請問Sales的薪資總額計算好了嗎?為什麼?

這是觀念題,答案是沒有,基於延遲執行原則,從最後開始取值。

 

11. 這是一個大題目,如下例。

switch的缺點是定型,以後如果AlterType增加,就要回到AlterNow增加case區段,有沒有方法可以省掉這個switch,達到增加AlterType不用修改AlterNow?

這是一個擴散應用題,通常能解出來就有一定的水準,解的過程中可以看出架構設計能力,在以下的中等解也能看出對於LINQ的理解度。

static IDictionary<AlterType, Action> mapping = null;

public static void AlterNow2(AlterType type)
{
   if (mapping == null)
   {
      mapping = typeof(AlterType).GetEnumValues().Cast<AlterType>().Join
                (
                   typeof(MyEventHandler).GetMethods(BindingFlags.Static | BindingFlags.Public), 
                   a => a, 
                   a => Enum.Parse(typeof(AlterType), a.Name.Replace("Alter", "")), (t, e) => new
                   {
                       Type = t,
                       EventHandler = e
                   }).ToDictionary(a => a.Type, 
                      a => new Action( ()=> a.EventHandler.Invoke(null, null)));
       mapping[type]();
   }
}

上等解是怎麼做?我的上等解會用Attribute,不過我不想過度複雜這個例子,如果連組態外部檔,DI都帶進來,那就是信仰解。

看出LINQ的理解度?這個例子應用了LINQ的Join延遲執行特色,在Join當下產生Join的右端式,同樣技巧可以用在GroupBy跟OrderBy等情境。

延遲執行,代表著可在執行當下改變條件式

 

就這樣,報告完畢,歡迎在粉絲頁留言討論或是指教,不知道在哪?(眼眶濕....)    https://www.facebook.com/cooldotnet/

喔,最後你問這幾ms的效能有差嗎?你知道60 FPS每個 frame 只有16.6 ms可以用,你說有沒有差呢?

然後你問我有沒有可能我的程式有錯?當然有可能啊。

我這輩子只有在Console印Hello World這種程式才有87% 自信自己沒有錯好嗎?