Hogy lehetne hatékonyabb ez a c++ program?

Hogy lehetne hatékonyabb ez a c++ program?
2021-11-25T16:33:20+01:00
2021-11-30T15:12:35+01:00
2022-10-17T07:00:40+02:00
  • forráskódok miért nem monospaced fonttal vannak

    Bjarne Stroustrup ajánlása is ez, bár nem terjedt el
    Mutasd a teljes hozzászólást!
  • Standard váltás sajnos nem egyszerű, főleg ha vannak külső függőségek (pl standard váltás törheti az ABI-t, tehát nem csak a saját projektet kell adott esetben újra fordítani, menedzselni)

    Mondjuk eleve nem szeretem pont ezért azt sem, ha standard lib típusokat binary api kiad... Ha ott a forrás, akkor viszont támaszkodok azért amennyire lehet az std libre, de ha shared object-esedés van, ott jellemzően szeretem, ha C-style egyszerű api van noexcept-ekkel (mert ugye az exception is okozhatna meglepetéseket).

    Hasonló problémát jelenthet függőségek-ből adódó megkötések, pl CUDA compiler supportálja-e..

    Inkább ez az, amire nehéz értelmes workaround-okat tervezni. A third party nagyon ocsmány dolgokba kényszerítheti az embert és ez csak a jéghegy csúcsa amit mondasz. Nekem az a kedvencem, amikor valami SDK odaborít egy teherautónyi kódot a dll-ek mellé és egy build ecosystem-et és az egész úgy van megcsinálva, hogy nagyobb meló egy cmake, vagy akár make build-et csinálni rá, mint az egész projekt, szóval valami legacy build rendszerhez kezd igazodni a projekt, mert pluginja valami "híres proginak" - Ja és persze konkrétan az interfészes kódok csak közel 5 éves fordítóval fordulnak, de ott is ki kell kapcsolnod... nem warningokat, hanem hibákat  

    Csapaton belül egyeztetni kell a guideline-okat

    Jó ez már nagyon csapat, meg projektméret függő is. Meg attól is függő, hogy open source, vagy closed source (vagy ha closed, akkor is minden source-ban van-e, vagy vannak bináris hidak). Van ahol ez semmiből sem áll és mégis nagy projekt és ilyen "rolling release"-hez hasonló szemlélettel csinálják. Nyilván nem lehet mindenhol.

    Amúgy teljesen jogosak az érvek, amennyiben library-t fejlesztesz,

    Jah... mondjuk a nagyobb méretű kódjaim mostanában lib fejlesztések voltak - több ügyfélnek is főként ilyen téma volt ahol meg app / plugin stb. része is volt a dolognak, az meg az én libem használta és igyekeztem kiemelni a dolgokat a libbe, mert elég általános, hogy több helyre jó legyen.

    Az első változattal kellene napi szinten dolgoznom, hát kifolyna a szemem és nagyon szomorú lennék (IDE színezés ide vagy oda..) :(

    Én meg ha ezt meglátom és nem látszik rajta, hogy hol használok standard libet és hol nem - vagyis rögtön az alapján, hogy távolról ránézek a kódra, nem egyértelmű, hogy használja az adott rész a standard libet - na engem inkább az zavar.

    Az ilyen "mindenki írjon QString szerű osztályokat, meg QVector-t stb." szemléletet is hülyeségnek tartom, de azt, hogy hol használom a standardot én tényleg szeretem ránézésből látni - pont az ilyen fenn nevezett dolgok miatt is.

    Nekem a második változat se szimpatikus annyira - ezeket a tapasztalatom szerint sokkal jobb kiírni sima ciklussal - hacsak nincs valami performance, vagy egyéb gain... Én látom mi történik, de azért nem vagyok annyira biztos benne, hogy a projektre kerülő összes ember látni fogja. A másik ami miatt ezeket ki szeretem írni, hogy jobban "kilátszik" mire fordul a cucc. Hasonló okból némely esetben (bár nem annyira vallásosan, mint egyesek) például az operator overload-al is vigyázni szoktam, mert jó ha a kódon reflexből meglátszik nem csak a nagyordó, de azért a konstans szorzó becsült nagysága is.

    Ilyen stilisztikai dolgokban elég projekt/csapatfüggő sok minden az tény, de azért lehet értelmesen érvelni. De az agy nagyon jó a mintaillesztésben, így szerintem (legalábbis én eddig ezt láttam) semmi akadálya hogy ne legyen egy megszokás után nem szemkifolyós ha ki van írva az std. Én is használok néha using namespace-t de tényleg erősen lokálisan és csak amikor nagyon egymásba ágyazott namespace-ek vannak. Érdekes, de fájl-szinten amikor legutoljára használtam, akkor az sem a standard lib volt (pedig bőven volt abban a fájlban), hanem egy randa-nevű namespace-be írt single-header lib miatt, ahol tényleg nem akartam kiírni.

    De akkor is áll, hogy ha header-be kell áttenni (én elég sok template-es kódot írok), akkor máris bukó ez és ott is akkor vagy ki kell írjam, vagy szűk scope-ba tenni a using-ot. A függvényed elejére betenni például tökre okés lehet...

    Szóval én tényleg inkább azt preferálom, ahogy kb. pont ők is mondják:
    Standard C++
    Mutasd a teljes hozzászólást!
  • Offtopic, viszont egyáltalán nem értelmetlen..

    Attól függ milyen projekten - ahol így van ott nyilván komoly dolog.

    Standard váltás sajnos nem egyszerű, főleg ha vannak külső függőségek (pl standard váltás törheti az ABI-t, tehát nem csak a saját projektet kell adott esetben újra fordítani, menedzselni)
    Hasonló problémát jelenthet függőségek-ből adódó megkötések, pl CUDA compiler supportálja-e..
    Csapaton belül egyeztetni kell a guideline-okat, hogy melyik feature-t hogyan szeretnénk használni, minek elvárt a használata, stb.. hogy konzisztens maradjon a fejlesztés.

    Amúgy teljesen jogosak az érvek, amennyiben library-t fejlesztesz, ott nyilván felértékelődik a könyvtár stabilitása külső felhasználók számára.. Tehát nem fekete-fehér dolog.

    std::ranges::for_each( std::ranges::iota_view{0, 10}, ( std::cout<< boost::lambda::_1 % 3 )); vs rng::for_each( iota_view{0, 10}, ( cout<<_1 % 3 ));
    Az első változattal kellene napi szinten dolgoznom, hát kifolyna a szemem és nagyon szomorú lennék (IDE színezés ide vagy oda..) :(
    Mutasd a teljes hozzászólást!
  • Ha az olvashatósággal van bajod, akkor válts színsémát az editorban, ami kiszínezi valami totálisan neutrális színnel és kész. Egyébként meg azért is jó megszokni "normálisan", mert ennyi erővel ha template-esíted akkor olvashatatlan lesz számodra a kód, mert nem szoktad meg? Vagy ott berakod scope-ba csak azért is?

    Standard váltás egy projekten komoly dolog

    Jó, de ha nulláról csinál az ember projektet úgy akarja csinálni, hogy ne legyen komoly dolog. Sok projekten semmiből se áll standardot váltani, de persze pont attól függ milyen projekten - ahol így van ott nyilván komoly dolog. Az a poén, amikor third party cucchoz volt pár kis modul amivel kommunikálsz egy DLL-el. A DLL / so nem open, de a kis cuccot forrással adják (és annyira az se "kicsi", de a cucchoz képest igen). Aztán tök jó amikor abban például valaki így gondolkozott mint most te és volt neki névütközés igen... nem igaz, hogy nem lehet ezt elkerülni... az olvashatóságon még javít is, hogy látod, hol van a standard lib használva és hol valami más.

    Most ne csak arra gondolj, hogy ütköznek a nevek, hanem mondjuk nem váltottál standardot, de a világon mindenki más ezer éve igen (khm... tudok példát...) és olvasva a kódot a standard manpage-ére tévedsz ahelyett, hogy az ő saját kis függvényüket látnád a hívás mögött. Na mindegy... etekintetben én annak vagyok a híve, hogy lehetőleg konzisztensen mind headerben, mind cpp fájlban ki legyen írva, de ha nem akarod kiírni (mondjuk a chrono-nál elég mély kezd lenni néha), akkor minél lokálisabban csak ott egy erősen szkópolt using legyen.

    De amúgy ez offtopic vita szerintem itt erősen, csak azt akartam, hogy legalább ha valaki erre jár, legyen már egy warning a megjegyzés alatt, hogy "ne művelj ilyet", vagy legalább "gondold át", mert te lehet hogy csak egy mini fájlnál használod ilyen példánál mondjuk, de aki nézi az hidd el betolja a header tetejére...
    Mutasd a teljes hozzászólást!
  • cpp-ben headerek után szerintem nem gond a 'using namespace std' sem.
    Ebben valóban van annyi kockázat, hogy standard váltásnál új dolgok kerülhetnek az std névtérbe, mely törheti a létező kódot névütközés miatt.

    Standard váltás egy projekten komoly dolog, az ilyen hibákat elég könnyű javítani (explicit megadod, hogy melyik namespace, ha ütközés van.)
    Szerintem ennyit megér, mert a másik oldalon sokkal többet jelent a kód olvashatóságán, hogy nincs ott a tonnányi tök felesleges 'std::'. Kiírni kód kiegészítés miatt nyilván nem ügy. Olvashatóság, ami óriási érték és bizony van különbség!
    Mutasd a teljes hozzászólást!
  • Igen, antipattern header-be...

    Meg .cpp fájlba is az, mert így keletkeznek azok a megoldások, amikor először így van a kód, majd a header-be kopizza valaki, mert mondjuk betesz egy template paramétert fejlesztés közben. Jobb esetben akkor átkörmöli az egészet és dühöng egyet, rosszabb esetben egy megfelelő scope-ba beteszi a using-ot, legrosszabb esetben rátalál ilyen kódokra a neten és a header tetejére beírja a másolás után...

    De értem mit akarsz mondani, csak ugyebár amikor a header tetejére írják, az is úgy történik, hogy a neten látnak "ilyen" kódokat, ahol "a fájl tetején" van a using... Szóval jó ha ilyet egyáltalán nem is látni na én csak azt mondom.
    Mutasd a teljes hozzászólást!
  • Ha ennyire optimalizálsz, akkor miért nem O3-al fordítasz?

    Az O3 nem mindig gyorsabb, mint az O2 - sőt!
    Azért nem küldözgettem azokat az eredményeket, mert az algoritmusok sorrendje nem változott (néztem O3-al is), és marginálisan ment feljebb vagy lejjebb egyik-másik az O2-ről 3-ra váltásnál. Igazából ahogy néztem inkább rosszabb is lett, de ez egyáltalán nem meglepő. Agresszívebben inline-olja amit annak jelölsz például és láthatod a példámból, hogy a "rendbe()" hívást mondjuk ha mindenhova inline-olod, akkor buksz vele, de ha csak szelektíven a belső hívást, akkor a simához képest nyersz vele. Szóval a kevesebb néha több.

    Pl engem meglepne, ha a vector absztrakciónak lenne bármilére overhead-je normál pointeres eléréshez képest.

    Pedig határozottan mérhető, bár kis különbség volt a tight loop miatt. De láthatod, hogy az új megoldásban is vektorban tartom az elemeket, csak nem vektorra mutató pointereket cserélgetek, hanem int* pointereket. Ha sima változó lenne ott, nem egy std::vector-ra mutató pointer akkor szinte semmi különbség nem volna, sőt a fordító akár a függvényhívást is inline-olhatja pl. a size() lekérdezésnél nekem. Itt azért nem, hiszen pointereket cserélek, illetve azon keresztül értem el a vektort és ő véletlenül sem szabad hogy inline-olja a hívásokat, mert fogalma se lehet a compilernek, hogy mely vektor van éppen melyik helyen a háromból az algoritmusomnál. Szóval teljesen jogos, hogy van egy plusz indirekció. Semmi vtable meg ilyesmi, csak egy plusz indirekció ezen a pointeren át, hogy tényleg mi ott a this - holott egy sima esetben ezt szanaszéjjel tudta volna optimalizálni valószínűleg.

    De elég marginális volt a különbség - mondom max 5%, de inkább 3-5% hogy őszinte legyek, csak akkor már így hagytam. Szóval nem a vektor lassú (az amúgy tök gyors még a c++03 időkhöz képest is), hanem a plusz indirekció egy minimálisat pazarol ott...
    Mutasd a teljes hozzászólást!
  • Tökre antipattern a using namespace std; Itt most senki se "szép kódra" törekszik (kivéve az első változatomnál kb. közepesen szépre), de ezt még példába se jó mutatni..

    Igen, antipattern header-be...
    Mutasd a teljes hozzászólást!
  • Igen, a feladatot ez is megoldja és ez is le fog futni ekkora elemszámra - bár mint sejtettem lassabb, mint a többi megoldás, de szép ettől még ez is és mint a merge-es megoldást ezt is nehéz elrontani  

    Egyébként:
    - Tökre antipattern a using namespace std; Itt most senki se "szép kódra" törekszik (kivéve az első változatomnál kb. közepesen szépre), de ezt még példába se jó mutatni...
    - map helyett ebben a konkrét esetben legalább std::unordered_map-ot érdemes használni, mert a sima map ugyebár piros-fekete fa, tehát nem O(1) a beszúrás oda!
    - size_t helyett a feladatban sima int is elegendő ha a géped legalább 32 bites, mert 10 milliós szám abba azért bőven belefér. Így feleannyi adat van egyszerre adat cache-ben míg lesz reload (ezt javítottam).

    Ezt is implementáltam a "giga c++ forrásba" egy mérhető esetnek (lásd csatolt fájl), mind map-al, mind unordered_map-al.

    A futásidő eredmények a megoldásodra:

    [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 39980us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 40524us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 19418us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 17340us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 18090us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 13484us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 39432us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 13592us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 39186us
    Illetve ha std::unordered_map-ot használsz

    [prenex@magosit-laptop misc]$ g++ --std=c++20 -O2 harom_proba.cpp -o harom_proba.out [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 16787us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 16753us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 12032us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 10343us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 10087us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 10784us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 16960us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 16653us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 16515us

    Összefoglalva a sima std::map tehát ~10x lassabb, mint az egyedi algoritmus amit írtam és úgy 8x lassabb legalább a merge-es megoldáshoz képest. Itt a számok összevethetők az előző megjegyzésemben írtakkal.
    Ettől persze még bőven 0.1 másodperc alatt fut le sima std::map-os megoldás is, hiszen 40-ezer mikroszekundom még mindig tágasan alatta van a tizedmásodpercnek, bár azért a nagyságrendek kezdenek közelíteni szóval a futtató géptől is függ, hogy 100k fölé megy-e ugyebár.

    Ha unordered_map-ot használsz, de semmi mást nem változtatsz, akkor már a veszélyzónán biztos kívül esik a dolog, hiszen úgy lineáris újra az algoritmus az O(1) map beszúrási idő miatt, de a korábbi (akár stdlibes) összes többi megoldásnál ez azért még mindig lassabb.

    Viszont így már 4 különféle megközelítéssel is adtunk algoritmust amik mind-mind lefutnak bőven a határidő alatt

    ui.: Pár emberben felmerülhet, hogy "dehát miért nem hashmap az std::map alapból?" - erre azért gyorsan kitérnék, bár mindenki utána tud nézni: a sima map egy rendezett set / rendezett map, míg a másik nem, így használhatod ahol a másikat nem. Továbbá bizonyos elemszám alatt és bizonyos esetekben a hash-elés helyett kisebb konstans-ja is lehet a sima mapnak szóval nyilván van értelme. Az adat lokalitás is jobb egy bizonyos elemszámig, de ahogy nő a méret, egyre inkább unordered_map kell általában - mint ugyebár itt is
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Ha ennyire optimalizálsz, akkor miért nem O3-al fordítasz?
    Pl engem meglepne, ha a vector absztrakciónak lenne bármilére overhead-je normál pointeres eléréshez képest.
    Mutasd a teljes hozzászólást!
  • 0.) Bevezető

    Csináltam pár optimalizációt az enyémre. Először is vektorokra mutató pointer helyett már int* sima pointerek vannak és indexálás helyett a pointert mozgatom. Ez gyorsította a megoldásomat úgy 5-10%-al.

    Aztán kíváncsiságból elkezdtem gondolkozni a branchless programming megoldásokon. Ehhez először ki akartam mérni, hogy melyik branch-et hányszor kap el a proci az átlagos esetben a teljes futás alatt, hogy egyáltalán van-e esély ezzel dolgozni. Persze ekkor rögtön előjött, hogy a RandomBemenet elég speciális bemenetet generál (ami miatt anno worstProgrammer eredeti algoritmusán nem vette észre, hogy az hibás), így akkor azt is értelmesebbre írtam.

    1.) Branchless programming ötletek és tanulságok

    Próbáltam branchless kódolni a kise(), kozepese(), nagye() stb. függvényeket, ami külön kihívás volt és sikerült egy olyat csinálni, ami szinte azonos sebességű a kérdőjel-kettőspont operátorral, de azért mert szorzás van benne, sajnos lassabb, mint a jump, mivel csak az első pár esetet nyerjük meg, hiszen az, hogy mikor fogy el egy adott vektor egészen jól branch prediktálható... Mármint azért, mert a tényleg random bemeneten minden vektor elég hosszú lesz, tehát ott egész addig "jót" prediktál minden értelmes proci. Itt esetleg trükközhetek valamit, hogy olyan branchless kódot írjak, ami szorzás nélkül dolgozik és még mindig rövid, de elég necces... Van egy 10-20% esély, hogy ez még javítható, de meglepően kompakt a dolog. 

    Ezt követően a "rendbe" függvény, mini-buborék rendezését próbáltam branchless-é tenni. Ez lényegében sikerült is, sőt itt szorzás sincs és nagyon elegáns lett a branchless kód, szinte még látszik is miből lett (lásd csatolt forráskódban).

    Itt tehát az overhead kicsi, a branch predictor pedig kimértem: 40000x veszi az ifet és 130000x nem veszi be az ifet egy átlagos futásnál 100k elemen. Szóval elvileg itt nyerhetünk a dolgon ugye?

    NEM! 

    Azért nem tudunk nyerni rajta (hacsak nem régi és ratyi branch prediction-t használó gépen futtatod), mert NINCS ELSE ÁG, CSAK EGY IF ÁG. Az if ág törzse három soros és képzeljétek még a branchless változatban is három soros, csak kicsit bonyolultabb tömb indexálással (lásd forráskód). Szóval, ha a modern laptopomon így csinálom, akkor ez a megoldás lassabb mindkét worstProgrammer-féle megoldásnál... az ok prózaian egyszerű: az if törzse skippelve van 130k esetben és végrehajtva 40k esetben, míg a branchless kódnál a törzs bár ugyanolyan kicsi, de 170k esetben lesz végrehajtva és hiába nincs feltételes ugrás a kódban, ez így már sajnos ellensúlyozza azt amit nyerünk a dologgal.

    Esetleg próbálkozok branchless programozással a "leptet()" függvényben, ahol van pár rész, ahol else ága is van az elágazásnak, tehát ott talán valami hasonlóval akár nyerni is lehet valamit....

    2.) Inline-olás

    Ha már úgyis elkezdtem nézegetni a generált assembly-t, megnéztem a generált asm outputban és a gcc (se a clang) nekem nem inline-olja be a "rendbe(true)" hívást... ez szerintem tökre szomorú, mert nem szeretek gépelni és ezt a fordító az adott helyzetben láthatja, hogy oda tudná generálni...

    No de üsse kő, rátettem először az egész függvényre egy (gcc+clang)-specifikus __attribute__((always_inline)) módosítót, de úgy valamivel lassabb lett, ellenben ha csak a hívási helyen inline-olom (még mindig nem másolással, mert arra nem voltam hajlandó, hogy kopi pásztorkodjak csak ezért), szóval ha csak a "megismétlés" rekurzív hívását inline-olom, de a függvény külső hívását nem, akkor viszont gyorsabb lett, mint eredetileg volt. Kb arra számítottam a fordító alapból ezt generálja, de alulbecsültem. Ezzel lehetett még kb. 5% performanciát nyerni...

    3.) Egyszerűbb invariáns tartás

    ^^ezt még nem csináltam meg

    4.) Eredmények

    Saját algoritmus:

    [prenex@magosit-laptop misc]$ g++ --std=c++20 -O2 harom_proba.cpp -o harom_proba.out [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 2927us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 2573us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 1602us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 2571us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 2558us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 2642us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 2661us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 2632us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 2641us
    worstProgrammer-féle merge algoritmus:

    [prenex@magosit-laptop misc]$ g++ --std=c++20 -O2 harom_proba.cpp -o harom_proba.out [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 3979us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 3868us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 3843us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 3853us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 3861us
    worstProgrammer-féle range-set algoritmus (amit én már kijavítottam feljebb):

    [prenex@magosit-laptop misc]$ g++ --std=c++20 -O2 harom_proba.cpp -o harom_proba.out [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 5883us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 5877us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 5949us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 6024us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 6330us [prenex@magosit-laptop misc]$ ./harom_proba.out > /dev/null Took 6018us
    A fentiekhez képest azért mások a futásidők, mert ugyebár javítottam a random generált inputon (lásd csatolt forrás). Szóval a kimenetekben több a szumma elemszám. Viszont így, hogy többféle esetre futtatjuk, az enyém továbbra is egyértelműen gyorsabb a másik kettőnél. Néztem clang-al is, minimális eltéréssel kb. ugyanezt tapasztaltam...

    5.) Egyebek

    A **G**-féle negyedik módszert nem mértem még le, ezzel voltam "elfoglalva". Biztos lehet még préselni egy kis sebességet az enyémből, de meglepően optimális volt amit reflexből alapból írtam. Meglepne, ha az a mapos-setes cucc gyorsabb volna, mint lineáris tömb műveletek, de majd lemérem azért kíváncsiságból.

    A "branchless" technikákat (az egyik kódba van ott a másikat csak visszaírtam egy kommentbe) azért érdemes megnézni - hátha valaki nem látott még ilyet egyáltalán, hogyan is lehet kiszedni a feltételes ugrásokat a kódból... Tanulságos azért, hogy azt inkább akkor éri meg csinálni, ha nem csak if, de else ág is van (én ilyenre csináltam korábban meg egyszer egy hasonlót). Illetve persze mindig mérni kell a branchless-nél már... Az oké, hogy van sok optimalizáció amit séróból eleve "begépel" az ember megszokásból, de a branchless mondjuk nyilván alapból nem ilyen, csak ezt gondoltam azért megerősítem
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Ez egy nagyon hasznos honlap, itt mindent megtalálsz leírással és példákkal.
    std::sort
    Mutasd a teljes hozzászólást!
  • A változó csak a for cikluson belül van használva. Ennek megfelelően csak ott kéne láthatónak lennie.
    (for cikluson belül deklarálod)
    Mutasd a teljes hozzászólást!
  • És, hogy tudom minimalizálni a változók scope-ját?
    Mutasd a teljes hozzászólást!
  • Köszönöm a választ. Melyik az a kész rendező függvény?
    Mutasd a teljes hozzászólást!
  • 'Proba::Beolvas'

    * resize(0) helyett a clear valószínűleg kifejezőbb
    * elemszam és elem változók scope-ját minimalizálni kellene
    * az első while ciklusban effektíve egy kulcs szerint keresel
    Első észrevétel, hogy C++-ban a standard könyvtárban már implementálták neked a funkcionalitást.
    Sokszor kell egy adott érték szerint keresni, akkor érdemes lehet elgondolkodni, hogy ezt hogyan lehetne gyorsan csinálni.
    (Rendezett elemek között lehet menne gyorsabban?, Vajon van egyéb konténer, ami már megvalósítja számunkra a kívánt funkcionalitást? Van-e lehetőség direkt indexelésre?)
    * második for ciklus egy rendezés, erre is van stanardben kész függvény a számodra. Ha már rendezel, akkor lehetne úgy is, hogy a kiválogatás könnyebben menjen (multi érték szerint, azonos multi érték esetén, pedig 'ertek' szerint, így kapásból egymásmellé kerülnek és megfelelő sorrendben a kiírandó elemek..)

    'Proba::Kivalogat()'
    * egy újonan létrehozott objektumot miért resize-olsz 0-ra?
    * érdemes lehet megismerkedned a 'range based for' feature-el, olvashatóbbá teszi a kódod (for ciklus)
    * extra space miatt a sor végén nem hiszem, hogy érdemes bonyolítani a kiiratást..
    Mutasd a teljes hozzászólást!
  • Eléggé elbonyolítottátok.

    Szerintem csak azért, mert az a kód már három algoritmus egyben + időmérés :D

    Mármint a saját kódomon nem változtattam semmit az eredeti formájához képest, a másik két algoritmus meg 10-20 soros max pont mint a tied is (a tied nem mértem le, de ennyi).
    Mutasd a teljes hozzászólást!
  • Közben nekem is sikerült hatékonyabbá tenni. Viszont a beolvasás felől megközelítve. Lehetne ezen még valahogy hatékonyítani?

    void Proba::Beolvas() { cin >> N; int elemszam; int elem; elemek.resize(0); for (int k=0;k<3;k++) { cin >> elemszam; for (int i=0;i<elemszam;i++) { cin >> elem; int j = 0; while (j < elemek.size() && elemek.at(j).ertek != elem) { j++; } if (j < elemek.size()) { elemek.at(j).multi++; } else { MultiHalmazElem ujelem; ujelem.ertek = elem; ujelem.multi = 1; elemek.push_back(ujelem); } } } for (int i=1;i<elemek.size();i++) { MultiHalmazElem a; a = elemek.at(i); int j = i - 1; while (j >= 0 && elemek.at(j).ertek > a.ertek) { elemek.at(j+1) = elemek.at(j); j--; } elemek.at(j+1) = a; } } void Proba::Kivalogat() { vector <int> kesz; kesz.resize(0); for (int i=0;i<elemek.size();i++) { if(elemek.at(i).multi == 2) { kesz.push_back(elemek.at(i).ertek); } } cout << kesz.size() << endl; if (kesz.size() == 0) { cout << endl; } else { for (int i=0;i<kesz.size();i++) { if (i == kesz.size()-1) { cout << kesz.at(i) << endl; } else { cout << kesz.at(i) << " "; } } } }
    Mutasd a teljes hozzászólást!
  • Eléggé elbonyolítottátok. Ezt lehetne még tömörebben is írni for ciklusok helyet stl algoritmusokkal..

    #include <cstdint> #include <vector> #include <random> #include <algorithm> #include <iterator> #include <ranges> #include <iostream> #include <map> using namespace std; int main() { // Generate candidates that passed any of the tests.. vector<size_t> passed; ranges::generate_n( back_inserter(passed), 50'000, [](){ // uniform distr in range of candidate ids static uniform_int_distribution<> dist(0, 99'999); // random engine with seed static mt19937 rnd(20211127); return dist( rnd); }); // Construct map<size_t, uint8_t> perf; for (const auto& candidate : passed) { ++perf[ candidate]; } // Select where passed exactly 2 for (const auto& entry : perf) { if (entry.second == 2) { cout<<entry.first<<"\n"; } } // Construct2 vector<size_t> perf2( 100'000, 0u); ranges::for_each( passed, [&](size_t candidate){ ++perf2[ candidate];} ); ranges::copy_if( ranges::iota_view{0u, perf2.size()}, ostream_iterator<size_t>( cout, "\n"), [&](size_t id){ return perf2[id] == 2; }); }
    Mutasd a teljes hozzászólást!
  • Na... Éjjel már döcögött a prog.hu, de azt akartam írni a

    Az én megoldásomon nem optimalizáltam időközben - bár lehetne.

    Részhez, hogy azért tényleg semmi külön effort nem ment rá, hogy optimalizáljam is. csak a nagyon alap "megszokásból" optimalizálás van rajta - sőt abból is kifejezetten visszafogtam magam, mert például azért, hogy az algoritmust a kódot olvasva meg lehessen érteni (ez is a célom volt), nem nyers int* pointer van, hanem index + std::vector pointerek. Ez tök felesleges indirekció, de így, hogy külön vannak a vektorok szemléletesebb a kódom... Szintén gondolom nyilvánvaló, hogy a "rendbe()" függvénnyel tartani az invariánst iszonyatosan overkill dolog: azt csak az elején kéne így megcsinálni, de a léptetést meg lehet úgy írni, hogy az invariáns tartás az egyedi esetekre benne legyen - csak akkor nem jön át a tanító jellege a dolognak, mert sokkal nehezebb lenne követni mit csinálok és miért. A rendbe() invariánstartásos "pazarlás és lazzaság" valószínűleg, ami a legtöbbet hoz a konyhára, ha rendesen ki lenne helyette írva az egyes esetekre mit kell csinálni.

    Eddig az  rész amit még mindig séróból másként írtam volna, de "direkt" nem csináltam. A cache lokalitásnak (minden megoldásnál) jót tenne persze, ha közös tömbbe teszem a bemenetet eleve a beolvasásnál. Az int* pointeres megoldásnál eleve mindegy hol az adat, csak egyre kevésbé szemléletes a 3 "terület" amin az indexek / pointerek mozognak. A beépítetteknél az első pár művelet beizzítja az adat cache-t, szóval ez inkább az enyémnél lenne előny, hogy mindig több cache hit lenne így, bár nem számítok sok relatív gyorsulásra egy értelmes gépen. A következő dolog lenne branchless coding-al felcserélni a nagyon hot code path-okon az ifeket amennnyire lehet, hogy a branch predictor késései ne számítsanak, illetve meg lehet csinálni az alap optimalizációt is a maradék elágazásokra, hogy a ha van kifejezetten ritka ága, azt noinline flageljük és kiemeljünkfüggvénybe, hogy kompaktabb legyen az instruction cache.

    Eddig az a rész, ami "tuti hoz a konyhára" és ezen még mindig túl van az, amikor elkezdjük a perf és egyéb profilerekkel nézegetni a kimenetet illetve tényleg elkezdjük nézegetni az asm kimenetet, hogy hol nem azt csinálja a fordító, amit képzelek, vagy mi az, amit nem tud kioptimalizálni. Az ILP-n is biztos lehetne javítani még - esetleg akár azon az áron is, hogy spekulatíven csinálunk bizonyos dolgokat meg előre... A magyarsort-omnál például abban, hogy kis elemszámra is gyorsabb az std::sort-nál az ILP az egyik legfontosabb tényező, mert az a magyarsortban szinte tökkéletesen perfekt a procinak (bár ott ezt sikerült séróból úgy is írni anno). 

    Osztán afölött még hol van az a real_het féle szint, amikor az asm-ot konkrét géphez optimalizálja vagy intrinsic-ekkel, vagy kézzel - ez utóbbit production "széjjeloptimalizálásnál" se szoktam megcsinálni.

    De azért jó dolog a C++, mert arról beszélünk mi gyorsabb 100-500 mikro(!) szekundummal 100000-es elemszámra
    Sokszor nehéz is visszamenni dolgozni mindenféle bisznisz-nyelvbe ahol akkora konstansai vannak az algoritmusoknak, hogy 100 millisec-ben mérhető egy lineáris, vagy legalább amortizált lineáris cucc futásideje hasonló nagyságrenden csak legalább az algoritmus miatt jól skálázódik ha véletlen kap egy extra nagy bemenetet...


    No de ha jól látom van már itt vagy 3 megoldás, illetve van forráskód, ami egyszerre tartalmazza mindhármat, van pár attól eltérő másik, kevésbé kidolgozott ötlet is korábbról, viszont a kérdezőnek meg lába kélt, de mi jól elbeszélgetünk legalább itt a mikroszekundumokon, ami őt nem érinti  

    Amúgy nekem mindent összevetve a könnyű általánosíthatóság miatt persze ha nem csak a sebességet nézem, a merge-es megoldás tetszik a legjobban - ha így van megcsinálva, ha kézzel lekódolva.
    Mutasd a teljes hozzászólást!
  • No... Beraktam ezt is, most már tényleg nem néztem, hogy helyes-e, csak az időt és elég késő is van, de még mindig viszi az enyém, persze lehet hogy széjjel kell optimalizálni a megszámolást még jobban. Csatoltam a kódot.

    Eredmény a gépemen:

    [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 1597us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 574us [prenex@magosit-laptop misc]$ [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 573us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 1691us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 574us [prenex@magosit-laptop misc]$
    Ez már sokkal közelebb van az én megoldásomhoz, kb. úgy 100-200 us lassabb a gépemen. Az átlagos eset az enyémnél 450 körüli ennél meg 570 körüli és a kiugrásoknál is lassabb továbbra is. Igazából viszont mérési pontatlanság közelébe érkezünk lassan szerintem, meg itt már lehet hogy játszik, hogy kinek éppen milyen gépe van stb. (ezt most nem néztem meg mindenféle architektúrán pl. armon is összehasonlítva).

    A megoldásnak előnye, hogy jobban általánosítható: tehát azzal, hogy a merge lépést megcsináljuk, igazából meg lehet írni bármennyi próbára, illetve arra is, hogy "mennyi legyen pontosan ami abból sikerült is" szintén bármennyi lehet. Ezt meg is lehet akár template-ezni futási idő vesztés nélkül simán ennél. A másiknál kb. újraírós / átgondolós.

    Az időmérésnek nem része, a három külön vektorba betöltés, szóval szerintem az, hogy az elején összemásolom egybe nem jelent hátrányt az eredeti algoritmusommal szemben ennél az algoritmusnál, mert az valszeg csak 3 memcpy ami még a push-back-eknél is gyorsabb így, meg ugye a mérésen kívül van...

    Az én megoldásomon nem optimalizáltam időközben - bár lehetne. Csak az volt benne optimalizálva, ami anno "séróból adódott, de a megértést még extrémen nem befolyásolta".
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Na ennek már több értelme van szerintem. Mondjuk ennyi erővel el lehet kezdeni az enyém is "valóban" optimalizálni, hogy ne legyen ennyi branch benne, hanem kb. egy three-way merge-et csináljon, ami közben ezt eleve számolja

    De amúgy ott a kód, ne már nekem kelljen mindig belekopírozni az elképzeléseid, időt is mér, össze is hasonlíthatod, stb.
    Mutasd a teljes hozzászólást!
  • Meglepően keveset számított:

    [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 870us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 851us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 1487us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 863us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 2488us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 2379us [prenex@magosit-laptop misc]$
    900+ us -> 860-870 lement a gyorsabb eset és maradt lassú a lassabb méréseknél. Az enyém továbbra is 400-1100 között mozog és a 400+ fordul elő a legtöbbet.

    Felteszem az új kódot (csak a méréshez kikommentáltam a persze a #define SAJAT-ot, de visszaraktam utána, hátha valaki ezt akarja használni).
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Ha kijavítod, hogy kezelje ezt az esetet (tehát almát ne körtével hasonlítsunk), akkor is gyorsabb amúgy, mint az enyém? Mert szerintem úgy kellhet pár másik ilyen run, set_union is talán, stb.

    Ha úgy már nem gyorsabb, akkor a másik egyszerűbb megoldással próbálnám megoldani a feladatot. Ha olvasni kell az adatot (amik rendezve vannak) akkor egy összesített vektorba dobnám az elemeket insert + upper_bound majd a végén megszámolnám, hogy hánynál fordul elő, hogy 2 egyforma van egymás mellett.

    Ha már be van olvasva 3 különböző vektorba akkor átmásolnám őket egybe és inplace_merge.

    std::ranges::inplace_merge(v.begin(), v.begin() + bemenet.a.size(), v.begin() + bemenet.a.size() + bemenet.b.size()); std::ranges::inplace_merge(v.begin(), v.begin() + bemenet.a.size() + bemenet.b.size(), v.begin() + bemenet.a.size() + bemenet.b.size() + bemenet.c.size());
    Mivel előre tudható mennyi elem van, egy vector reservet azért bedobnék minden esetben :)
    Mutasd a teljes hozzászólást!
  • Tippre az időkülönbség nagyrésze vektor méretezéssel telik..
    Érdemes lehet úgy is megmérned, hogy előre méretezed a vectorokoat.
    (metszet nem lehet nagyobb, mint a kisebb elemszámú halmaz, ugyanígy unio-ra is tudsz megkötést..)
    Mutasd a teljes hozzászólást!
  • Most nem ellenőríztem le, de ha range-ekkel csinálsz valami kompexebbet, mint pl. ez:

    #ifdef SAJAT auto hp = HaromProba(&bemenet.a, &bemenet.b, &bemenet.c); std::vector<int> megoldas = hp.megold(); #else // SAJAT std::vector<int> vab, vac, vbc, vabc, vmix1, vmix2; std::vector<int> megoldas; std::ranges::set_intersection(bemenet.a, bemenet.b, std::back_inserter(vab)); std::ranges::set_intersection(bemenet.a, bemenet.c, std::back_inserter(vac)); std::ranges::set_intersection(bemenet.b, bemenet.c, std::back_inserter(vbc)); std::ranges::set_intersection(vab, bemenet.c, std::back_inserter(vabc)); std::ranges::set_union(vab, vac, std::back_inserter(vmix1)); std::ranges::set_union(vmix1, vbc, std::back_inserter(vmix2)); std::ranges::set_difference(vmix2, vabc, std::back_inserter(megoldas)); #endif // SAJAT
    Akkor ennél már például a "megoldás" (most független attól jó-e egyáltalán) máris lassabb, mint amit feljebb én írtam:

    [prenex@magosit-laptop misc]$ g++ --std=c++20 -O2 harom_proba.cpp -o harom_proba.out [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 933us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 922us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 931us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 2944us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 2561us [prenex@magosit-laptop misc]$
    Egy ilyesmi már 2x lassabb, mint az enyém - bár ha működik, akkor lehet vitázgatni melyik egyszerűbb, de szerintem az enyémet gondolatban könyebb azért követni, ha úgy tényleg megvan a koncepció, csak "begépelni" több idő. De lehet az enyémveb is van valami bug nem tagadom, de valszeg ha van is, akkor valami apróbb részletben. Mindenesetre a speed claim így már másképp fest ha jó ez a "javítás" a tiedhez, ha nem... Csak egyáltalán az időt mértem, mert érdekelt, valami ilyesmi kombónál kb. mik a futási idők.

    Feltettem a fájlt, ebbe belegányolhatod a megoldásaid jobban összehasonlítani...
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Most nem ellenőríztem le, de ha range-ekkel csinálsz valami kompexebbet, mint pl. ez:

    ... #ifdef SAJAT auto hp = HaromProba(&bemenet.a, &bemenet.b, &bemenet.c); std::vector<int> megoldas = hp.megold(); #else // SAJAT std::vector<int> vab, vac, vbc, vabc, vmix1, vmix2; std::vector<int> megoldas; std::ranges::set_intersection(bemenet.a, bemenet.b, std::back_inserter(vab)); std::ranges::set_intersection(bemenet.a, bemenet.c, std::back_inserter(vac)); std::ranges::set_intersection(bemenet.b, bemenet.c, std::back_inserter(vbc)); std::ranges::set_intersection(vab, bemenet.c, std::back_inserter(vabc)); std::ranges::set_union(vab, vac, std::back_inserter(vmix1)); std::ranges::set_union(vmix1, vbc, std::back_inserter(vmix2)); std::ranges::set_difference(vmix2, vabc, std::back_inserter(megoldas)); #endif // SAJAT ...
    Akkor ennél már például a "megoldás" (most független attól jó-e egyáltalán) máris lassabb, mint amit feljebb én írtam:

    [prenex@magosit-laptop misc]$ g++ --std=c++20 -O2 harom_proba.cpp -o harom_proba.out [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 933us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 912us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 931us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 2944us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 2561us [prenex@magosit-laptop misc]$
    Egy ilyesmi már 2x lassabb - bár ha működik, akkor lehet vitázgatni melyik egyszerűbb, de szerintem az enyémet gondolatban könyebb azért követni, ha úgy tényleg megvan a koncepció, csak "begépelni" több idő. De lehet ott is van bug nem tagadom. Mindenesetre a speed claim így már másképp fest ha jó ez a "javítás" a tiedhez, ha nem... Csak egyáltalán az időt mértem, mert érdekelt, valami ilyesmi kombónál kb. mik a futási idők.
    Mutasd a teljes hozzászólást!
  • Egyetlen szépséghibája (ami elég nagy), hogy az általad generált adatra működik csak (minden elem amiből kettő van az-az AB halmaz metzete, AC, BC metzer üres).

    Á, szóval írtál egy rossz megoldást amit gyorsabb, mint az enyém, ami (talán) jó, vagy ha rossz is legalább jóvá tehető ha elírtam valamit benne?

    Hopp. Ez mondjuk gáz, mármint az eredeti feladatot ez a range-es így nem oldja meg azért. Persze az enyémet se teszteltem a generált adatomon kívül, de az enyém elvileg az viszont azt tudja szépen, mert ugye folyamatosan forgatom a vektorokat azzal a három pointerrel és az invariáns helyesnek tűnik azokban az esetekben is, amit mondasz. Első blikkre azért jónak tűnt a range-es, de nyilván csak a saját cuccom néztem meg pontosabban - de még azt is sokkal felületesebben azért, mint amúgy normál kódnál szoktam, csak szerintem ott legalább ez kezelve van azért.

    Igazából csak a speed test méréshez generáltam ilyen egyszerű inputot én, de írtam is, hogy ez kb. nem megfelelő teszt minden esetre, csak arra figyeltem, hogy a kiírásnak megfelelő nagy inputot azért gyártsak...

    Ha kijavítod, hogy kezelje ezt az esetet (tehát almát ne körtével hasonlítsunk), akkor is gyorsabb amúgy, mint az enyém? Mert szerintem úgy kellhet pár másik ilyen run, set_union is talán, stb.
    Mutasd a teljes hozzászólást!
  • Na kimértem és tényleg gyorsabb a C++20as megoldás

    A saját az raw runtime-ba 470-1100-1500 mikroszekundom 100000 elemnél, a range-es megoldás meg 280-800-900 mikroszekundum (lásd alánt mérések). Viszont nekem a megoldásod nem azért lenne production-ready-bb mint az enyém, hanem mert a tied nehezebb elbaltázni, az enyémet meg könnyebb. De ettől még áll amit mondtam, hogy melyikkel mit tanulsz meg  

    [prenex@magosit-laptop misc]$ echo sajat sajat [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 1178us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 476us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 477us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 477us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 1590us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 1591us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 507us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 824us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 523us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 467us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 475us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 1217us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 668us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 475us [prenex@magosit-laptop misc]$ fg vim harom_proba.cpp [1]+ Megállítva vim harom_proba.cpp [prenex@magosit-laptop misc]$ g++ --std=c++20 -O2 harom_proba.cpp -o harom_proba.out [prenex@magosit-laptop misc]$ echo cpp20 cpp20 [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 282us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 926us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 389us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 279us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 280us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 917us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 282us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 285us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 287us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 287us [prenex@magosit-laptop misc]$ ./harom_proba.out < harom_proba_100k.txt > /dev/null Took 880us [prenex@magosit-laptop misc]$
    Mutasd a teljes hozzászólást!
  • Ezzel C++20-azni tanulsz, az enyémmel meg algoritmizálni tanulsz

    Van C++20 előtt is ilyen függvény, csak ott iterátorokat kell használni.

    De ez is szép megoldás persze.

    Egyetlen szépséghibája (ami elég nagy), hogy az általad generált adatra működik csak (minden elem amiből kettő van az-az AB halmaz metzete, AC, BC metzer üres).
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd