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       31 778×

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 DistrCut – optimalizace pomocí distribuované inteligence

DistrCut – optimalizace pomocí distribuované inteligence

Optimalizační systémy, které jsem dosud popisoval, se týkaly vždy optimalizace na jednom zařízení. Optimalizovalo se dělení tyčového materiálu na jedné pile, vypalování plošného materiálu na jednom plazmovém stroji, řídilo se tavení na jedné elektrické obloukové peci.

Ve výrobním procesu je však často nutné optimalizovat činnost celého výrobního úseku, kde je více různých objektů odlišného typu a koordinovat činnost těchto objektů k dosažení společného cíle, zpravidla kvality finálního výrobku. Řešení tohoto problému umožňuje distribuovaná inteligence.

Reklama
Reklama

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ý