Kolekce v .NET – 2. yield a iterátory
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Kolekce v .NET –  2. yield a iterátoryKolekce v .NET – 2. yield a iterátory

 

Kolekce v .NET – 2. yield a iterátory

Google       Google       21. 1. 2013       43 561×

V minulém dílu seriálu jsem se dozvěděli, že i ty úplně nejjednodušší kolekce musí implementovat rozhraní IEnumerableA právě toto rozhraní bude stát v centru dění dnešního dílu. Ukážeme si jeho implementaci pomocí návrhového vzoru Iterator a klíčového slova yield. Řekneme si, co je to lazy evaluation a na základě jakých mechanismů v .NETu funguje.

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.

Obr. 1: Generické a negenerické rozhraní IEnumerator

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. Má v podstatě dva způsoby použití, které si demonstrujeme na metodách GetStrings a GetNumbers:

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?

Nasnadě je otázka: Jaké jsou výhody použití klíčového slova yield a rozhraní IEnumerable oproti třeba obyčejnému Listu? Odpověď nám poskytne následující testovací aplikace:

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++;            
                 }
                 break;

              case 1:
                 goto Label_00BC;
            }
         return false;
     }
    ...
}

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

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:

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

2 názory  —  2 nové  
Hlasování bylo ukončeno    
13 hlasů
Google
(fotka) Zdeněk VaisZdeněk pracuje jako programátor a .NET trainer. Ve volných chvílích se zabývá fyzikou, sportuje a chová kachny.
Web    

Nové články

Obrázek ke článku Stavebnice umělé inteligence 1

Stavebnice umělé inteligence 1

Článek popisuje první část stavebnice umělé inteligence. Obsahuje lineární a plošnou optimalizaci.  Demo verzi je možné použít pro výuku i zájmovou činnost. Profesionální verze je určena pro vývojáře, kteří chtějí integrovat popsané moduly do svých systémů.

Obrázek ke článku Hybridní inteligentní systémy 2

Hybridní inteligentní systémy 2

V technické praxi využíváme často kombinaci různých disciplín umělé inteligence a klasických výpočtů. Takovým systémům říkáme hybridní systémy. V tomto článku se zmíním o určitém typu hybridního systému, který je užitečný ve velmi složitých výrobních procesech.

Obrázek ke článku Jak vést kvalitně tým v IT oboru: Naprogramujte si ty správné manažerské kvality

Jak vést kvalitně tým v IT oboru: Naprogramujte si ty správné manažerské kvality

Vedení týmu v oboru informačních technologií se nijak zvlášť neliší od jiných oborů. Přesto však IT manažeři čelí výzvě v podobě velmi rychlého rozvoje a tím i rostoucími nároky na své lidi. Udržet pozornost, motivaci a efektivitu týmu vyžaduje opravdu pevné manažerské základy a zároveň otevřenost a flexibilitu pro stále nové výzvy.

Obrázek ke článku Síla týmů se na home office může vytrácet. Odborníci radí, jak z pracovních omezení vytěžit maximum

Síla týmů se na home office může vytrácet. Odborníci radí, jak z pracovních omezení vytěžit maximum

Za poslední rok se podoba práce zaměstnanců změnila k nepoznání. Především plošné zavedení home office, které mělo být zpočátku jen dočasným opatřením, je pro mnohé už více než rok každodenní realitou. Co ale dělat, když se při práci z domova ztrácí motivace, zaměstnanci přestávají komunikovat a dříve fungující tým se rozpadá na skupinu solitérů? Odborníci na personalistiku dali dohromady několik rad, jak udržet tým v chodu, i když pracovní podmínky nejsou ideální.

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý