Zadani prece nebylo jine - zadani se zmenilo v prubehu debaty a az po mem prispevku. To je velky rozdil.
Vy jste vážně hrozně naivní. Ne, to zadání nebylo jiné a nezměnilo se. Jenom bylo chybně formulované – tak, jako naprostá většina zadání.
Vyraz "vyssi sptreba pameti" se vztahuje k jiz obsazene pameti.
Ne, nevztahuje. Vyšší spotřeba paměti se vztahuje k jiným algoritmům ve stejném okamžiku běhu. A jiný algoritmus umí po skončení mazání mít méně obsazené paměti, než váš algoritmus.
A jak jiz bylo drive zmineno, je to vlastnosti ArrayListu, ze se nasledne po operaci, ktera ma vliv na jeho velikost (zmensi se), muze zavolat metoda, ktera podkladove pole prealokuje. Ale tato operace by se nemela nemela volat vzdy, ale podle pravidel implementace ArrayListu. Vsechno toto jsem jiz drive napsal. A proc takto (podle pravidel prace ArrayListu s podkladovym polem) zmenseni podkladoveho pole neresim? Protoze resim pouze onen problem odmazani prvku z listu a povazuji problem zmenseni podkladoveho pole za marginalni - neprispivam tim prece do JDK, kde bych toto jiz resil zcela zodpovedne.
Vlamujete se do otevřených dveří. Já jsem nikde nepsal, že je z tohoto pohledu váš kód špatně. Pouze jsem ukázal, že existuje paměťově efektivnější algoritmus, čímž jsem vyvrátil vaše tvrzení, že váš algoritmus je nejefektivnější možný. Mimochodem, už jenom to, že existují dva mírně odlišné algoritmy, z nichž jeden je paměťově efektivnější, ale druhý je v obecném případě správnější, svědčí o tom, že všeobecné prohlášení „nejefektivnější možný“ algoritmus je prostě nesmysl, protože – jako už jsem napsal několikrát – můžete porovnávat různé efektivity. Pokud máte problém představit si to na algoritmech, nechte si na nějaké mapě naplánovat cestu autem z bodu A do bodu B. Uvidíte, že budete mít na výběr minimálně ze dvou variant – nejrychlejší a nejkratší. Je nějaká z nich obecně nejefektivnější?
Napsal jsem, ze je "maximalne efektivni". A mel jsem tim na mysli pametovou a vypocetni slozitost - tedy ta zakladni kriteria hodnoceni algoritmu.
Pardon, ale toho, ze jste to vyvratil, jsem si nevsiml.
Pokud jste tím myslel, že je algoritmus efektivní z hlediska obou základních kritérií, měl jste to napsat. Ono je totiž typické, že snižování výpočetní složitosti zvyšuje paměťovou náročnost a opačně. Ostatně jako v tomto případě – výpočetní složitost můžete snížit tím, že prostě alokujete nové pole o stejné velikosti a pak zkopírujete prvky, které se nemají smazat. Ale paměťovou náročnost tím zdvojnásobíte.
Maximální efektivitu jsem vyvrátil jednoduše tak, že jsem předvedl algoritmus, který má nižší výpočetní složitost, a algoritmus, který má nižší paměťovou náročnost.
Ale ne...copak native metoda je optimalizovana JITem? :-)
Nemyslím si, že by ve standardu bylo uvedeno, jak přesně má být implementována metoda
System.arraycopy.
Presouvat bloky pole o male delce potencialne pres docasne jednorazove alokovane pole se vam zda v poradku?
Potenciálně přes dočasné jednorázově alokované pole může být klidně implementováno i to vaše přiřazování. To, že je v dokumentaci napsáno „chování je ekvivalentní k“ neznamená, že to tak musí být opravdu implementováno.
Tady uz pomuze pouze benchmark, jinak je to pouze akademicka debata. Tak si to prosim zkuste, jestli volani arracopy pro kopirovani prvku po jednom (resp. pro jak velke pole se to jeste vyplati a) je rychlejsi nez pure Java prirazeni prvku
do pole.
Vy se zkuste zamyslet nad tím, jak velká je pravděpodobnost, že při náhodném rozložení mazaných indexů se budou mazat všechny sudé nebo všechny liché prvky.
Ano. A ja jsem jiz drive take napsal, ze jsem na tomto foru reagoval proto, ze se mi to zadani libilo a zdalo se mi zajimave. Proto jsem prispel. Pokud bych vedel, ze bude stacit cyklicke volani ArrayList.remove(), tak bych se opravdu neobtezoval :-).
V pořádku. Mně zase přišlo zajímavé vaše sebejisté tvrzení, že vaše řešení je maximálně efektivní. Dalo se předpokládat, že nebude problém dokázat, že existuje paměťově efektivnější nebo výpočetně efektivnější řešení – nakonec se ukázalo, že existují obě.
Podstatou problemu byla prace s ArrayListem a to neni rozhrani.
To, že je použitý
ArrayList, málokdy bývá vytesáno do kamene. Pokud se ukáže, že
ArrayList není nejvhodnější struktura, bývá možné použít jinou strukturu. Navíc
ArrayList není finální třída, takže implementaci potomka nestojí nic v cestě. Když tedy chcete slovíčkařit.
54 Odpovědí
32229 Zhlédnutí