Kolekce v .NET – 2. yield a iterátory
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
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       29 647×

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 Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Reklama
Reklama
Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

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 © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý