reklama

Java - jak vymazat z ArrayListu množinu položek

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #30 kdy: 23. 09. 2019, 14:51:38 »
Presne zadani jsem ocekaval v prvnim prispevku tohoto fora.
To je dost naivní…

Ponechava puvodni velikost podkladoveho pole a povazuji to za dobrou vlastnost.
Já to také považuji za dobrou vlastnost, většinou to bude nejlepší řešení. Ale ne vždy – a přesné zadání neznáme.

Dovoluji si tvrdit, ze to je maximalne efektivni algoritmus proto, ze pouziva pouze pristup do 2 poli pres index a jeho narocnost neni vyssi nez narocnost jednoho pruchodu podkladoveho pole. Pokud nemam pravdu, tak by to chtelo necim konkretnim dolozit (efektivnejsim algoritmem, at to neni pouze akademicka debata).
Doložil jsem to už v původním příspěvku. Nelze o algoritmu tvrdit, že je „obecně efektivní“ – je velmi časté, že algoritmy efektivní na počet instrukcí nebo na strojový čas mají vyšší spotřebu paměti a naopak.

Původně mi šlo hlavně o to obecné tvrzení, ale když tak toužíte po tom vědět, proč váš algoritmus není ani maximálně efektivní vzhledem k době běhu, máte to mít. Na vašem algoritmu je výpočetně neefektivní to, že kopírujete prvky po jednom. Pokud bude v poli za sebou víc prvků, které se mají zachovat, je efektivnější zkopírovat („posunout“) celý souvislý blok najednou. Záleží na přesné implementaci funkce System.arraycopy, jestli dokáže celý blok posunout jedním směrem bez vytváření dočasného pole.

Dalsi uvadene zpusoby zalozene na kopirovani (neodstranuje elementy a dopredu nevime jako bude mit vysledny list velikost, pouze ze bude mensi nebo stejne velky - opet skryte kopirovani pole pri rustu velikosti vysledneho listu)
Velikost výsledného listu dopředu víme. Kopírování do nového pole by mohlo být na procesorový výkon i efektivnější, než vaše řešení – protože umožní vždy kopírovat celé souvislé bloky, nebo-li je nezávislé na efektivitě implementace System.arraycopy.

Odstranovani pro kazde volani posouva zbytek pole za odstranenym elementem.
To nikdo nezpochybňuje. Ale to, že vaše řešení je lepší, než jiné, ještě neznamená, že je maximálně efektivní…

reklama


gill

  • ***
  • 190
    • Zobrazit profil
    • E-mail
Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #31 kdy: 23. 09. 2019, 20:26:30 »
Pomocí streamů:

Kód: [Vybrat]
List<String> arrList = new ArrayList<>();
arrList.add("a");
arrList.add("b");
arrList.add("c");
arrList.add("d");

Integer[] indexes = { 1, 3 };
List<Integer> indexesList = Arrays.asList(indexes);
List<String> withItemsRemoved = arrList.stream().filter(i -> !indexesList.contains(arrList.indexOf(i)))
.collect(Collectors.toList());
System.err.println(withItemsRemoved);

Output: [a, c]

Samozřejmě je nutné vzít v potaz kontext, ve kterém se tahle akce provádí a případně použít jiné performantnější řešení.

tohle je špatně a pomalé. Nebude to fungovat, když se v tom arraylistu opakují hodnoty. Správný přístup by asi byl vytvořit pole indexů, to přefiltrovat a následně namapovat prvky z toho původního arraylistu. Ale, je to zbytečně komplikované. V Javě je stručnější normální imperativní přístup.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #32 kdy: 23. 09. 2019, 22:59:40 »
To je dost naivní…

Jestli je to naivni nebo ne povazuji za vec nazoru. Me to zadani prislo OK. Zpochybnovat se da vse a vzdy, ale nerekl bych, ze to nekam povede.

Doložil jsem to už v původním příspěvku. Nelze o algoritmu tvrdit, že je „obecně efektivní“ – je velmi časté, že algoritmy efektivní na počet instrukcí nebo na strojový čas mají vyšší spotřebu paměti a naopak.

Tady ale vyssi spotreba pameti neni (nealokuje se zadna dalsi pamet na heapu) a procesorovy cas je take OK a srazit ho pod jeden pruchod listu s daty myslim si ze nejde. Tento algoritmus neni obecny, ale zcela konkretni a proto muzu byt konkretni i ve svem tvrzeni.

Původně mi šlo hlavně o to obecné tvrzení, ale když tak toužíte po tom vědět, proč váš algoritmus není ani maximálně efektivní vzhledem k době běhu, máte to mít. Na vašem algoritmu je výpočetně neefektivní to, že kopírujete prvky po jednom. Pokud bude v poli za sebou víc prvků, které se mají zachovat, je efektivnější zkopírovat („posunout“) celý souvislý blok najednou. Záleží na přesné implementaci funkce System.arraycopy, jestli dokáže celý blok posunout jedním směrem bez vytváření dočasného pole.

No vidite, v podstate si sam odpovidate :-). Pokud neumim predem efektivne zjistit, zda se System.arraycopy rozhodne v pripade src==dest delat docasne pole, pak je lepsi ho nepouzit a nechat JIT at to za nas zaridi.

Ale jako napad na zrychleni se mi to libi a je to dobry pokus. Staci indexy premapovat na velikost "diry". Pokud by se dalo zjistit, zda to pujde presunout jako blok, pak pouziti System.arraycopy() je vyhodne. Ale...umite to? A neposkodi to prenositelnost? A melo by to byt v odpovedi na tomto foru? :-)

Velikost výsledného listu dopředu víme. Kopírování do nového pole by mohlo být na procesorový výkon i efektivnější, než vaše řešení – protože umožní vždy kopírovat celé souvislé bloky, nebo-li je nezávislé na efektivitě implementace System.arraycopy.

Vytvoreni noveho listu hodnot jsem jiz argumentoval drive tim, ze v zadani bylo prvky smazat, tak je mazu a nevytvarim novy list.

Pokud bych mohl vytvorit nove podkladove pole pro stejny list, pak by to v principu bylo mozne bez vytvoreni nove instance, ale obavam se, ze to take nepujde nebo to nebude dobre reseni. ArrayList neni zase az tak "otevreny".

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #33 kdy: 24. 09. 2019, 13:44:31 »
Jestli je to naivni nebo ne povazuji za vec nazoru. Me to zadani prislo OK. Zpochybnovat se da vse a vzdy, ale nerekl bych, ze to nekam povede.
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.

Tady ale vyssi spotreba pameti neni (nealokuje se zadna dalsi pamet na heapu) a procesorovy cas je take OK a srazit ho pod jeden pruchod listu s daty myslim si ze nejde. Tento algoritmus neni obecny, ale zcela konkretni a proto muzu byt konkretni i ve svem tvrzeni.
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.

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.

No vidite, v podstate si sam odpovidate :-). Pokud neumim predem efektivne zjistit, zda se System.arraycopy rozhodne v pripade src==dest delat docasne pole, pak je lepsi ho nepouzit a nechat JIT at to za nas zaridi.
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 jako napad na zrychleni se mi to libi a je to dobry pokus. Staci indexy premapovat na velikost "diry". Pokud by se dalo zjistit, zda to pujde presunout jako blok, pak pouziti System.arraycopy() je vyhodne. Ale...umite to? A neposkodi to prenositelnost? A melo by to byt v odpovedi na tomto foru? :-)
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í.

Vytvoreni noveho listu hodnot jsem jiz argumentoval drive tim, ze v zadani bylo prvky smazat, tak je mazu a nevytvarim novy list.
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.

Pokud bych mohl vytvorit nove podkladove pole pro stejny list, pak by to v principu bylo mozne bez vytvoreni nove instance, ale obavam se, ze to take nepujde nebo to nebude dobre reseni. ArrayList neni zase az tak "otevreny".
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.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #34 kdy: 24. 09. 2019, 14:37:07 »
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.

reklama


Kit

  • ***
  • 244
    • Zobrazit profil
    • E-mail
Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #35 kdy: 24. 09. 2019, 15:49:58 »
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.

Správně. Když mám v ruce kladivo, všechno najednou vypadá jako hřebík

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #36 kdy: 24. 09. 2019, 22:56:50 »
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.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #37 kdy: 24. 09. 2019, 23:39:25 »
Nerad rusim vysoce abstraktni debaty, ale IMHO bude nejefektivnejsi prosty pristup puvodniho tazatele, kdy vytvari novy arraylist kopii dat z puvodniho.

A to z toho prosteho duvodu, ze se jedna o shallow copy, na objekty uvnitr array listu (tipuju nejake beany) se nijak nesaha, pouze se vyrobi nove pole s referencema na puvodni objekty (kryci nazev arraylist), kde budou obsazeny pouze pozadovane reference.

A az se puvodni arraylist descopuje, zmizej i reference na vyhozene objekty, garbage collector to pozere.

Hotovo, veru neni potreba vyrabet selmostroje s kopirovanim nalezenych bloku.
Jednoduche, ucinne, proto mame jawu radi.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #38 kdy: 25. 09. 2019, 22:21:51 »
Nerad rusim vysoce abstraktni debaty, ale IMHO bude nejefektivnejsi prosty pristup puvodniho tazatele, kdy vytvari novy arraylist kopii dat z puvodniho.

A to z toho prosteho duvodu, ze se jedna o shallow copy, na objekty uvnitr array listu (tipuju nejake beany) se nijak nesaha, pouze se vyrobi nove pole s referencema na puvodni objekty (kryci nazev arraylist), kde budou obsazeny pouze pozadovane reference.

A az se puvodni arraylist descopuje, zmizej i reference na vyhozene objekty, garbage collector to pozere.

Hotovo, veru neni potreba vyrabet selmostroje s kopirovanim nalezenych bloku.
Jednoduche, ucinne, proto mame jawu radi.
Tím, co jste napsal, jste ale nijak nedokázal, že ten postup bude nejefektivnější. Postup s přesouváním bloků totiž také jenom přesouvá reference – ono totiž v Javě ani nemáte jak kopírovat „hodnoty“ objektů, máte k dispozici jenom reference.

Postup s vytvořením nového pole je pravděpodobně implementačně nejjednodušší a pokud můžete vytvořit novou instanci Listu a tu vrátit, považoval bych takové řešení (pokud nemáme nějaké další zpřesňující podmínky) za nejlepší. Ale je spousta případů, kdy už jste referenci na ten List někam předal a potřebujete, aby se i tam pracovalo s tím promazaným seznamem – potřebujete tedy ten List promazat in-place.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #39 kdy: 26. 09. 2019, 12:26:43 »
Nerad rusim vysoce abstraktni debaty, ale IMHO bude nejefektivnejsi prosty pristup puvodniho tazatele, kdy vytvari novy arraylist kopii dat z puvodniho.

A to z toho prosteho duvodu, ze se jedna o shallow copy, na objekty uvnitr array listu (tipuju nejake beany) se nijak nesaha, pouze se vyrobi nove pole s referencema na puvodni objekty (kryci nazev arraylist), kde budou obsazeny pouze pozadovane reference.

A az se puvodni arraylist descopuje, zmizej i reference na vyhozene objekty, garbage collector to pozere.

Hotovo, veru neni potreba vyrabet selmostroje s kopirovanim nalezenych bloku.
Jednoduche, ucinne, proto mame jawu radi.
Tím, co jste napsal, jste ale nijak nedokázal, že ten postup bude nejefektivnější. Postup s přesouváním bloků totiž také jenom přesouvá reference – ono totiž v Javě ani nemáte jak kopírovat „hodnoty“ objektů, máte k dispozici jenom reference.

Postup s vytvořením nového pole je pravděpodobně implementačně nejjednodušší a pokud můžete vytvořit novou instanci Listu a tu vrátit, považoval bych takové řešení (pokud nemáme nějaké další zpřesňující podmínky) za nejlepší. Ale je spousta případů, kdy už jste referenci na ten List někam předal a potřebujete, aby se i tam pracovalo s tím promazaným seznamem – potřebujete tedy ten List promazat in-place.

Modifikovat ArrayList, ktery jsem nekam poslal, je naprosto spolehliva cesta do zadeke.
Pokud ta vzdalena strana bude mit nad arraylistem otevreny Iterator, padne to cele na hubu na ConcurrentModificationException.

https://www.journaldev.com/378/java-util-concurrentmodificationexception

Pokud bude pristupovat pres indexy, vznikne nahodny chaos, obcas prolozeny IndexOutOfBoundException.

Problemy tototo typu osobne resim Spring Beanem instaciovanym v potrebnem scope, ktery ma ArrayList jako svuj atribut s pruslusnymi synchronizovanymi gettery plus ona metoda na odstraneni polozek pomoci pole indexu.
A tato metoda provede v ramci synchronized bloku provede vytvoreni noveho arraylistu ktery zase povesi na pristusny atribut beanu.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #40 kdy: 26. 09. 2019, 16:03:34 »
Modifikovat ArrayList, ktery jsem nekam poslal, je naprosto spolehliva cesta do zadeke.
Pokud ta vzdalena strana bude mit nad arraylistem otevreny Iterator, padne to cele na hubu na ConcurrentModificationException.

Nikde nebyla zminka o soubeznem zpracovani vice vlakny, tak je zbytecne to dovozovat. Predpokladejme pouze existujici referenci.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #41 kdy: 26. 09. 2019, 16:08:51 »
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.

Porad predpokladate, ze jste neco dokazal, ale ja zde na foru zadny vas algoritmus nebo modifikaci meho algoritmu nevidim.

Dodejte svoji implementaci a pak se muzeme bavit dal nad benchmarkem techto dvou implementaci.
Do te doby povazuji pokracovani teto diskuse s vami za bezpredmetne.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #42 kdy: 26. 09. 2019, 16:11:19 »
Modifikovat ArrayList, ktery jsem nekam poslal, je naprosto spolehliva cesta do zadeke.
Přesto se to dělá – říká se tomu programování. Modifikovat ArrayList, který nikdo nepoužívá, je totiž k ničemu.


Pokud ta vzdalena strana bude mit nad arraylistem otevreny Iterator, padne to cele na hubu na ConcurrentModificationException.

Pokud bude pristupovat pres indexy, vznikne nahodny chaos, obcas prolozeny IndexOutOfBoundException.
Jinými slovy, pokud bude programátor špatně používat nástroje, bude to špatné. Nu – ano. Programátor by měl vědět, jak se ten ArrayList používá, jaké jsou s ním spojené invarianty, a podle toho se k němu chovat. Dokonce k tomu bylo vymyšleno i programovací paradigma – objektové programování. Datové struktury (zde ArrayList) se schovají dovnitř objektů, a komunikuje se s nimi jenom prostřednictvím volání metod těch objektů. V ideálním případě ty implementace těch metod zajistí dodržování těch invariantů – nebo tomu alespoň pomůže.

Problemy tototo typu osobne resim Spring Beanem instaciovanym v potrebnem scope, ktery ma ArrayList jako svuj atribut s pruslusnymi synchronizovanymi gettery plus ona metoda na odstraneni polozek pomoci pole indexu.
A tato metoda provede v ramci synchronized bloku provede vytvoreni noveho arraylistu ktery zase povesi na pristusny atribut beanu.
Ano, to je krásný příklad strukturovaného programování. Jak jsem psal, dá se to naprogramovat i objektově, strukturu ArrayList vůbec nevystavovat a přistupovat k ní pouze pomocí metod, které budou dělat právě to, co se s tím ArrayListem má dělat.

gill

  • ***
  • 190
    • Zobrazit profil
    • E-mail
Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #43 kdy: 26. 09. 2019, 16:13:21 »
dlouhá diskuze, zatím tu nezanělo žádné krátké řešení s vytvořením nového arraylistu. Rád bych viděl jednořádkový Java kód, který dělá to stejné co moje řešení v Kotlinu.

Re:Java - jak vymazat z ArrayListu množinu položek
« Odpověď #44 kdy: 26. 09. 2019, 16:19:25 »
Nikde nebyla zminka o soubeznem zpracovani vice vlakny, tak je zbytecne to dovozovat. Predpokladejme pouze existujici referenci.
ConcurrentModificationException ale může vypadnout i v jednovláknové aplikaci. Připadá mi to jako dost základní znalost.

Porad predpokladate, ze jste neco dokazal, ale ja zde na foru zadny vas algoritmus nebo modifikaci meho algoritmu nevidim.
Vy zase předpokládáte, že co nevidíte, to neexistuje. Já jsem tady ale modifikaci vašeho algoritmu popisoval.

Dodejte svoji implementaci a pak se muzeme bavit dal nad benchmarkem techto dvou implementaci.
Já zase nevidím, že byste tu někde popisoval konkrétní benchmark. Původní dotaz byl velmi vágní, můžete vymyslet asi tak milion různých benchmarků, a každý vám vyjde jinak.

Akorát potvrzujete, že vám výpočetní složitost mnoho neříká. Nejdřív jste přišel s obecným tvrzením, že váš algoritmus je maximálně efektivní (tedy ze všech možných hledisek a ve všech možných případech), a teď to chcete dokazovat jedním benchmarkem.

Já bych to uzavřel tím, že váš algoritmus je pro potřeby tazatele dobrý, a do dalšího teoretizování o něm se raději nepouštějte.

 

reklama