Lazy evaluation в IEnumerable

Всем привет!

Сегодня я бы хотел поговорить о Lazy evaluation (ленивые вычисления), а точнее об этой особенности в IEnumerable. Этот очень удобный интерфейс применяется повсеместно, но не всегда при этом разработчик понимает тонкости его работы. С этим могут быть связаны разные проблемы: лишние вычисления, неверные результаты и пр. В этой статье мне хотелось бы пролить свет на некоторые возможные проблемы использования IEnumerable, чтобы избежать плачевных последствий.


В основном, проблемы возникают из-за того, что разработчик четко не понимает различий между IEnumerable, Array, List и т.д. У всех этих контейнеров разная природа. Например, для того, чтобы работать с Array мы должны четко указать какого размера мы хотим выделять память, и работаем уже с конкретными ячейками памяти, к которым в любой момент времени можем обратиться. List, хоть и обладаем динамичным размером, внутри реализован через тот же Array, просто когда происходит переполнение, память перераспределяется. И так же в любой момент можно непосредственно обратиться к объекту.

С IEnumerable ситуация совсем другая. Объявление этого интерфейса:

public interface IEnumerable<out T> : IEnumerable
{
  new IEnumerator<T> GetEnumerator();
}

* This source code was highlighted with Source Code Highlighter.

Единственный метод GetEnumerator() возвращает перечислитель, интерфейс которого объявлен как:

public interface IEnumerator<out T> : IDisposable, IEnumerator
{
  new T Current { get; }
}

* This source code was highlighted with Source Code Highlighter.

Здесь мы видим свойство Current, т.е. текущий элемент в коллекции. Это generic-определение перечислителя, а есть просто IEnumerator:

public interface IEnumerator
{
  object Current { get; }
  bool MoveNext();
  void Reset();
}

* This source code was highlighted with Source Code Highlighter.

Как видно из определений IEnumerable — это просто фабрика для создания перечислителей (IEnumerator). В свою очередь перечислитель просто поддерживает механизм, с помощью которого можно получить какой-то текущий элемент, перейти к следующему или сбросить результат. Он только должен знать как вычислить следующий элемент или начать процесс заново.
Поэтому существование самой коллекции вовсе не обязательно! Вычисляется текущий элемент в методе MoveNext(), затем он возвращает сигнал о том, что можно еще продолжить процесс или его нужно прекратить.

Перейдем к примерам.

class Term
 {
   public Term(string name, int code)
   {
     Name = name;
     Code = code;
   }

   public readonly int Code;
   public string Name;

   public override string ToString()
   {
     return string.Format("{0} [{1}]", Name, Code);
   }
 }

 class Thrower
 {
   public IEnumerable<Term> ThrowTerms()
   {
     for (int i = 0; i < 10; ++i)
       yield return new Term("Name_" + i, i);
   }
 }

 class Program
 {
   static void Main()
   {
     IEnumerable<Term> terms = new Thrower().ThrowTerms();

     foreach (var term in terms.Where(x => x.Code % 2 == 0))
       term.Name = "Caught";

     foreach (var term in terms)
       Console.WriteLine(term);
   }
 }

* This source code was highlighted with Source Code Highlighter.

Запустите этот код. От него мы ожидаем, что у всех Term'ов с четным кодом имя будет «Caught», соответственно, это мы хотим увидеть на экране. Ан нет! На самом деле на экран будет выведено следующее:

Name_0 [0]
Name_1 [1]
Name_2 [2]
Name_3 [3]
Name_4 [4]
Name_5 [5]
Name_6 [6]
Name_7 [7]
Name_8 [8]
Name_9 [9]

* This source code was highlighted with Source Code Highlighter.

Давайте разбираться почему так получилось. На самом деле никакой коллекции объектов не было создано! IEnumerable terms не содержит в себе никакой коллекции! Сейчас станет понятно почему так получается. Начнем с разбора метода ThrowTerms().

for (int i = 0; i < 10; ++i)
  yield return new Term("Name_" + i, i);

* This source code was highlighted with Source Code Highlighter.

На первый взгляд кажется, что все эти 10 Term'ов будут сложены в какую-то промежуточную коллекцию, а потом одним return'ом она будет возвращена. Но это только на первый взгляд. На самом деле все по-другому! Компилятор создает вложенный в Thrower класс, который реализует интерфейсы IEnumerable и IEnumerator, а в методе ThrowTerms() возвращается новый экземпляр этого класса. А сам класс выглядит примерно так:

class Thower__d0 : IEnumerable<Term>, IEnumerator<Term>
 {
   private readonly int _count;
   private int _index = 0;

   public Thower__d0(int count)
   {
     _count = count;
   }

   public IEnumerator<Term> GetEnumerator()
   {
     return this;
   }

   IEnumerator IEnumerable.GetEnumerator()
   {
     return GetEnumerator();
   }

   public void Dispose()
   {
   }

   public bool MoveNext()
   {
     if (!(_index < _count))
       return false;

     Current = new Term("Name_" + _index, _index);
     ++_index;

     return true;
   }

   public void Reset()
   {
     Current = null;
   }

   public Term Current
   {
     get; private set;
   }

   object IEnumerator.Current
   {
     get { return Current; }
   }
 }

* This source code was highlighted with Source Code Highlighter.

А метод ThrowTerms() преобразуется в:

public IEnumerable<Term> ThrowTerms()
{
 return new Thower__d0(10);
}

* This source code was highlighted with Source Code Highlighter.

Вы можете воспользоваться IL Dasm чтобы посмотреть на скомпилированный код и увидеть все тонкости. Там много интересного :)

Теперь, я думаю, должно стать понятнее почему наши ожидания не совпали с действительностью. Просто на каждой итерации цикла создавался новый экземляр Term'а, который потом просто терялся. Во втором foreach по terms метод ThrowTerms() вызывается второй раз! Получается, что создается новый перечислитель, который просто создает новые экземпляры Term'ов. Это совершенно не заметно, если не знать того, о чем написано в этой статье. И это может иметь неприятные последствия. Например, что было бы если в методе ThrowTerms() было обращение к базе данных или файловой системе? Да-да-да, вместо одного обращения, как мы предполагали, будет два! Очевидно, это может очень навредить производительности, либо привести к неверным результатам!

Ну а как же решить проблему и сделать так, чтобы наши ожидания совпали с реальностью? Достаточно изменить вызов

IEnumerable<Term> terms = new Thrower().ThrowTerms();

* This source code was highlighted with Source Code Highlighter.

на

IEnumerable<Term> terms = new Thrower().ThrowTerms().ToList();

* This source code was highlighted with Source Code Highlighter.

Вызовом ToList() мы инициируем немедленное создание списка, при этом все Term'ы размещаются в массиве внутри List. После этого мы можем обращаться к любому Term'у и что-нибудь с ним делать :)
Запускаем код на выполнение и видим то, что хотели:

Caught [0]
Name_1 [1]
Caught [2]
Name_3 [3]
Caught [4]
Name_5 [5]
Caught [6]
Name_7 [7]
Caught [8]
Name_9 [9]

* This source code was highlighted with Source Code Highlighter.

Спасибо за внимание.
Всем внимательности и удачи!