Сложно о простом или особенности Linq to objects

LINQ to objects сейчас прочно вошел в нашу жизнь, победоносными шагами ступая по всему стеку .net приложений. В этой статье я бы хотел привести примеры нескольких не очевидных вещей, с которыми довелось столкнуться, работая с LINQ. Интересно — прошу под кат.

1. Особенность работы с List<T>

LINQ отличается в своей реализации когда к нему приходит объект типа IEnumerable<T> и когда приходит List<T>. Даже в простом методе Where создаются разные итераторы:

1. if (source is Iterator<TSource>) return ((Iterator<TSource>)source).Where(predicate);
2. if (source is TSource[]) return new WhereArrayIterator<TSource>((TSource[])source, predicate);
3. if (source is List<TSource>) return new WhereListIterator<TSource>((List<TSource>)source, predicate);

* This source code was highlighted with Source Code Highlighter.

К слову, обратите внимание, что для массива так же будет свой итератор, отличие которого заключается в том, что элементы он будет получать напрямую через обращение по индексу.

Чем же эта особенность интересна для нас? Ну, например, я обычно скептически подходил к вызову конструкции Last, т.к. она по идеи должна пройти по всему энумератору до конца. Однако если вы применяете ее к объекту, реализующему интерфейс IList<T>, то последний элемент будет получен через индексатор, что конечно уже не так плохо.

1.  public static TSource LastOrDefault<TSource>(this IEnumerable<TSource> source) {
2.       if (source == null) throw Error.ArgumentNull("source");
3.       IList<TSource> list = source as IList<TSource>;
4.       if (list != null) {
5.         int count = list.Count;
6.         if (count > 0) return list[count - 1];
7.       }
8.       else {

* This source code was highlighted with Source Code Highlighter.

Аналогичная оптимизация сделана для методов типа Single

1.  public static TSource Single<TSource>(this IEnumerable<TSource> source) {
2.       if (source == null) throw Error.ArgumentNull("source");
3.       IList<TSource> list = source as IList<TSource>;
4.       if (list != null) {
5.         switch (list.Count) {
6.           case 0: throw Error.NoElements();
7.           case 1: return list[0];

* This source code was highlighted with Source Code Highlighter.

2. Работа GroupBy

Допустим у нас есть такой код:

1. class Key
2. {
3.   private readonly int _number;
4.   public static int HashCallsCount;
5.   public static int EqualsCallsCount;
6.  
7.   public Key(int number)
8.   {
9.     _number = number;
10.   }
11.  
12.   public bool Equals(Key other)
13.   {
14.     if (ReferenceEquals(null, other))
15.     {
16.       return false;
17.     }
18.     if (ReferenceEquals(this, other))
19.     {
20.       return true;
21.     }
22.     return other._number == _number;
23.   }
24.  
25.   public override bool Equals(object obj)
26.   {
27.     EqualsCallsCount++;
28.     if (ReferenceEquals(null, obj))
29.     {
30.       return false;
31.     }
32.     if (ReferenceEquals(this, obj))
33.     {
34.       return true;
35.     }
36.     if (obj.GetType() != typeof (Key))
37.     {
38.       return false;
39.     }
40.     return Equals((Key) obj);
41.   }
42.  
43.   public override int GetHashCode()
44.   {
45.     HashCallsCount++;
46.     return _number;
47.   }
48. }
49.  
50. class Test
51. {
52.   public int Number { get; set; }
53.   public string Name { get; set; }
54.  
55.   public Key Key
56.   {
57.     get { return new Key(Number);}
58.   }
59.  
60.   public override string ToString()
61.   {
62.     return string.Format("Number: {0}, Name: {1}", Number, Name);
63.   }
64. }
65. internal class Program
66. {
67.   private static void Main(string[] args)
68.   {
69.  
70.     var items = Enumerable.Range(1, 20).Select(x => new Test {Number = x%3});
71.  
72.     foreach (var group in items.GroupBy(x=>x.Key))
73.     {
74.       Console.WriteLine("Group key: {0}", group.Key);
75.       foreach (var item in group)
76.       {
77.         Console.WriteLine(item);
78.       }
79.     }
80.  
81.     Console.WriteLine("EqualsCallsCount {0}", Key.EqualsCallsCount);
82.     Console.WriteLine("HashCallsCount {0}", Key.HashCallsCount);
83.   }  
84. }

* This source code was highlighted with Source Code Highlighter.

Какое значение будет выведено на экран для переменных EqualsCallsCount и HashCallsCount? 17 и 20 соответственно. 17 — т.к. значения, которые стали ключами группы с другими ключами сравниваться не будут(на всякий случай укажу, что группа в данном примере получается ровно 3). 20 же вызов, т.к. hashсode от объекта Key используется для определения в какую группу помещать объект Test. Тут надо заметить, что если хэшкод перестанет давать уникальные значения(например всегда будет возвращать 0), то количество вызов Equals вырастет до 38. Причины, думаю, понятны. Еще одна интересная деталь это то, что массив групп по умолчанию равен 7

1. Lookup(IEqualityComparer<TKey> comparer) {
2.       if (comparer == null) comparer = EqualityComparer<TKey>.Default;
3.       this.comparer = comparer;
4.       groupings = new Grouping[7];
5.     }

* This source code was highlighted with Source Code Highlighter.

И затем линейно увеличивается, производя на этом шаге копирование всего массива.

1.  void Resize() {
2.       int newSize = checked(count * 2 + 1);
3.       Grouping[] newGroupings = new Grouping[newSize];
4.       Grouping g = lastGrouping;
5.       do {
6.         g = g.next;
7.         int index = g.hashCode % newSize;
8.         g.hashNext = newGroupings[index];
9.         newGroupings[index] = g;
10.       } while (g != lastGrouping);
11.       groupings = newGroupings;
12.     }

* This source code was highlighted with Source Code Highlighter.

Т.к. указать capacity для метода GroupBy нельзя, то лучше воздержаться от группировки с большим количеством ключей, иначе могу возникнуть проблемы с памятью(ну и скорость конечно просядет).

3. Энумератор это тоже объект

Рассмотрим две функции:

1. private static IEnumerable<Test> SortTest(Func<IEnumerable<Test>> list)
2.   {
3.     foreach (var item in list().OrderBy(x => x.Number).ThenBy(x => x.Name))
4.     {
5.       yield return item;
6.     }
7.   }

* This source code was highlighted with Source Code Highlighter.

и

1. private static IEnumerable<Test> SortTest2(Func<IEnumerable<Test>> list)
2.   {
3.     return list().OrderBy(x => x.Number).ThenBy(x => x.Name);
4.   }

* This source code was highlighted with Source Code Highlighter.

Будем считать, что list() возвращает устойчивый список элементов, например массив. Являются ли функции эквивалентными? Конечно нет(кстати в последнем решарпере есть соответствующая бага). В первом случае функция list() будет вызываться всегда, когда мы будем проходить возвращаемый энумератор. И соответственно, если она станем возвращать другие значения, то и значения энумератора станут другими. Во втором же случае функция list() будет вызвана только один раз, ее результат сохранится в поле source класса OrderedEnumerable<TElement, TKey> и в дальнейшем сколько бы мы не проходили возращенный энумератор, значения в нем будут одни и те же.

Заключенние

Надеюсь данная небольшая статья будет для кого-то полезна и поможет избежать ошибок при работе с Linq to object. Замечания и дополнения приветствуются.

Ссылки

MSDN o LINQ

Спасибо за внимание.