Бесконечные последовательности в C#
Опубликовано в Статьи | 19-06-2009
Компьютеры – в общей массе своей, штуки дискретные. Поэтому мы не можем сказать – дайте мне последовательность чисел Фибоначчи, и работать с ней, не указав необходимую её длину. Ну, на самом деле мы можем вычислять эту последовательность динамически, при каждой потребности в следующем элементе (пока у нас хватает памяти), создавая иллюзию бесконечности. В языках программирования такие вещи наиболее элегантно проделываются с помощью ленивых вычислений. Ленивые вычисления означают такие вычисления, которые производятся только тогда, когда в них действительно возникает необходимость, а до этого времени они откладываются, как могут.
На самом деле возможность определять такие ленивые последовательности появилась ещё в С# 2.0 при помощи ключевого слова yield. Мы определяем метод, возвращающий IEnumerable или IEnumerator, а внутри него при необходимости генерации нового элемента этой последовательности вызываем yield return.
Например:
Public static IEnumerable<decimal> Fibonacci
{
get
{
decimal pred = 1;
decimal curr = 1;
yield return pred;
yield return curr;
while (true)
{
var next = pred + curr;
yield return next;
pred = curr;
curr = next;
}
}
}
В этом примере каждый новый элемент генерируется при каждом обращении к методу MoveNext() IEnumerator-а данной последовательности. Плюс ко всему, я сделал Fibonacci свойством для красоты. Теперь мы можем сделать следующее:
foreach(var v in Fibonacci)
Console.WriteLine (v);
На экран будет выводиться последовательность Фибоначчи так долго, пока у вас хватит на это памяти, или не произойдёт переполнение decimal. Однако часто нам не нужны все значения бесконечной последовательности, а только первые несколько. Поэтому полезно будет определить следующий метод расширения, уже с использованием фишек C# 3.0. Конечно, данный метод должен содержаться в каком-то статическом классе.
public static IEnumerable<T> Take<T>(this
IEnumerable<T> e, int n)
{
var r = e.GetEnumerator();
for (int i = 0; i < n; i++)
{
r.MoveNext();
yield return r.Current;
}
}
И теперь мы можем работать так:
foreach(var k in Fibonacci.Take(10))
Console.WriteLine(k);
А применяя расширяющие методы из System.Linq.Enumerable, мы можем применять к нашей бесконечной последовательности различные трансформации и ограничения, перед её использованием, например, для вывода только чётных элементов последовательности Фибоначчи можно проделать следующее:
var fib = Fibonacci.Where(x => x % 2 == 0); // бесконечная из чётных чисел Фибоначчи
foreach(var k in fib.Take(10))
Console.WriteLine(k);
Конечно, всё вышеперечисленное можно было реализовать и по-другому, но в контексте нововведений C# 3.0 конкретно данная реализация может показаться более естественной.
Исходный текст примера (с добавленной последовательностью факториалов) можно загрузить .