Diskuze: foreach vs for

Naučíme tě pracovat na home-office.

Zjistit více...

Aktivity

roks

Člen

roks:22.5.2014 21:05

Zdravím, chcem sa spýtať, čo je lepšie (respektíve rýchlejšie) na prácu s kolekciou, či cyklus for (int i = 0; i < mojList.Count; i++) alebo foreach (var prvok in mojList) ... keď zoberieme za úvahu, že chcem aby cyklus for integroval +1??

Odpovědět

22.5.2014 21:05

Michal Žůrek - misaz

Tvůrce

Michal Žůrek - misaz:22.5.2014 21:07

si to otestuj. Naplň si kolekci milionem hodnot, všechny projdi v cyklu a něco s nimi udělej (přičti jejich hodnotu k nějaké jiné), změř jak dlouho to bude trvat u for each a for.

Nahoru Odpovědět

22.5.2014 21:07

roks

Člen

roks:22.5.2014 21:11

Dobrý nápad, vďaka

Nahoru Odpovědět

22.5.2014 21:11

roks

Člen

roks:22.5.2014 21:28

Ak by to niekoho náhodou zaujímalo, spravil som si pokus so stopkami, ktoré sa zapli pri kliknutí na tlačítko a vypli pri dokončení cyklu. Kolekcia obsahovala 100 000 000 prvkov(int) a čas dosiahnutý pre prechádzaní kolekcie pomocou foreach bol 0,613 sekundy, pričom cyklus for bol pomalší a trvalo mu to 0,906 sekundy

Nahoru Odpovědět

22.5.2014 21:28

coells

Tvůrce

coells:22.5.2014 21:51

Tím pádem projdeš 100 000 prvků za milisekundu a nemusíš vůbec řešit, co je rychlejší.

Dále pokud si procházení for-cyklem lehce upravíš, bude stejně rychlé, jako enumerace:
for (int i = 0, ic = mojList.Count; i < ic; i++)

A navíc pokud se přepneš z debug módu do release módu, bude for-cyklus dle očekávání 2-3x rychlejší než enumerace.

Editováno 22.5.2014 21:52

Nahoru Odpovědět

22.5.2014 21:51

Jan Vargovský

Tvůrce

Jan Vargovský:22.5.2014 22:15

Někde jsem slyšel, že cyklus, kde se dekrementuje je rychlejší, než cyklus, kde se inkrementuje - je na tom něco pravdy? Že by cpu dekrementoval rychleji?

Nahoru Odpovědět

22.5.2014 22:15

coells

Tvůrce

coells:22.5.2014 22:36

Pokud bys chtěl dřít procesor až na kost, pak je několik faktorů, které určují rychlost provádění.
Řekněme, že si napíšu tři for-cykly, které prochází pole intů.

int[] pole = new int[1000000];
int n = pole.Length;

a) for (int i = 0; i < n; i++) { pole[i] ... }
b) for (int i = 0; i < n; ++i) { pole[i] ... }
c) for (int i = n - 1; i >= 0; i--) { pole[i] ... }

Příklad (a) je typický, jak bys to napsal a použijeme ho jako referenční.

Příklad (b) používá prefixový operátor místo postfixového. ++i je obvykle rychlejší než i++, protože z hlediska instrukční sady lze lépe optimalizovat pořadí a počet instrukcí. Ale stejně se to bude lišit podle toho, jestli bude i mapované do registru nebo ne. Rozdíl proti (a) bude minimální.

Příklad (c) se liší v podmínce. Porovnávání na 0 je rychlejší, než porovnání s nenulovou hodnotou. Rozdíl proti (a) jenom z hlediska podmínky bude také minimální. Tohle byl ten důvod, proč jsi slyšel, že cyklus přes dekrement je rychlejší

Opravdový rozdíl v rychlostech přijde úplně odjinud. Jestli něco procesor umí dobře, je to práce s velkými bloky paměti. Když totiž procesor zjistí, že pracuješ s určitým blokem paměti, přesune si ho do cache a kód poběží řádově rychleji.

V případech (a) a (b) je mnohem větší šance, že procesor bude cacheovat správné bloky, protože bude implicitně předpokládat inkrementální průchod. Pokud v rámci cyklu procházíš i nějakou oblast okolo aktuálního indexu, je velká šance, že případ (c) bude o dost pomalejší.

Dobrá zpráva je, že rozdíl v rychlostech bude jen minimální, takže se o to nemusíš starat. Od té doby, co přišly procesory s taktem přes 1GHz, jsem podobné problémy řešil pouze dvakrát:

V prvním případě šlo o implementaci GEMM, viz http://wiki.cs.utexas.edu/…ptimizeGemm/
Ve druhém případě to bylo využití FFT k násobení polynomů přes konvoluci, viz http://en.wikipedia.org/…er_transform

Jsou to ovšem tak extrémní situace, že je lepší vždy dávat přednost případu (a).

Editováno 22.5.2014 22:39

Nahoru Odpovědět

22.5.2014 22:36

Jan Vargovský

Tvůrce

Jan Vargovský:22.5.2014 22:46

Dobře, díky za vysvětlení

Nahoru Odpovědět

22.5.2014 22:46

coells

Tvůrce

coells:23.5.2014 11:13

Ještě si můžeš vyzkoušet tenhle prográmek, který demonstruje cache-miss.
Program jednoduše prochází stále stejným polem a sčítá jeho prvky, ale v jednotlivých případech běhá po různě vzdálených indexech.

class Program
{
    private static void Measure(int[] arr, int stride)
    {
        Stopwatch w = new Stopwatch();
        w.Start();

        int sum = 0, index = 0, n = arr.Length;
        for (int i = 0; i < n; i++)
        {
            sum += arr[index];
            index = (index + stride + n) % n;
        }

        w.Stop();
        Console.WriteLine(stride + " " + w.ElapsedMilliseconds + " " + sum);
    }

    static void Main(string[] args)
    {
        const int n = 100000000;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = i;

        Measure(arr, 1);
        Measure(arr, 11);
        Measure(arr, 111);
        Measure(arr, 1111);
        Measure(arr, 11111);
        Measure(arr, 111111);
        Measure(arr, 1111111);
        Measure(arr, 49999999);
        Measure(arr, -49999999);
        Measure(arr, -1111111);
        Measure(arr, -111111);
        Measure(arr, -11111);
        Measure(arr, -1111);
        Measure(arr, -111);
        Measure(arr, -11);
        Measure(arr, -1);
        Measure(arr, 1);
    }

Na mám notebooku jsem dostal tohle:

1 886 887459712
11 1025 887459712
111 1434 887459712
1111 2661 887459712
11111 1817 887459712
111111 1865 887459712
1111111 1488 887459712
49999999 995 887459712
-49999999 923 887459712
-1111111 1559 887459712
-111111 1975 887459712
-11111 1876 887459712
-1111 2757 887459712
-111 1439 887459712
-11 945 887459712
-1 889 887459712
1 890 887459712

Docela by mě zajímalo, jak by si se stejným kódem poradila Java, když všichni tvrdí, že už je stejně rychlá jako C#.

Nahoru Odpovědět

23.5.2014 11:13

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 9 zpráv z 9.