Jenže se ukázalo, že zadání ve skutečnosti bylo jiné, než jste si myslel. Takže zpochybnění zadání v tomto případě vedlo k nalezení vhodného řešení – podle mne je to dobrý výsledek.
Zadani prece nebylo jine - zadani se zmenilo v prubehu debaty a az po mem prispevku. To je velky rozdil.
Je pozoruhodné, jak se ve vašich komentářích snoubí správný algoritmus použitý pro danou věc s absolutní neznalostí obecnějších principů. Když máte pro něco alokované větší pole, než je potřeba, vyšší spotřeba paměti tam samozřejmě je. To, že ta paměť už byla alokovaná dříve, na věci nic nemění – potřeba paměti je závislá na čase, neřeší se jenom maximum. Vašemu algoritmu možná ta nevyužitá paměť nijak nechybí, ale jiný algoritmus nebo proces by jí třeba využil – a v extrémním případě ta vámi nevyužitá paměť může způsobit třeba swapování nebo i pád aplikace, která by potřebovala alokovat další paměť, která ale není k dispozici.
Myslim, ze jste to nepochopil, protoze jinak by jste nekombinoval vice veci dohromady, ktere by se mely resit separatne. Vyraz "vyssi sptreba pameti" se vztahuje k jiz obsazene pameti. Tedy ze nedochazi k zadne dalsi alokaci pameti na heapu - jak jsem jiz drive napsal. Zatimco zminene algoritmy nejakou tu (nezanedbatelnou vzhledem k pametove narocnosti) pamet otoci a z heapu alokuji a castecne ji vrati. 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.
Vy jste ve svém tvrzení nebyl vůbec konkrétní, právě naopak. Napsal jste, že váš algoritmus je nejefektivnější možný – tedy obecně, ve všech kritériích. Nelze napsat algoritmus, který by spotřeboval méně paměti ani algoritmus, který by spotřeboval méně procesorového času. Přitom obojí jsem vyvrátil – váš algoritmus tedy zjevně nejefektivnější možný není. Je možné, že v některých případech je nejefektivnější z hlediska procesorového času – za cenu paměťové neefektivity.
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.
Kdybyste použil System.arraycopy(), necháváte to na JIT. V nejhorším případě udělá to, co vy jste naprogramoval ručně. Ale může to udělat i efektivněji. Vy jste ale VM nadiktoval svůj (nejpomalejší) způsob přesouvání bloků pole, s tím už JIT nic neudělá.
Ale ne...copak native metoda je optimalizovana JITem? :-)
Jasně že to umím, vždyť je to triviální. Jako blok to přesunou jde vždy. V nejhorším případě budete přesouvat bloky o délce jedna. Což by se dalo oifovat, ale to bych považoval ze typickou předčasnou optimalizaci. Přenositelnost to v žádném případě nepoškodí.
Presouvat bloky pole o male delce potencialne pres docasne jednorazove alokovane pole se vam zda v poradku? 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.
Já už jsem vám na to odpovídal, že je naivní očekávat, že to zadání bylo takhle přesné. Ostatně jak se později ukázalo, vytvoření nového listu bylo akceptováno jako vhodné řešení – tedy to „mazání“ byl pouze laický neprogramátorský popis, bylo to jen jinak napsáno „chci, abych měl na konci list, kde nebudou prvky se zadanými indexy“. Jedna z nejdůležitějších věcí, které je potřeba se naučit ohledně analýzy problémů, je následující: To, co někdo chce, a co tvrdí, že chce, jsou obvykle dvě naprosto odlišné věci.
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 :-).
Proto je výhodné programovat proti rozhraním, protože pak i tu uzavřenost ArrayListu můžete snadno obejít tím, že si vytvoříte vlastní implementaci Listu, která uvnitř vymění celý ArrayList.
Podstatou problemu byla prace s ArrayListem a to neni rozhrani.
Zobrazit příspěvky
