Сложно о простом или особенности 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

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

    Комментарии 10

      +7
      Честно говоря, прочитав заголовок, ожидал увидеть под катом банальный обзор редкоиспользуемых методов. А у вас тут действительно интересные моменты описаны.
        0
        Спасибо.
        +1
        Должен заметить, что конструкцию «yield return» нужно использовать аккуратно. В частности, недавно получил неожиданный BadImageFormatException на такой код: gist.github.com/1085737
        С моей точки зрения код валиден, но разбираться в том, почему это не работает, я предоставил ребятам из Microsoft, написав баг-репорт. Я буду премного благодарен тому, кто разъяснит мне причину этого исключения.
          +1
          А там у них вообще все плохо с компилятором стало. Вот, например, бага с энумератором, которую я нашел. Или вот бага с try...catch, тоже BadImageFormatException.
            0
            Мы с вами нашли одну и ту же багу) С try/ctache — это интересно)
          0
          Спасибо за статью, честно говоря никогда не задумывался о подобном различии объектов в LINQ.
            0
            Спасибо вам =)

            Вот в качестве бонуса еще о потрохах .net
            Какой самый быстрый способ проверить элемент на вхождение в список? Многие используют Contains и они абсолютно не правы
            1. var list = new List<string>();
            2. list.AddRange(Enumerable.Range(1, 10000000).Select(x => x.ToString()));
            3.  
            4. var sw = Stopwatch.StartNew();
            5. Console.WriteLine(list.Exists(x => x == "10000000"));
            6. sw.Stop();
            7.  
            8. Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            9.  
            10.  
            11. sw = Stopwatch.StartNew();
            12. Console.WriteLine(list.Contains("10000000"));
            13. sw.Stop();
            14.  
            15. Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            16.  
            17. sw = Stopwatch.StartNew();
            18. Console.WriteLine(list.BinarySearch("10000000") != -1);
            19. sw.Stop();
            20.  
            21. Console.WriteLine(sw.Elapsed.TotalMilliseconds);
            * This source code was highlighted with Source Code Highlighter.

            True
            142,6747
            True
            187,8975
            True
            0,5824
              0
              Ну разница заметна, а чем подобное можно объяснить? И справедливо ли это для комплексных объектов.
                0
                Первый проигрывает, т.к. дополнительно тратимся на вызов функции предиката и функция энумератора. Во втором идет вызов прямой Equals по N элементов с первого по последний. Ну а бинарный поиск в данном случае работает быстрее, т.к. наши элементы в списке отсортированы.
                  0
                  ну тогда честнее будет смотреть время Sort + BinarySearch

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое