.[ ČeskéHry.cz ].
std::vector a rekurze
Jdi na stránku 1, 2  Další
 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> C / C++
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
mar



Založen: 16. 06. 2012
Příspěvky: 526

PříspěvekZaslal: 6. březen 2014, 23:42:04    Předmět: std::vector a rekurze Odpovědět s citátem

Čau,
řešil jsem před chvílí vtipný problém s std::vectorem (samozřejmě v debug buildu bez optimalizací problém nenastával Smile
měl jsem následující kód v rekurzivně volané fuknci

kód:

void func(...)
{
    ...
    size_t pos = v.size();
    ...
    v.push_back( ... );
    if ( ... )
        v[pos].a = func(...);
    if ( ... )
        v[pos].b = func(...);
}


problém je ten, že volání rekurzivní funkce může realokovat vektor, překladač ale udělal to, že si načetl pointer na data před voláním a až pak jej použil.
Řešení bylo uložit výsledek volání do pomocné proměnné a tu pak přiřadit (tj. uměle vytvořit sequence point)

kód:

    if ( ... )
    {
        size_t tmp = func(...);    // sequence point
        v[pos].a = tmp;
    }


samozřejmě chyba byla na mé straně (undefined behavior), nicméně nevíte někdo, jestli toto řešení (hack)
je v pořádku a nerozbije mi to v budoucnu chytřejší překladač? Smile
Čistší řešení by bylo přidávat vyplněnou strukturu až po rekurzi, ale chci mít zachované toto pořadí (tj. aby root uzel byl uložen jako první).
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
quas4



Založen: 18. 10. 2007
Příspěvky: 199

PříspěvekZaslal: 7. březen 2014, 00:31:39    Předmět: Odpovědět s citátem

Muzes vysvetlit co myslis tim "sequence point"? z kodu ktery jsi napsal nejsem moc moudry. func je void ale jeji vysledek nekam prirazujes. jsi schopen napsat kratky zkompilovatelny kod ktery by demonstroval toto rozdilne chovani mezi debug a optimalizovanou verzi o kterem pises? mam podezreni ze ti unika neco podstatneho.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
micky



Založen: 28. 02. 2008
Příspěvky: 337
Bydliště: Plzeň, Praha

PříspěvekZaslal: 7. březen 2014, 00:43:55    Předmět: Odpovědět s citátem

Co to bylo za překladač...?

Navíc - moje interpretace:
kód:

TYP func(...)
{
    ...
    v.push_back( ... );
    if ( ... )
        temp = func(...);
        v[v.size()-1].a = temp; ///??? push_back?
    if ( ... )
        temp = func(...);
        v[v.size()-1].b = temp; ///??? push_back?
}


...nicméně se mi to celé nějak nezdá, podle toho segmentu, co jsi původně napsal, tak nejdřív vložím prvek do pole (odpovídá indexu pos), následně se v rekurzi vkládá vesele dál, pak se vrátím zpátky a na to samé pole (pos) si zapíšu výsledek. Pokud to chceš přepisovat, tak OK... Ani to nesouvisí s tím, jestli se teda vyhodnotí dříve pravá nebo levá strana přiřazení...
_________________
http://www.bluepulsar.cz/
https://twitter.com/bluepulsargames/
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 526

PříspěvekZaslal: 7. březen 2014, 09:17:52    Předmět: Odpovědět s citátem

Ok zapomněl jsem pár věcí, takže tady mám funkční kód:

kód:

#include <cstdlib>
#include <vector>

struct Struct
{
    size_t indices[2];
};

size_t func( std::vector< Struct > &v, int depth = 1 )
{
    if ( depth >= 10 )
        return -1;

    // force allocation
    std::vector< int > iv;
    iv.push_back( depth );

    size_t res = v.size();
    v.push_back( Struct() );
    v[res].indices[0] = func( v, depth+1 );
    v[res].indices[1] = func( v, depth+1 );
    return res;
}

int main()
{
    std::vector< Struct > v;
    func(v);
    return 0;
}


Překladač je Microsoftí (VS2012).
Toto v release padá (protože si načtě pointer na data do registru před voláním func.

Se sequence pointem to funguje:
kód:

    size_t tmp;
    tmp = func( v, depth+1 );
    v[res].indices[0] = tmp;
    tmp = func( v, depth+1 );
    v[res].indices[1] = tmp;


quas: sequence point je popsaný ve standardu, to není pojem, který bych já vymyslel Smile
http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
quas4



Založen: 18. 10. 2007
Příspěvky: 199

PříspěvekZaslal: 7. březen 2014, 10:30:11    Předmět: Odpovědět s citátem

dik za link. Hezky to ilustruje co vsechno je potreba v c++ standardu specifikovat protoze samotny jazyk je tak neuveritelne komplikovany. Jenom specifikace gramatiky by byla urcite na mnoho stran. c++ je podle me spatny programovaci jazyk.

Neni lepsi si pred func() naalokovat vector (nebo Struct* v) uz s potrebnou velikosti? (mensi defragmentace pameti, optimalnejsi vuci L2 cache, jen jeden narocny malloc/new)

(1 << (max_recur - 1)) - 1

a neresit "sequence point"? Jeho existenci a nutnost v tomto pripade vnimam jako selhani jazyka nez jako chybu v uvaze programatora.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 526

PříspěvekZaslal: 7. březen 2014, 10:48:44    Předmět: Odpovědět s citátem

quas4 napsal:
dik za link. Hezky to ilustruje co vsechno je potreba v c++ standardu specifikovat protoze samotny jazyk je tak neuveritelne komplikovany. Jenom specifikace gramatiky by byla urcite na mnoho stran. c++ je podle me spatny programovaci jazyk.

Neni lepsi si pred func() naalokovat vector (nebo Struct* v) uz s potrebnou velikosti? (mensi defragmentace pameti, optimalnejsi vuci L2 cache, jen jeden narocny malloc/new)

(1 << (max_recur - 1)) - 1

a neresit "sequence point"? Jeho existenci a nutnost v tomto pripade vnimam jako selhani jazyka nez jako chybu v uvaze programatora.

No jak se na ten link koukám, tak volání funkce by měl být taky sequence point Shocked
Ano předem si to naalokovat by řešení bylo, projít si strom, spočítat uzly a pak to jenom plnit. Je to kód, který dělám v preprocess kroku, takže nic kritického. Jenom bych se rád do budoucna vyhnul podobným překvapením.
Jinak souhlasím, nějakou dobu jsem pokukoval po D, ale nakonec z toho udělali podobný balast, jako z C++.
Je tam celkem dost dalších věcí, na které je třeba si dávat pozor, jako např. že přetečení signed integeru je undefined behavior, standard navíc neříká, že reprezentace celých čísel musí být ve two's complement formátu, že reprezentace nulového pointeru nemusí být nula apod., tohle jsou ale pozůstatky z dob minulých.
EDIT: tak to vypadá, že to nesouvisí se sequence points, ale s tím, že u přiřazovacího operátoru = standard nezaručuje, že pravá strana se vyhodnotí dřív, jediná záruka je, že přiřazení se provede až po vyhodnocení obou stran
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
perry



Založen: 28. 07. 2009
Příspěvky: 866

PříspěvekZaslal: 7. březen 2014, 11:19:22    Předmět: Odpovědět s citátem

V tom postnutém "funkčním" kódu absolutně nepobírám tohle:

kód:

    // force allocation
    std::vector< int > iv;
    iv.push_back( depth );


K čemu to tam je... to je naprosto k ničemu. Příklad jsem nezkoušel pustit, ale ani nechápu o jakém pointeru tam mluvíš.. žádný pointer nikde nevidím (pokud mluvíš o &, tak to není pointer ale reference).

Plus zkoušel jsem ten kód a nijak mi to nepadá

Ad C++... jazyk je to v pohodě a dá se v tom psát úplně normálně. Ano, jdou tam psát čuňárny.. ale to nevidím jako chybu jazyka, ale programátora
_________________
Perry.cz
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
quas4



Založen: 18. 10. 2007
Příspěvky: 199

PříspěvekZaslal: 7. březen 2014, 11:28:51    Předmět: Odpovědět s citátem

mar> hehe. jasne. c++ umi cloveku vylozene explodovat pred ocima.

na programovani her kde je dulezita rychlost se mi jevi jako kandidati golang (velka komunita, pekne udelana prace s thready, nema operator overloading, atd..) nebo jeste lepe rust (generuje rychly kod, dobre navrhnuta prace s pointery, atd..)

na ostatni (napr. web server apod.) jsem zastancem lispu a scheme. expresivita a syntakticka jednoduchost lisp-like jazyku je uzasna. Z implementaci mam dobrou zkusenost s sbcl, clojure, guile, gambit, kazde je dobre podle typu ulohy.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 526

PříspěvekZaslal: 7. březen 2014, 11:43:15    Předmět: Odpovědět s citátem

perry napsal:
V tom postnutém "funkčním" kódu absolutně nepobírám tohle:

kód:

    // force allocation
    std::vector< int > iv;
    iv.push_back( depth );


K čemu to tam je... to je naprosto k ničemu. Příklad jsem nezkoušel pustit, ale ani nechápu o jakém pointeru tam mluvíš.. žádný pointer nikde nevidím (pokud mluvíš o &, tak to není pointer ale reference).

Plus zkoušel jsem ten kód a nijak mi to nepadá

Nekoukej na funkčnost toho kódu, demonstruje to čistě určitý případ, který může nastat.
Tohle tam je kvůli tomu, aby se vynutila alokace, která si vezme blok, který byl uvolněný realokací vektoru (tj. aby to poškodilo heap a tím pádem padalo).
Mně to tady padá, Microsoftí překladač (VS2012), release.
Jinak v tomhle případě to byla moje chyba a pro příště si dám větší pozor.
quas: díky, podívám se, většinu z toho neznám (kromě go a clojure, o kterých jsem už slyšel)
EDIT: perry tak máš pravdu, ta dummy alokace tam ani není potřeba, stačí si to zvýšit na ( depth >= 20 )
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
perry



Založen: 28. 07. 2009
Příspěvky: 866

PříspěvekZaslal: 7. březen 2014, 12:25:07    Předmět: Odpovědět s citátem

Jde o to, ze tu dummy alokaci stejne visualko pri prekladu vyhodi. Nikde se nepouziva, takze je tm k nicemu. Teda alespon myslim ze ji v release buildu vyhodi.
_________________
Perry.cz
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
]semo[



Založen: 29. 07. 2007
Příspěvky: 1472
Bydliště: Telč

PříspěvekZaslal: 7. březen 2014, 13:54:53    Předmět: Odpovědět s citátem

quas4 napsal:
... c++ je podle me spatny programovaci jazyk.

To mě vždycky tak rozesmutní. Je to napsat, že "moře je podle mě špatné, mělo by se jezdit jen na rybníku" Neni to tak nebezpečné, že...? :-)
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
quas4



Založen: 18. 10. 2007
Příspěvky: 199

PříspěvekZaslal: 7. březen 2014, 14:46:07    Předmět: Odpovědět s citátem

]semo[ napsal:
quas4 napsal:
... c++ je podle me spatny programovaci jazyk.

To mě vždycky tak rozesmutní. Je to napsat, že "moře je podle mě špatné, mělo by se jezdit jen na rybníku" Neni to tak nebezpečné, že...? Smile


takoveto srovnani je velmi zjednodusujici a scestne. V cem srovnavas c++ s morem? V tom ze je na nem nebezpecne jezdit? O bezpecnosti prece nebyla vubec rec. A i kdyby tak jsem ani v nejmensim netvrdil ze ti co to umi by se na nej nemeli poustet. Minimalne v tomto je to zavadejici..

K cemu je c++ urceno a je v tom taky vyborne? Podle me velice komplikovanou syntaxi a neprehlednou semantikou prekladacu (napriklad zde: http://stackoverflow.com/questions/620137/do-the-parentheses-after-the-type-name-make-a-difference-with-new nebo vtipny dotaz zde: http://stackoverflow.com/questions/5347444/overload-resolution-and-arrays-which-function-should-be-called ). Pokud nevnimam programovaci jazyk jak nastroj pro psani poezie pak vyzaduji prakticke vlastnosti do kterych pro me spada i syntakticka jednoduchost. V pripade programovani "poezie" bych sahnul treba na Brainfuck nebo Piet. I v nich lze napsat velke veci.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
VODA



Založen: 29. 07. 2007
Příspěvky: 1692
Bydliště: Plzeň

PříspěvekZaslal: 7. březen 2014, 15:14:04    Předmět: Odpovědět s citátem

Mně se přirovnání, které Semo napsal líbí. Osobně C++ preferuji nad všemi dalšími jazyky.
A co se týče toho kódu, řeknu jen jednu věc... fuj rekurze! Razz
_________________
Opravdovost se pojí s trýzní...
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
]semo[



Založen: 29. 07. 2007
Příspěvky: 1472
Bydliště: Telč

PříspěvekZaslal: 7. březen 2014, 15:23:19    Předmět: Odpovědět s citátem

Tak jiný přirovnání :-)- Máš letadlo - akrobatický speciál. Obyčejnej pilot se bude skoro bát do toho sednout, protože se to řídí špatně. A je to snad proto špatné letadlo? No neni. Prostě jen dává více volnosti za cenu náročnějšího řízení.

U těch příkladů, co si poslal, je samozřejmě jedno velké ALE: nikdo tě nenutí to psát takhle. A musel bys být fakt velké prase, abys to tak psal. U C++ zkrátka záleží na tom, jakým stylem budeš psát. U jiných jazyků ti ten styl většinou někdo vnutí.

Ještě že je pátek, aspoň se ten flame snad brzo utne (aspoň pro mě, až za chvíli vypnu komp :) ).
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 526

PříspěvekZaslal: 7. březen 2014, 15:41:14    Předmět: Odpovědět s citátem

]semo[ napsal:
To mě vždycky tak rozesmutní. Je to napsat, že "moře je podle mě špatné, mělo by se jezdit jen na rybníku" Neni to tak nebezpečné, že...? Smile

Kdyby mě pokaždé rozesmutnilo to, že má někdo jiný názor než já, tak bych byl asi smutný pořád Smile
Co se týká rekurze, ten kód (původní) dumpuje bsp strom. Nevidím absolutně důvod to měnit a mít kvůli tomu složitější kód.
Btw. recursive descent je taky fuj? Smile
Nicméně díky za flamewar, teď jsem konečně spokojený Wink
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> C / C++ Časy uváděny v GMT + 1 hodina
Jdi na stránku 1, 2  Další
Strana 1 z 2

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna