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

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       30 763×

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.

Reklama
Reklama

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 Dovozci baterií mění logistiku, letadlo nahrazuje námořní doprava

Dovozci baterií mění logistiku, letadlo nahrazuje námořní doprava

Dovozci baterií do mobilů či notebooků upouštějí od letecké přepravy zboží. V letošním roce plánují dovézt až 80 % produktů lodí. Přitom před 5 lety byla většina baterií do mobilních přístrojů dovezených do České republiky přepravována letadlem. Za proměnou způsobu transportu akumulátorů stojí zpřísnění pravidel pro leteckou přepravu, která přinášejí vyšší náklady i náročnou agendu.

Reklama
Reklama
Obrázek ke článku JIC otevírá největší digitální dílnu pro veřejnost v České republice

JIC otevírá největší digitální dílnu pro veřejnost v České republice

JIC otevírá první nonstop veřejně dostupnou digitální dílnu světového formátu s vybavením za 3 miliony korun. Dílnu může využívat po registraci kdokoliv. V  prostorách vzniknou prototypy produktů místních startupů, projekty kutilů a studentů i umělecká díla. Cílem dílny je zpřístupnit veřejnosti drahé přístroje a přitáhnout více podnikavých lidí k technickým oborům.

Obrázek ke článku Nový IT hráč na českém trhu

Nový IT hráč na českém trhu

V roce 2015 otevřela v Praze na Pankráci v budově City Tower své kanceláře společnost EPAM Systems (NYSE:EPAM), jejíž centrála se nachází v USA. Společnost byla založená v roce 1993 a od té doby prošla velkým vývojem a stále roste.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý