Algol
02.01.2010, 15:13
Начиная с версии 2.0 C# поддерживает итераторы. В этой мини-статье рассмотрим зачем они нужны, и каким образом они могут облегчить нам жизнь и повысить производительность приложений.
Фактически, итераторы были и в первой версии сишарпа (IEnumerator), но они были несколько неудобны в использовании, излишне запутывали код. В версии 2.0 появился оператор yield, который кардинально облегчил написание итераторов.
Рассмотрим простейшую задачу, и два примера ее решения - с итераторами и без.
Пусть нам нужно создать класс, которых хранит список целых чисел. При этом, в классе должен быть метод GetBigNumbers(int min) который возвращает числа из хранимого списка, большие чем min.
Рассмотрим самую реализацию без использования итераторов:
public class SeparableList1
{
List<int> items = new List<int>();
public void Add(int v)
{
items.Add(v);
}
/// получение элементов, больших чем min
public List<int> GetBigNumbers(int min)
{
List<int> result = new List<int>();
foreach (int v in items)
if (v > min)
result.Add(v);
return result;
}
}
В этом классе есть метод GetBigNumbers(), который перебирает элементы исходного списка, проверяет условие, и если оно выполняется - заносит элемент в выходной список.
Такая реализация - типична, но имеет несколько недостатков.
Недостаток первый: Расход памяти. Внутри метода создается новый объект - List<int>, который заполняется копиями исходных чисел. При этом тратится время на создание объекта и расходуется память на хранение копий элементов исходного списка.
Недостаток второй: Вычислительная избыточность. Метод возвращает все элементы большие некоторого числа. Однако, если вызывающая программа использует не все из этих чисел (например, ей нужно получить только первое из больших чисел), то все остальные элементы - просто будут посчитаны впустую.
Теперь посмотрим на реализацию класса, но с использованием итераторов:
public class SeparableList2
{
List<int> items = new List<int>();
public void Add(int v)
{
items.Add(v);
}
/// получение элементов, больших чем min
public IEnumerable<int> GetBigNumbers(int min)
{
foreach (int v in items)
if (v > min)
yield return v;
}
}
Здесь в реализации метода GetBigNumbers() применен оператор yield, а сам метод возвращает объект типа IEnumerable<int>. Посмотрим как это работает. Пусть вызывающая программа содержит такой код
foreach (int big in separableList.GetBigNumbers(10))
Console.WriteLine(big);
Как видим, метод GetBigNumbers вызывается внутри оператора foreach. При первом вызове, метод перебирает элементы своего списка, находит число большее 10, и возвращает управление в вызывающую программу, с помощью оператора yield return. Найденное число big выводится в консоль. Далее снова вызывается метод GetBigNumbers, для получения следующего числа. Однако он начинает выполнятся не с начала , а с той точки, где он был прерван оператором yield return. Таким образом вызывающий цикл получает все элементы исходного списка, большие 10. Когда метод GetBigNumbers больше не находит чисел, он завершается (не через yield, а просто подходит к точке выхода), а вызывающий foreach при этом прерывает цикл.
Несмотря на некторую запутанность последовательности выполняемых операторов, такая конструкция имеет несколько преимуществ, по сравнению с первой версией класса SeparableList1:
Преимущество первое: Экономия памяти. Метод GetBigNumbers не создает новых списков, он просто возвращает элементы исходного списка, подходящих под некторое условие. Фактически это означает что метод вообще не расходует память.
Преимущество второе: Ленивые вычисления. Заметим, что в первой версии класса, все элементы генерировались заранее, а лишь потом выводились бы в консоль. В версии с итератором - числа ищутся по мере необходимости. Когда вызывающий foreach требует слудующий элемент, метод GetBigNumbers его находит и возвращает. Но если вдруг вызывающий цикл прервется (например оператором break), то GetBigNumbers не будет искать следующие числа, таким образом не делая лишних вычислений.
Итак: итераторы снижают расход памяти, и благодаря ленивым вычислениям, могут существенно повысить производительность приложения. Кроме того, методы с yield обычно оказываются немного компактнее, чем без него.
Теперь немного дегтя в бочку с медом:
Казалось бы итераторы всегда должны повышать быстродействие. Однако, на практике это не так. Во-первых, yield это оператор из разряда "compiler magic". На более низком уровне, этот оператор компилируется в довольно громоздкий класс, реализующий интерфейс IEnumerable, со всеми методами, необходимыми для этого интерфейса. И по быстродействию этот итератор обычно проигрывает итераторам для обычного List<int>. Во-вторых фреймворк довольно быстро создает списки, и расходы времени на их создание могут быть меньше чем на работу ленивого итератора. Так или иначе, но итераторы повышают производительность только если у нас большие объемы данных, либо вызывающая программа использует не все затребованные данные, и срабатывает эффект "ленивых вычислений".
Фактически, итераторы были и в первой версии сишарпа (IEnumerator), но они были несколько неудобны в использовании, излишне запутывали код. В версии 2.0 появился оператор yield, который кардинально облегчил написание итераторов.
Рассмотрим простейшую задачу, и два примера ее решения - с итераторами и без.
Пусть нам нужно создать класс, которых хранит список целых чисел. При этом, в классе должен быть метод GetBigNumbers(int min) который возвращает числа из хранимого списка, большие чем min.
Рассмотрим самую реализацию без использования итераторов:
public class SeparableList1
{
List<int> items = new List<int>();
public void Add(int v)
{
items.Add(v);
}
/// получение элементов, больших чем min
public List<int> GetBigNumbers(int min)
{
List<int> result = new List<int>();
foreach (int v in items)
if (v > min)
result.Add(v);
return result;
}
}
В этом классе есть метод GetBigNumbers(), который перебирает элементы исходного списка, проверяет условие, и если оно выполняется - заносит элемент в выходной список.
Такая реализация - типична, но имеет несколько недостатков.
Недостаток первый: Расход памяти. Внутри метода создается новый объект - List<int>, который заполняется копиями исходных чисел. При этом тратится время на создание объекта и расходуется память на хранение копий элементов исходного списка.
Недостаток второй: Вычислительная избыточность. Метод возвращает все элементы большие некоторого числа. Однако, если вызывающая программа использует не все из этих чисел (например, ей нужно получить только первое из больших чисел), то все остальные элементы - просто будут посчитаны впустую.
Теперь посмотрим на реализацию класса, но с использованием итераторов:
public class SeparableList2
{
List<int> items = new List<int>();
public void Add(int v)
{
items.Add(v);
}
/// получение элементов, больших чем min
public IEnumerable<int> GetBigNumbers(int min)
{
foreach (int v in items)
if (v > min)
yield return v;
}
}
Здесь в реализации метода GetBigNumbers() применен оператор yield, а сам метод возвращает объект типа IEnumerable<int>. Посмотрим как это работает. Пусть вызывающая программа содержит такой код
foreach (int big in separableList.GetBigNumbers(10))
Console.WriteLine(big);
Как видим, метод GetBigNumbers вызывается внутри оператора foreach. При первом вызове, метод перебирает элементы своего списка, находит число большее 10, и возвращает управление в вызывающую программу, с помощью оператора yield return. Найденное число big выводится в консоль. Далее снова вызывается метод GetBigNumbers, для получения следующего числа. Однако он начинает выполнятся не с начала , а с той точки, где он был прерван оператором yield return. Таким образом вызывающий цикл получает все элементы исходного списка, большие 10. Когда метод GetBigNumbers больше не находит чисел, он завершается (не через yield, а просто подходит к точке выхода), а вызывающий foreach при этом прерывает цикл.
Несмотря на некторую запутанность последовательности выполняемых операторов, такая конструкция имеет несколько преимуществ, по сравнению с первой версией класса SeparableList1:
Преимущество первое: Экономия памяти. Метод GetBigNumbers не создает новых списков, он просто возвращает элементы исходного списка, подходящих под некторое условие. Фактически это означает что метод вообще не расходует память.
Преимущество второе: Ленивые вычисления. Заметим, что в первой версии класса, все элементы генерировались заранее, а лишь потом выводились бы в консоль. В версии с итератором - числа ищутся по мере необходимости. Когда вызывающий foreach требует слудующий элемент, метод GetBigNumbers его находит и возвращает. Но если вдруг вызывающий цикл прервется (например оператором break), то GetBigNumbers не будет искать следующие числа, таким образом не делая лишних вычислений.
Итак: итераторы снижают расход памяти, и благодаря ленивым вычислениям, могут существенно повысить производительность приложения. Кроме того, методы с yield обычно оказываются немного компактнее, чем без него.
Теперь немного дегтя в бочку с медом:
Казалось бы итераторы всегда должны повышать быстродействие. Однако, на практике это не так. Во-первых, yield это оператор из разряда "compiler magic". На более низком уровне, этот оператор компилируется в довольно громоздкий класс, реализующий интерфейс IEnumerable, со всеми методами, необходимыми для этого интерфейса. И по быстродействию этот итератор обычно проигрывает итераторам для обычного List<int>. Во-вторых фреймворк довольно быстро создает списки, и расходы времени на их создание могут быть меньше чем на работу ленивого итератора. Так или иначе, но итераторы повышают производительность только если у нас большие объемы данных, либо вызывающая программа использует не все затребованные данные, и срабатывает эффект "ленивых вычислений".