Kolko cyklov zbehne

Kolko cyklov zbehne
« kdy: 12. 08. 2020, 22:32:17 »
Dobrý deň, kolko cyklov zbehne počas vykonávania tohoto kódu?:

Kód: [Vybrat]
std::vector<int> result;
boost::copy(
        boost::irange(1, 12)
        | filtered([](const int n) { return n % 2 == 0; })
        | transformed([](const int n) { return n * n; }),
        std::back_inserter(result)
);

A poprosím aj vysvetliť prečo. Ďakujem.


Re:Kolko cyklov zbehne
« Odpověď #1 kdy: 13. 08. 2020, 09:30:28 »
... kolko cyklov zbehne ...
Šlo by tu otázku trochu rozepsat? Vůbec netuším, na co se ptáš.

none_

Re:Kolko cyklov zbehne
« Odpověď #2 kdy: 13. 08. 2020, 10:38:32 »
Zalezi na tom, co kazda ta funkce vraci. Neznam tenhle konkretni programovaci jazyk, ale jsou v podstate 2 moznosti.

1. Jedna se o nejake Stream API. Tzn zadna z tech funkci nevraci primo pole, ale misto toho vraci instanci nejakyho streamu. Vy pridavate dalsi a dalsi funkce do toho retezu. Pak to vypada takto:
irange vygeneruje prvni prvek 1, posle ho filtru (overi delitelnost 2), pokud nesplnuje, konec; pokud splnuje, provede se transormace, prvek se vlozi do vysledneho vectoru. Tohle opakuj pro kazdy prvek. Celkem jeden cyklus.

2. kazda ta operace vraci rovnou vector<int> nebo nejaky pole. Potom by kazda ta operace sbehla cyklus. Tedy: range vygeneruje pole 1-12 (1. iterace), filtr projede pole a vyhazi polovinu (2. iterace), transformace vynasobi kazdy prvek (3. iterace na mensim poli), vlozit kazdy prvek do noveho pole (4. iterace). Navíc každá operace vytvoří nové pole a staré zahodí.

Tezko rict, co dela vas kod konkretne. Pokud se pipe chova stejne jako treba v bashi, tak bych tipnul na ty 4 iterace. Na druhou stranu muze v tom jazyce pipe znamena to, co treba jave znamena "." (zretezeni prikazu). Kazdopadne at tak nebo tak, mel byste byt schopny si to projit v debugeru...

Re:Kolko cyklov zbehne
« Odpověď #3 kdy: 13. 08. 2020, 11:39:45 »
Zalezi na tom, co kazda ta funkce vraci. Neznam tenhle konkretni programovaci jazyk, ale jsou v podstate 2 moznosti.

1. Jedna se o nejake Stream API. Tzn zadna z tech funkci nevraci primo pole, ale misto toho vraci instanci nejakyho streamu. Vy pridavate dalsi a dalsi funkce do toho retezu. Pak to vypada takto:
irange vygeneruje prvni prvek 1, posle ho filtru (overi delitelnost 2), pokud nesplnuje, konec; pokud splnuje, provede se transormace, prvek se vlozi do vysledneho vectoru. Tohle opakuj pro kazdy prvek. Celkem jeden cyklus.

...

Tezko rict, co dela vas kod konkretne. Pokud se pipe chova stejne jako treba v bashi, tak bych tipnul na ty 4 iterace. Na druhou stranu muze v tom jazyce pipe znamena to, co treba jave znamena "." (zretezeni prikazu). Kazdopadne at tak nebo tak, mel byste byt schopny si to projit v debugeru...
Je to stream api z C++.

Range se skládá z iterátoru a zarážky. Iterátor se dá posunout na nový prvek, dereferencovat nebo porovnat se zarážkou.
"filtered" vylepší posun iterátoru
"transformed" vylepší dereferenci iterátoru
Až to "copy" tu range projde a nacpe výsledky do výstupní range (a ta při zápise přidává do vectoru).

Takže ten kód teoreticky odpovídá jednomu for-cyklu. Ale reálně to bude větší binec, protože do toho vstupují i další věci jako realokace toho vectoru. Proto jsem se ptal na detaily.

jouda2

Re:Kolko cyklov zbehne
« Odpověď #4 kdy: 13. 08. 2020, 12:27:37 »
Takže ten kód teoreticky odpovídá jednomu for-cyklu. Ale reálně to bude větší binec, protože do toho vstupují i další věci jako realokace toho vectoru. Proto jsem se ptal na detaily.
Tak neznaje vnitřnosti C++, tak bych to asi prostě přeložil s debug symboly a podíval se do toho oblíbeným debuggerem, případně gcc umělo překládat i do assembleru (pokud nevadí at&t syntaxe)


none_

Re:Kolko cyklov zbehne
« Odpověď #5 kdy: 13. 08. 2020, 12:58:46 »
Je to stream api z C++.

Mohl byste jeste vyvsetlit, co znameta ten operator pipe "|". C++ syntaxi trochu znam, ale tohle si nepamatuju. V C++ bych cekal spis neco takovyhleho: boost::irange(1, 12).filtered().transformed()... Nebo je to nejak pretizenej operator?

Re:Kolko cyklov zbehne
« Odpověď #6 kdy: 13. 08. 2020, 14:34:48 »
Je to stream api z C++.

Mohl byste jeste vyvsetlit, co znameta ten operator pipe "|". C++ syntaxi trochu znam, ale tohle si nepamatuju. V C++ bych cekal spis neco takovyhleho: boost::irange(1, 12).filtered().transformed()... Nebo je to nejak pretizenej operator?

Ďakujem za vysvetlenie. Vidím že ste moju otázku nakoniec pochopil.

Išlo mi o to či sa tam používa lazy evaluation a či sa tie operácie optimalizujú na čo najmenší počet cyklov. Takže to funguje podobne ako LINQ (alebo spomínané streamy z Java).

Ja som si to nakoniec aj prechádzal v debuggeri a vyzeralo to tak že obidve adaptéry sa aplikujú vrámci 1 cyklu postupne za sebou. Najprv 2 iterácie filter potom sa aplikuje map a potom znovu filter.

Je to stream api z C++.

Mohl byste jeste vyvsetlit, co znameta ten operator pipe "|". C++ syntaxi trochu znam, ale tohle si nepamatuju. V C++ bych cekal spis neco takovyhleho: boost::irange(1, 12).filtered().transformed()... Nebo je to nejak pretizenej operator?

C++ má operator overloading. A tú pipu si overloadol boost. Správa sa to podobne ako forward pipe z funkcionálnych jazykov.
« Poslední změna: 13. 08. 2020, 14:36:19 od fortran1986 »

Re:Kolko cyklov zbehne
« Odpověď #7 kdy: 13. 08. 2020, 14:35:59 »
Najprv 2 iterácie filter potom sa aplikuje map a potom znovu filter.

Oprava: tým filter som myslel filtered a map = transformed.

Re:Kolko cyklov zbehne
« Odpověď #8 kdy: 13. 08. 2020, 17:10:47 »
Tak neznaje vnitřnosti C++, tak bych to asi prostě přeložil s debug symboly a podíval se do toho oblíbeným debuggerem, případně gcc umělo překládat i do assembleru (pokud nevadí at&t syntaxe)
V assembleru bohužel není moc čitelná ani ekvivalentní verze s forem a ifem :
https://godbolt.org/z/74WbPa
Dát si breakpointy do těch lambd je rozumnější řešení.
Mohl byste jeste vyvsetlit, co znameta ten operator pipe "|". C++ syntaxi trochu znam, ale tohle si nepamatuju. V C++ bych cekal spis neco takovyhleho: boost::irange(1, 12).filtered().transformed()... Nebo je to nejak pretizenej operator?
Jo, je to přetížený operátor.

Verze s tečkama by byla naopak naprosto proti filosofii c++. Ty range vycházejí z STL knihovny. STL poskytuje nezávislé kontejnery a algoritmy. Algoritmy vyžadují od kontejnerů jen minimální nutné rozhraní. Takže si napíšu vlastní kontejner a můžu ho s minimem námahy zkombinovat se všemi kompatibilními algoritmy. Můžu použít kontejner z jedné a algoritmus z druhé naprosto nezávislé knihovny.

A ta kombinace přes přetížený operátor (což je jen maskovaná globální funkce) funguje úplně stejně :
1) Tou řadou adaptérů můžu prohnat jakýkoliv kontejner, který podporuje standardní begin+end. Případně si ty dvě potřebné funkce můžu dopsat i pro nějaký obskurní kontejner třetí party. Dokonce k němu ani nemusím mít zdrojáky. I Cčkovské pole to zvládne.
2) Můžu si napsat nějaký adaptér, který pak můžu aplikovat na cokoliv úplně stejně jako ty standardní. Přes tečku nemůžu kombinovat adaptéry a kontejnery z nezávislých knihoven.

Re:Kolko cyklov zbehne
« Odpověď #9 kdy: 13. 08. 2020, 17:20:33 »
Cele je to jeden cyklus, ktery probehne 12 krat, ty funkce vraci iteratory, zpracovava se to po jednotlivych prvcich.

Re:Kolko cyklov zbehne
« Odpověď #10 kdy: 14. 08. 2020, 15:46:02 »
Dobrý deň, kolko cyklov zbehne počas vykonávania tohoto kódu?:

Kód: [Vybrat]
std::vector<int> result;
boost::copy(
        boost::irange(1, 12)
        | filtered([](const int n) { return n % 2 == 0; })
        | transformed([](const int n) { return n * n; }),
        std::back_inserter(result)
);

A poprosím aj vysvetliť prečo. Ďakujem.

Cyklů čeho? Takhle položená otázka nedává moc smysl, protože tam není žádná smyčka.

Odpověď na správnější otázku by byla asi takováto:
 - lambda u filtered se vykoná 11x
 - lambda u transformed se vykoná 5x
 - vector::push_back se vykoná 5x

Správnější otázku si domysli sám.

Mimochodem, to se mi to C++ nelíbí, ekvivalentní verze v Rustu:

let result: Vec<usize> =
  (1..12)
    .filter(|x| x % 2 == 0)
    .map(|x| x * x)
    .collect();

Re:Kolko cyklov zbehne
« Odpověď #11 kdy: 16. 08. 2020, 22:38:03 »
V assembleru bohužel není moc čitelná ani ekvivalentní verze s forem a ifem :
https://godbolt.org/z/74WbPa

Na to aby assembler output bol citatelny najskor treba kompilovat bez -O2 :D

Re:Kolko cyklov zbehne
« Odpověď #12 kdy: 16. 08. 2020, 23:29:31 »
V assembleru bohužel není moc čitelná ani ekvivalentní verze s forem a ifem :
https://godbolt.org/z/74WbPa

Na to aby assembler output bol citatelny najskor treba kompilovat bez -O2 :D
Není koukání na assembler bez optimalizací trochu zbytečné? Vždyť většina z toho budou nezajímavé prology, epilogy a přesuny věcí tam a zpět. Pár zajímavých instrukcí je utopených v šumu. Vám ten kód bez optimalizací přijde čitelnější? :o Vždyť to z nějakých 230 řádků udělalo 3k řádků "balastu".
A opravdu si myslíte, že v tom neoptimalizovaném assembleru najde tazatel odpověď na svou otázku?  ::)

Re:Kolko cyklov zbehne
« Odpověď #13 kdy: 17. 08. 2020, 17:53:49 »
V assembleru bohužel není moc čitelná ani ekvivalentní verze s forem a ifem :
https://godbolt.org/z/74WbPa

Na to aby assembler output bol citatelny najskor treba kompilovat bez -O2 :D
Není koukání na assembler bez optimalizací trochu zbytečné? Vždyť většina z toho budou nezajímavé prology, epilogy a přesuny věcí tam a zpět. Pár zajímavých instrukcí je utopených v šumu. Vám ten kód bez optimalizací přijde čitelnější? :o Vždyť to z nějakých 230 řádků udělalo 3k řádků "balastu".
A opravdu si myslíte, že v tom neoptimalizovaném assembleru najde tazatel odpověď na svou otázku?  ::)

noo ak chces pochopit kolkokrat sa zavola ta ktora metoda z boostu v tomto konkretnom kode tak definitivne ano, lebo -O2 v tomto pripade cely boost zahodi a spravi si to po svojom... a ak spravne chapem v metode bar tiez zahodi push_back vysledky si predpocita do pola a z toho spravi vector...,

tych 230 vs. 3k riadkov je rozdiel kvoli tomu, ze compiler explorer do vystupu zahrna aj kod kniznicnych funkcii (std, boost).., bez optimalizacii vysledny kod vykonava to, co mu autor povedal, ze ma robit.., optimalizacie kod prepisu castokrat na nespoznanie (uz len to, ze compielr explorer ukazuje ktore riadky asm zodpovedaju ktorym riadkom C a s -O2 ku vacsine riadkov v C neexistuje ASM ekvivalent lebo ich proste kompilator zahodil :D )

+ nehovoriac o tom, ze s beznymi znalostami ASM z jedneho semestra na vyske je ovela viac citatelnejsi neoptimalizovany kod ako vystup s optimalizaciami lebo kompilator/optimalizator je schopny vytiahnut z klobuka nejaku 5pismenkovu instrukciu ktoru ludia ktori nerobia s assemblerom dennodenne castokrat vidia prvy krat..,

alex6bbc

  • *****
  • 1 431
    • Zobrazit profil
    • E-mail
Re:Kolko cyklov zbehne
« Odpověď #14 kdy: 17. 08. 2020, 22:10:36 »
souhlas s odpovedi "Cele je to jeden cyklus, ktery probehne 12 krat, ty funkce vraci iteratory, zpracovava se to po jednotlivych prvcich."

jeden cyklus co se 12x otoci a uvnitr se pokazde provede test/prepocet filtered/transformed a to jednou
pokazde jednou v kazdem kroku, bud s vysledkem true nebo false zda se zaradi do vystupu.

takze 12 cyklu.