Díky nutnosti lehce nadprůměrného pracovní nasazení v posledních pár týdnech jsem si našel chvilku (přesněji dvě nebo tři) na napsání dalšího příspěvku až nyní.
Mějme například tento enumerátor:
static IEnumerable<TResult> Generate<TSeed, TResult>(TSeed seed, Func<TSeed, TResult> next)
{
while (true)
{
yield return next(seed);
}
}
static void Main()
{
var randomNumbers = Generate(new Random(), rnd => rnd.Next(100)).Take(20);
Console.WriteLine("1)");
foreach (int i in randomNumbers)
{
Console.Write(i + " ");
}
Console.WriteLine();
Console.WriteLine("2)");
foreach (int i in randomNumbers)
{
Console.Write(i + " ");
}
}
Výstup:
1)
29 75 61 55 16 65 4 59 65 95 11 16 97 72 30 93 74 66 2 54
2)
85 2 79 29 82 67 71 64 51 86 88 37 51 54 89 70 83 99 24 83
Je vidět, že při opakovaném procházení enumerátoru jsou výsledky různé. Řeknete si, no to je přeci normální, protože náš enumerátor je vyhodnocován až při jeho procházení (deferred execution) (*) a funkce použitá pro generování jednotlivých prvků vrátí pokaždé jinou náhodnou hodnotu. Dobře.
Ve funkcionálním programování se tento jev obecně označuje jako side effect a funkce
rnd => rnd.Next(100) není tzv. pure funkce nebo side effect free funkce. Otázkou je, jak lze zabránit nechtěné “replikaci side effectu” (což je to k čemu zde dochází).
Nejjednodušší je to udělat asi takto:
static void Main()
{
var randomNumbers = Generate(new Random(), rnd => rnd.Next(100)).Take(20).ToList();
Console.WriteLine("1)");
foreach (int i in randomNumbers)
{
Console.Write(i + " ");
}
Console.WriteLine();
Console.WriteLine("2)");
foreach (int i in randomNumbers)
{
Console.Write(i + " ");
}
}
Výstup:
1)
45 97 59 10 45 25 59 18 31 96 73 98 33 80 14 88 42 82 26 51
2)
45 97 59 10 45 25 59 18 31 96 73 98 33 80 14 88 42 82 26 51
Nyní jsme si pomoci LINQ operátoru ToList() vynutili okamžité vyhodnocení enumerátoru (eager evaluation) a pak již jen dvakrát procházíme stejný výsledek uložený v paměti, stále asi nic nového, takto by to udělala většina z nás.
Toto řešení má ale obecně dva problémy:
- Pro vytvoření výsledku se musí nejprve projít celá zdrojová sekvence a ta je pak také celá uložená v paměti, což nefunguje např. na nekonečné sekvence (všimněte si, že operátor Take() musí být aplikován nejdříve, jinak by výše uvedený kód nikdy nedoběhl, protože naše sekvence čistě náhodou nekonečná je).
- Vytvoření a uložení výsledků do paměti je provedeno ihned tj. tato činnost nyní není oddálena až do posledního možného místa ve zpracování.
Naštěstí to ale jde udělat i jinak:
static void Main()
{
var randomNumbers = Generate(new Random(), rnd => rnd.Next(100)).MemoizeAll().Take(20);
Console.WriteLine("1)");
foreach (int i in randomNumbers)
{
Console.Write(i + " ");
}
Console.WriteLine();
Console.WriteLine("2)");
foreach (int i in randomNumbers)
{
Console.Write(i + " ");
}
}
Výstup:
1)
19 18 72 27 75 32 51 2 10 42 5 48 78 15 60 52 25 79 52 84
2)
19 18 72 27 75 32 51 2 10 42 5 48 78 15 60 52 25 79 52 84
Nyní jsme použili operátor jiný a sice konkrétně operátor MemoizeAll(). Tento operátor je vypůjčený z knihovny Reactive Extensions for .NET (Rx) konkrétně z assembly System.Interactive.dll což je rozšíření množiny standardních LINQ operátoru (LINQ Standard Query Operators) pro interface IEnumerable<T> o některé další v některých případech docela užitečné operátory. (Pokud by jste ale nechtěli do svého projektu tuto assembly přidávat z důvodu např. nutnosti její distribuce, je níže uvedená i vlastní implementace tohoto operátoru.)
A co přesně tahle věc dělá? Co tahle věc dělá je to, že umožňuje procházet původní zdrojovou sekvenci, ale během načítaní jednotlivých prvků a jejich posílání na výstup zároveň ještě tak jak jdou jednotlivé prvky postupně za sebou sestavuje list. Nejedná se zde ale o obyčejný list nýbrž o “spoják” (linked list). Když se nad tím zamyslíte, zjistíte, že tento způsob není až tak složitý a je přitom velmi efektivní. Tím je totiž zajištěno nejen to, že když danou sekvenci začne současně (**) procházet kdokoliv další dostává již prvky uložené v tomto listu (z cache), ale zároveň může kdykoliv “převzít” úkol načítaní zdrojové sekvence a prodlužování budovaného listu v případě, že všechny ostatní v procházení sekvence předežene (graficky je to znázorněno na tomto diagramu).
Operátor MemoizeAll() tedy na rozdíl od operátoru ToList() netrpí nepříjemnostmi uvedenými u řešení předchozího a nejčastěji ho právě použijeme v případech, kdy by nám vadila přílišná “eagerness” operátorů jako je ToList(). A tentokrát si všimněte, že v našem příkladu bylo možné tento operátor i předřadit před operátor Take().
A popravdě řečeno vlastní implementace tohoto operátoru není až tak složitá, jak by se možná na první pohled mohlo zdát:
using System;
using System.Collections.Generic;
namespace System.Linq
{
internal static class MemoizeAllEnumerableEx
{
#region member types definition
private sealed class MemoizeAllEnumerable<T> : IEnumerable<T>, System.Collections.IEnumerable
{
#region member types definition
private sealed class LinkedList
{
#region member varible and default property initialization
public T Current { get; private set; }
private IEnumerator<T> m_enumerator;
private readonly object m_gate;
private LinkedList m_next;
#endregion
#region constructors and destructors
private LinkedList(IEnumerator<T> enumerator, T current, object gate)
{
this.Current = current;
m_enumerator = enumerator;
m_gate = gate;
}
#endregion
#region action methods
public static LinkedList Create(IEnumerator<T> enumerator, object gate)
{
lock (gate)
{
if (!enumerator.MoveNext())
{
enumerator.Dispose();
return null;
}
return new LinkedList(enumerator, enumerator.Current, gate);
}
}
#endregion
#region property getters/setters
public LinkedList Next
{
get
{
if (m_enumerator != null)
{
lock (m_gate)
{
if (m_enumerator != null)
{
m_next = LinkedList.Create(m_enumerator, m_gate);
m_enumerator = null;
}
}
}
return m_next;
}
}
#endregion
}
#endregion
#region member varible and default property initialization
private readonly object m_gate = new object();
private LinkedList m_list;
private IEnumerable<T> m_source;
#endregion
#region constructors and destructors
public MemoizeAllEnumerable(IEnumerable<T> source)
{
m_source = source;
}
#endregion
#region action methods
public IEnumerator<T> GetEnumerator()
{
if (m_source != null)
{
lock (m_gate)
{
if (m_source != null)
{
m_list = LinkedList.Create(m_source.GetEnumerator(), m_gate);
m_source = null;
}
}
}
LinkedList item = m_list;
while (item != null)
{
yield return item.Current;
item = item.Next;
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
}
#endregion
#region action methods
public static IEnumerable<TSource> MemoizeAll<TSource>(this IEnumerable<TSource> source)
{
if (source == null)
{
throw new ArgumentNullException("source");
}
return new MemoizeAllEnumerable<TSource>(source);
}
#endregion
}
}
Ještě nutno říct, že tento operátor není jediný, ale existují i další jeho varianty, jako operátor Memoize(), u kterého lze specifikovat velikost bufferu. Podrobněji se o těchto dalších operátorech můžete dozvědět v tomto článku.
BTW: Toto je úplně mimo vlastní téma, ale doufám, že všichni ví, jakou závažnou chybu by způsobili, kdyby byl enumerátor z první verze příkladu napsán například takto (díky této chybě bude i generován jiný výstup):
(Update: Chyba je samozřejmě v tom, že se nyní vytváří pro každé volání GetEnumerator() nová instance třídy Random, která bude inicializována stejnou výchozí hodnotou seed.)
static IEnumerable<TResult> Generate<TSeed, TResult>(Func<TSeed> seedFactory, Func<TSeed, TResult> next)
{
TSeed seed = seedFactory();
while (true)
{
yield return next(seed);
}
}
static void Main()
{
var randomNumbers = Generate(() => new Random(), rnd => rnd.Next(100)).Take(20);
//Všechno ostatní stejně jako předtím
}
(*) Tento typ enumerátoru se někdy také označuje jako tzv. “cold”
IEnumerable<T>. Podobný případ je i kdybychom konstruovali nějaké objekty LINQ dotazem, také při každé enumeraci budeme dostávat nové instance těchto objektů. Opakem je “hot”
IEnumerable<T>, které by při každém procházení vracelo prvky stejné (tj. i např. stejné instance objektů) jako třeba pole, list apod. Také je dobré si uvědomit, že to, zda je nějaký enumerátor “hot” nebo “cold” nemusíme pouze
ze samotné deklarace typu vůbec poznat (v obou případech se může jednat pouze o
IEnumerable<T>).
(**) Zde se nejedná pouze o multi-threadingové scénáře (i když ty jsou samozřejmě podporovány také), ale protože enumerátor má obecně kontrolu (tj. běží kód enumerátoru) pouze během volání metody
MoveNext(), zrovna tak připadá v úvahu současný přístup k enumerátoru i ve scénářích, které jsou pouze
single-threadingové.