V minulém dílu seriálu jsem se dozvěděli, že i ty úplně nejjednodušší kolekce musí implementovat rozhraní IEnumerable
Než začneme, připomeňme si, jak vypadá rozhraní IEnumerable<T>:
public interface IEnumerable<out T> : IEnumerable
{
IEnumerator<T> GetEnumerator();
}
V principu existují dva způsoby, jak vytvořit toto rozhraní, a to buďto použitím klíčového slova yield, nebo jeho implementací s pomocí iterátorů.
Iterátory a enumerátory
Návrhový vzor Iterator
Iterator je návrhový vzor, který stručně řečeno umožňuje procházet datovou strukturu bez znalosti její implementace. Jedná se o velmi rozšířený návrhový vzor, jehož nativní podporu najdeme ve většině vyšších programovacích jazyků.
Iterátory v zásadě můžeme rozdělit podle jejich funkcionality např. na tyto typy:
- Dopředné (forward) umožňují průchod kolekcí od začátku na konec.
- Zpětné (backward) procházející kolekci od konce.
- Obousměrné (bidirectional), které jsou schopny procházet kolekci v obou směrech.
- Cyklické/nekonečné iterují buďto dokud není splněna nějaká vnější podmínka, nebo dokud kolekce není prázdná a nebo se nikdy nezastaví.
Dopředný iterátor - IEnumerator
Rozhraní IEnumerator (viz obr. 1) v .NETu zastupuje dopředný iterátor, který je zde většinou označován jako enumerátor.
Jak můžete vidět, tak i u enumerátorů můžeme nalézt generickou a negenerickou verzi rozhraní, obě však obsahují tyto prvky:
- Current - vrací aktuální prvek kolekce.
- MoveNext() - změní Current na následující prvek. Pokud je po zavolání MoveNext dosažen konec kolekce, tj. nemá již cenu dále volat MoveNext, je vráceno True, v opačném případě False.
- Reset() - obnoví výchozí nastavení iterátoru.
Generická verze ještě navíc implementuje IDisposable.
Příklad: iterátor pro výčtové typy
Iterátor je zcela obecný návrhový vzor a nemusí být použit pouze u kolekcí. Následující příklad ukazuje implementaci iterátoru pro výčtové typy enum:
public class EnumIterator<T> : IEnumerator<EnumIterationItem<T>> where T : struct
{
private readonly T[] _enumMembers; // pole s jednotlivymi cleny enumu
private int _currentIndex; // aktualni index pri pruchodu polem
public EnumIterator()
{
// naplnime interni pole cleny enumu
_enumMembers = (T[])Enum.GetValues(typeof(T));
}
public bool MoveNext()
{
if (_currentIndex < _enumMembers.Length - 1)
{
_currentIndex++; // zvetsime index pro pristup k _enumMembers
return true;
}
return false;
}
public EnumIterationItem<T> Current
{
get { return new EnumIterationItem<T>(_enumMembers[_currentIndex]); }
}
object System.Collections.IEnumerator.Current { get { return Current; } }
public void Reset() { _currentIndex = 0; }
public void Dispose() {}
}
Návratový datový typ EnumIterationItem<T> může vypadat např. následovně:
public class EnumIterationItem<T> where T : struct
{
public T Value { get; private set; }
public int UnderlayingValue { get { return Convert.ToInt32(Value); } } public string Name { get { return Enum.GetName(typeof(T), Value); } }
public EnumIterationItem(T item)
{
Value = item;
}
}
Snadno již pak implementujeme kolekci pro výčtové typy:
public class EnumList<T> : IEnumerable<EnumIterationItem<T>> where T : struct
{
public IEnumerator<EnumIterationItem<T>> GetEnumerator()
{
return new EnumIterator<T>();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return new EnumIterator<T>();
}
}
Ostatní iterátory
Jiné než dopředné iterátory nacházejí uplatnění jen výjimečně, avšak i přesto můžeme nalézt situace, kdy mohou být užitečné.
Zpětné a obousměrné iterátory
Nejméně často můžeme v .NETu narazit na situaci, kdy využijeme zpětný iterátor. .NET totiž obsahuje extension metodu Reverse vracející kolekci v opačném pořadí. Jedním z mála míst, kde by implementace zpětného nebo obousměrného iterátoru mohla dávat smysl, jsou vázané seznamy (viz další díly seriálu).
Cyklický iterátor
Cyklické iterátory se mohou hodit například v okamžiku, když ve vlákně s nízkou prioritou potřebujeme neustále procházet jednotlivé prvky a aktualizovat je. Můžeme tak např. aktualizovat či mazat hodnoty v cache.
Klíčové slovo yield a lazy evaluation
Syntaxe
Klíčové slovo yield slouží k vrácení objektu typu IEnumerable
public IEnumerable<string> GetStrings()
{
yield return "první prvek";
yield return "druhý prvek";
yield return "třetí prvek";
yield return "...";
}
public IEnumerable<int> GetNumbers()
{
for (int i = 0; i < 10; i++)
yield return i;
}
Vedle yield return existuje ještě yield break ukončující vracení prvků:
public IEnumerable<int> GetSomeNumbers()
{
for (int i = 0; i < 1000; i++)
{
if(i > 250) // Zde muze byt libovolna ukoncovaci podminka.
yield break; // Prerusi vraceni prvku a cela metoda je ukoncena.
yield return i;
}
}
Proč yield používat? Co je to lazy evaluation?
public static IEnumerable<int> GetIEnumerable()
{
for (int i = 0; i < 5000000; i++)
yield return i;
}
public static IEnumerable<int> GetList()
{
var list = new List<int>(5000000);
for (int i = 0; i < 5000000; i++) list.Add(i);
return list;
}
static void Main(string[] args)
{
var watch = new Stopwatch(); // Stopky na mereni casu
// STOPNEME CAS PRO yield return
watch.Start();
foreach (var item in GetIEnumerable()) { }
watch.Stop();
Console.WriteLine("Pouziti yield: {0}", watch.ElapsedTicks);
watch.Reset();
// STOPNEME CAS PRO List
watch.Start();
foreach (var item in GetList()) { }
watch.Stop();
Console.WriteLine("Pouziti Listu: {0}", watch.ElapsedTicks);
Console.Read();
}
Spuštěním tohoto jednoduchého programu zjistíme, že yield oproti Listu zabere zhruba polovinu času. Proč je tomu tak? Yield return totiž nevrací všechny prvky najednou jako List, ale jeden po druhém. V okamžiku, kdy potřebujeme jeho první prvek, tak ho dostaneme. Rozdíl je ale v tom, že dostaneme jen a pouze první prvek a ne celou kolekci, jak by tomu bylo v případě Listu. Proto je při použití yield return vykonán pouze jeden cyklus foreach, zatímco u Listu jsou provedeny smyčky dvě - naplnění a průchod. Takováto vlastnost je označována jako lazy-evaluation nebo hezky česky líné vyhodnocování.
Další malou výhodou je nižší paměťová náročnost yield return. List oproti kolekci vracené yield returnem obsahuje celou řadu interních proměnných a property, které často ani nejsou potřeba.
Lazy evaluation a nekonečné smyčky
Zajímavostí je, že líné vyhodnocování nám v kódu umožňuje použít nekonečné smyčky jako while(true), aniž by se aplikace zacyklila:
public static IEnumerable GetNaturalNumbers()
{
int i = 0;
while(true) yield return ++i;
}
Finta je v tom, že ukončovací podmínku cyklu nemusíme definovat do metody GetNaturalNumbers, ale k jejímu použití. To se nám může hodit zejména v případech, kdy nevíme, kolik prvků kolekce budeme potřebovat, viz následující příklad:
// Nalezne cislo, ktere kdyz podelime jeho cifernym souctem, tak dostaneme 12.
int vysledek = 0;
foreach (int cislo in GetNaturalNumbers())
{
// VYPOCTEME CIFERNY SOUCET
int cifernySoucet = 0;
foreach (char znak in cislo.ToString())
cifernySoucet += int.Parse(znak.ToString()); // Otazka pro ctenare: Proc zde nemuzeme pozit Convert?
// KONTROLA ZBYTKU PO DELENI CIF. SOUCTEM
if (cislo % cifernySoucet == 12)
{
vysledek = cislo;
break;
}
}
Jak lazy evaluation funguje?
Kompilátor neumožňuje vracet čistě rozhraní, vždy za ním musí stát nějaká konkrétní třída, proto na pozadí vygeneruje třídu implementující IEnumerable a také její iterátor.
Následující kód:
public static IEnumerable<T> necoUdelej()
{
for(int i = 0; i < 10; i++)
yield return nejakaFunkce();
}
je kompilátorem přeložen přibližně na toto:
[CompilerGenerated]
public sealed class VygenerovanaTrida : IEnumerable<T>
{
public IEnumerator<T> GetEnumerator()
{
return new VygenerovanyEnumerator();
}
}
[CompilerGenerated]
public sealed class VygenerovanyEnumerator
{
private bool MoveNext()
{
switch (this.state)
{
case 0:
this.state = -1;
this.i = 0;
while (this.i < 10)
{
this.current = nejakaFunkce();
this.state = 1;
return true;
Label_00BC:
this.state = -1;
this.i++;public static IEnumerable<T> necoUdelej()
{
return new VygenerovanaTrida();
}
Jak je vidět, tak vešekerá logika byla přesunuta do iterátoru a cyklus for byl přeložen na while. Možná vás překvapí, že vygenerovaný kód obsahuje příkaz goto. Goto je zcela oprávněně jedním z nejhorších zvěrstev, jakých se v kódu můžete dopustit. .NET kompiler ho však používá běžně. I dvojice příkazů switch-case je kompilátorem přeložena na goto. Více o tom, jak .NET a IL pracuje s yield najdete na csharp-online.net [ http://en.csharp-online.net/CSharp_Coding_Solutions%E2%80%94What_Does_Yield_Keyword_Generate ]
Závěr
V dnešním díle jsme si ukázali nejzákladnější prostředky k tvorbě a práci s kolekcemi. V příštím díle se již konečně zaměříme na konkrétní datové struktury. Tématem budou pole a seznamy. Ukážeme si, co nám .NET v této oblasti nabízí, co jsou to vázané seznamy a skip list. Naprogramujeme si také kolekci, která .NETu chybí.
Zdroje:
- http://en.csharp-online.net/CSharp_Coding_Solutions%E2%80%94What_Does_Yield_Keyword_Generate [ http://en.csharp-online.net/CSharp_Coding_Solutions%E2%80%94What_Does_Yield_Keyword_Generate ]
- http://cs.wikipedia.org/wiki/Iterator [ http://en.wikipedia.org/wiki/Circular_buffer ]
- Trey Nash: C# 2010, CPress, 2010