RLE dekomprese
asked 2014-11-28 11:27:50 +0100
Ahoj, progtest mi hazi:
"Test nahodnymi daty': Program překročil přidělenou maximální dobu běhu"
Realokuji tak, ze vzdy, kdyz narazim na cislo, zvetsim vystupni pole o hodnotu cisla. Muze to byt ten problem? (presna, ale prilis casta realokace)
A v zakladnim testu mam Využití paměti: 12712 KiB (limit: 13361 KiB).. je tohle normalni, nebo mate o hodne min? diky
Neznám zadání apod., ale přesná realokace je časově opravdu velmi drahá.
Miro Hrončok ( 2014-11-28 11:37:19 +0100 )editSouhlasím s @Miro Hrončok. Co si pamatuji, při realokaci je běžné pole zvětšovat o násobek jeho velikosti. Typicky 2x, pokud budou paměťové limity, tak třeba 1,5x ...
VojtechMyslivec ( 2014-11-28 12:52:40 +0100 )editAlokace je vždy velmi výpočetně náročná, a většinou i paměťově. Pokud máte úlohu jako RLE, tak bych se skoro vsadil, že vyjde výkonnostně lépe projít vstup dvakrát - v jednom průchodu spočítat velikost, potom udělat jednu alokaci, potom v druhém průchodu naplnit data (a možná bych ten druhý průchod dělal v "obráceném pořadí", tzn. od konce). Není to zrovna čistá technika, ale pro toto zadání pravděpodobně bude rychlejší než jednoprůchodové řešení. Extrémní případy typu "vstup úplně bez komprese" (resp. vstup s několika málo případy komprese) lze řešit počítáním, na které pozici je první resp. poslední komprimovaný bajt (abych při druhém průchodu mohl na bajty od začátku do prvního kopírovaného resp. od posledního komprimovaného do konce použít obyčejné memcpy, které je mnohem rychlejší než kopírování po bajtech).
Josef Kokeš ( 2014-11-28 14:19:30 +0100 )editNedávno jsme to s někým řešil: Jde projít vstup ze stdin víckrát?
Miro Hrončok ( 2014-11-28 16:55:41 +0100 )editJde, pokud vstupem je soubor a nikdo do něj nezapisuje - tzn. není to spolehlivé. Ale vycházím ze zadání postnutého na Fit Wiki, kde o standardním vstupu není ani slovo - vstupem je ukazatel na ASCIIZ řetězec. Nevidím důvod, proč bych tohle nemohl projít víckrát.
Josef Kokeš ( 2014-11-28 16:59:52 +0100 )edit