Fórum Root.cz

Hlavní témata => Vývoj => Téma založeno: karelguth 20. 09. 2019, 07:48:12

Název: Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: karelguth 20. 09. 2019, 07:48:12
Mám nějaký ArrayListový seznam a k němu jsem dostal jsem dostal pole, které obsahuje indexy, jež určují, které prvky se z ArrayListového seznamu mají vymazat. Když ale začnu v cyklu promazávat ten seznam, tak dojde k rozhození indexace a tím pádem jsou ty původní indexy neplatné.

Existuje nějaký způsob, jak rychle naráz vymazat určité prvky z ArrayListu, které jsou specifikovány nějakou množinou prvků?
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: tecka 20. 09. 2019, 08:23:17
Když ty indexy seřadíš, tak při procházení od nejmenšího víš, o kolik jsou ty další posunuté, nebo při procházení od nejvyššího tě posunutí netrápí. Jak se na tohle můžeš ptát?
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Ondra Satai Nekola 20. 09. 2019, 09:06:56
Opakovaně mazat uprostřed ArrayListu je dost neefektivní.

Chceš promazat ten původní nebo ti stačí vytvořit nový s příslušným obsahem? To druhé je snadné.

Je docela dobře možné, že bude efektivní i udělat nový a jeho obsahem pak překropit ten starý, ale tam by to chtělo detaily a měření.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Standa Blábol 20. 09. 2019, 15:40:30
Bud si proste vyrob novy arraylist zkopirovanim dat ve foreach cyklu, kde key not in keylist. Keylist array si preved na arraylist a pouzij contains().
Tenhle pristup je vhodny, pokud pocet klicu > polovina delky arraylist


Nebo si vyrob pomocny arraylist pro vsechny keys z keylistu a na puvodnim arraylistu zavolej removeAlll()
Tehnle pristup je vhodny pokud je pocet klicu maly vzhledem k delce arraylistu.

Nepredpokladam, ze resis kazdou milisekundu, to by nebyly daove struktury tak blbe navrzene.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Zabanovaný Anonymní Troll 20. 09. 2019, 18:05:44
Strc ten arraylist do hashmapy, a v hashmape uz pak muzes mazat prvky dle klice.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Idris 20. 09. 2019, 18:24:12
Strc ten arraylist do hashmapy, a v hashmape uz pak muzes mazat prvky dle klice.
Taky by si ho mohl strčit do Fibonacciho haldy.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 21. 09. 2019, 02:32:34
Mám nějaký ArrayListový seznam a k němu jsem dostal jsem dostal pole, které obsahuje indexy, jež určují, které prvky se z ArrayListového seznamu mají vymazat. Když ale začnu v cyklu promazávat ten seznam, tak dojde k rozhození indexace a tím pádem jsou ty původní indexy neplatné.

Existuje nějaký způsob, jak rychle naráz vymazat určité prvky z ArrayListu, které jsou specifikovány nějakou množinou prvků?

 ;)


   public static void main(final String[] args) {
      final ArrayList<Object> arrayList = new ArrayList<Object>(Arrays.asList("a", "b", "c", "d", "e"));
      System.out.println(arrayList);
      final int[] toRemoveIdxs = new int[]{0, 3, 1, 5};
      Arrays.sort(toRemoveIdxs); // pokud toRemoveIdxs jsou nesetrizeny
      
      { // algoritmus odstraneni podle indexu
         int cnt = 0;
         for (int i = 0, toRemovePtr = 0; i < arrayList.size(); i++) {
            if (cnt > 0) {
               arrayList.set(i - cnt, arrayList.get(i));
            }
            if (toRemovePtr < toRemoveIdxs.length) {
               int toRemoveIdx = toRemoveIdxs[toRemovePtr];
               if (toRemoveIdx == i) {
                  cnt++;
                  toRemovePtr++;
               }
            }
         }
         // odseknu zbytek
         arrayList.subList(arrayList.size() - cnt, arrayList.size()).clear();
      } //

      System.out.println(arrayList);
   }

Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Ondrej Nemecek 21. 09. 2019, 15:08:19
Mám nějaký ArrayListový seznam a k němu jsem dostal jsem dostal pole, které obsahuje indexy, jež určují, které prvky se z ArrayListového seznamu mají vymazat. Když ale začnu v cyklu promazávat ten seznam, tak dojde k rozhození indexace a tím pádem jsou ty původní indexy neplatné.

Existuje nějaký způsob, jak rychle naráz vymazat určité prvky z ArrayListu, které jsou specifikovány nějakou množinou prvků?

 ;)
Kód: [Vybrat]

public static void main(final String[] args) {
final ArrayList<Object> arrayList = new ArrayList<Object>(Arrays.asList("a", "b", "c", "d", "e"));
System.out.println(arrayList);
final int[] toRemoveIdxs = new int[]{0, 3, 1, 5};
Arrays.sort(toRemoveIdxs); // pokud toRemoveIdxs jsou nesetrizeny

{ // algoritmus odstraneni podle indexu
...

Proč bych to měl dělat takhle, když můžu použít čitelnější postup Standy Blábola? Viz.
https://forum.root.cz/index.php?topic=21857.msg317204#msg317204
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: vitro 21. 09. 2019, 22:26:13
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í.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: vitro 21. 09. 2019, 22:51:55
Jak se na tohle můžeš ptát?

Jak se na tohle můžeš ptát?
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Kit 21. 09. 2019, 23:27:14
Popravdě řečeno, nenapadá mě případ užití toho, co požaduješ. Evidentně si pleteš pojmy pole a seznam, z toho vzniká tohle zmatení.

ArrayList implementuje rozhraní List. Má rozhraní List metodu pro odstranění prvku podle indexu? Nemá, tak ji laskavě nepoužívej.

Abych trochu napověděl: Můžeš použít třeba metodu List.removeAll(), ta by to měla zvládnout.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 21. 09. 2019, 23:34:07
Proč bych to měl dělat takhle, když můžu použít čitelnější postup Standy Blábola? Viz.
https://forum.root.cz/index.php?topic=21857.msg317204#msg317204

Protoze v zadani je, ze se maji z listu prvky vymazat a ne ze se ma vytvorit novy list.
Navic je tu performance.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: listoper 22. 09. 2019, 07:22:45
Popravdě řečeno, nenapadá mě případ užití toho, co požaduješ. Evidentně si pleteš pojmy pole a seznam, z toho vzniká tohle zmatení.

ArrayList implementuje rozhraní List. Má rozhraní List metodu pro odstranění prvku podle indexu? Nemá, tak ji laskavě nepoužívej.

Abych trochu napověděl: Můžeš použít třeba metodu List.removeAll(), ta by to měla zvládnout.

https://docs.oracle.com/javase/8/docs/api/java/util/List.html#remove-int-
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Ondra Satai Nekola 22. 09. 2019, 08:21:26
ArrayList implementuje rozhraní List. Má rozhraní List metodu pro odstranění prvku podle indexu? Nemá, tak ji laskavě nepoužívej.

nebalábol
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: karelguth 22. 09. 2019, 11:01:51
Díky za odpovědi, vyřešil jsem jednoduše vytvořením nového ArrayListu. Šlo mi jen o to se ujistit, zda neexistuje nějaká metoda, kterou by se to dalo sfouknout na jednom řádku kódu.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Idris 22. 09. 2019, 11:10:17
Popravdě řečeno, nenapadá mě případ užití toho, co požaduješ. Evidentně si pleteš pojmy pole a seznam, z toho vzniká tohle zmatení.

ArrayList implementuje rozhraní List. Má rozhraní List metodu pro odstranění prvku podle indexu? Nemá, tak ji laskavě nepoužívej.
Já tam tu metodu vidím. Jsi si jist, že víš, o čem mluvíš?
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Ondra Satai Nekola 22. 09. 2019, 11:21:39
Popravdě řečeno, nenapadá mě případ užití toho, co požaduješ. Evidentně si pleteš pojmy pole a seznam, z toho vzniká tohle zmatení.

ArrayList implementuje rozhraní List. Má rozhraní List metodu pro odstranění prvku podle indexu? Nemá, tak ji laskavě nepoužívej.
Já tam tu metodu vidím. Jsi si jist, že víš, o čem mluvíš?

Neví. Tupě aplikuje nějakou Bobovskou poučku.

A ano, ta metoda existuje. A i kdyby nebyla, tak není důvod ji nepoužít, protože kód byl pro ArrayList a ne List. (Nic proti programování na interface, ale ocamcaď pocamcaď. Kdyby nemělo smysl mít mezi implementacemi rozdíly, tak by nebylo potřeba mít různé implementace.)
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Ondrej Nemecek 22. 09. 2019, 11:22:26
Proč bych to měl dělat takhle, když můžu použít čitelnější postup Standy Blábola? Viz.
https://forum.root.cz/index.php?topic=21857.msg317204#msg317204

Protoze v zadani je, ze se maji z listu prvky vymazat a ne ze se ma vytvorit novy list.
Navic je tu performance.

To ale Standa Blábol taky řeší:

(...)
Nebo si vyrob pomocny arraylist pro vsechny keys z keylistu a na puvodnim arraylistu zavolej removeAlll() Tehnle pristup je vhodny pokud je pocet klicu maly vzhledem k delce arraylistu.

Nepredpokladam, ze resis kazdou milisekundu, to by nebyly daove struktury tak blbe navrzene.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Ondra Satai Nekola 22. 09. 2019, 11:23:16
Díky za odpovědi, vyřešil jsem jednoduše vytvořením nového ArrayListu. Šlo mi jen o to se ujistit, zda neexistuje nějaká metoda, kterou by se to dalo sfouknout na jednom řádku kódu.

Všimni si ještě, o co je to tak snažší, než když musíš modifikovat ten původní... A to nemluvíme o situaci, kdy bys ta data nějak sdílel.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: gill 22. 09. 2019, 19:49:21
Díky za odpovědi, vyřešil jsem jednoduše vytvořením nového ArrayListu. Šlo mi jen o to se ujistit, zda neexistuje nějaká metoda, kterou by se to dalo sfouknout na jednom řádku kódu.

možná nějakou knihovnou nebo přejít na Kotlin, v Kotlinu existuje metoda filterIndexed

Kód: [Vybrat]
val list = listOf("one", "two", "three", "four")
val toremove = setOf(1,2)
val filteredIdx = list.filterIndexed { index, _ -> index !in toremove  }
println(filteredIdx) // [one, four]

pokud vím, v Javě nic podobného není, ani v Guavě a podobných knihovnách. Musel bys vytvořit list indexů, ten přefiltrovat a potom namapovat. Možná by šel elegantně použít predikát "in" z Guavy. Záleží, jestli ti jde o jednoduchost nebo o výkon.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: gill 22. 09. 2019, 20:23:25
Když ty indexy seřadíš, tak při procházení od nejmenšího víš, o kolik jsou ty další posunuté, nebo při procházení od nejvyššího tě posunutí netrápí. Jak se na tohle můžeš ptát?

nebo procházet od největšího.

Kód: [Vybrat]
Collections.sort(toremove, Collections.reverseOrder());
for (int i : toremove)
    list.remove(i);

to je asi nejstručnější, ale nejsem si jistý složitostí. Jistější je vytvořit nový seznam.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Zabanovaný Anonymní Troll 22. 09. 2019, 20:53:16
Jak se na tohle můžeš ptát?

Jak se na tohle můžeš ptát?

Jak se ho na to muzes ptat?
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 22. 09. 2019, 20:56:13
Proč bych to měl dělat takhle, když můžu použít čitelnější postup Standy Blábola? Viz.
https://forum.root.cz/index.php?topic=21857.msg317204#msg317204

Protoze v zadani je, ze se maji z listu prvky vymazat a ne ze se ma vytvorit novy list.
Navic je tu performance.

To ale Standa Blábol taky řeší:

(...)
Nebo si vyrob pomocny arraylist pro vsechny keys z keylistu a na puvodnim arraylistu zavolej removeAlll() Tehnle pristup je vhodny pokud je pocet klicu maly vzhledem k delce arraylistu.

Nepredpokladam, ze resis kazdou milisekundu, to by nebyly daove struktury tak blbe navrzene.

Algoritmu, ktery jsem uvedl v prispevku, je maximalne efektivni a zaroven ten ArrayList modifikuje (nevytvari novy).
Coz, jak spravne bylo uvedeno v prispevku vyse, je klicova vlastnost pri sdileni teto struktury.
Ze zadani jsem se domnival, ze prave sdileni sktruktury nebo performance pozadavky implikuje "odstraneni polozek", nikoliv vytvoreni listu noveho.
Metoda ArrayList.removeAll() provadi remove v cyklu, coz zvysuje vypocetni slozitost.
Proto si dovolim pouziti removeAll povazovat za zbytecne plytvani. A prosim, debaty o tom, ze performance neni argument, jednoduse neberu.
Bohuzel se zda, ze dotaz vznikl pouze z nedostatecne znalosti, ikdyz to je moc pekny dotaz. Vyvozuji to z prijateho reseni.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Zabanovaný Anonymní Troll 22. 09. 2019, 21:02:23
Kód: [Vybrat]
int[] itemsToRemove = {0, 5, 1, 4};
Arrays.sort(itemsToRemove);

for(int i = 0; i<itemsToRemove.length; i++) {
  list.remove(itemsToRemove[i] - i);
}
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Zabanovaný Anonymní Troll 22. 09. 2019, 22:11:57
Nebo:

Kód: [Vybrat]
int[] itemsToRemove = {0, 5, 1, 4};
Arrays.sort(itemsToRemove);
Arrays.reverse(itemsToRemove);

for(int i = 0; i<itemsToRemove.length; i++) {
  list.remove(itemsToRemove[i]);
}
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 23. 09. 2019, 08:21:35
Algoritmu, ktery jsem uvedl v prispevku, je maximalne efektivni
Je dost odvážné tvrdit o něčem, že je to maximálně efektivní, když neznáte přesné zadání. Váš algoritmus ponechá původní velikost podkladového pole, takže není paměťově efektivní. Kdybyste to chtěl spravit zavoláním trimToSize(), bude zase výpočetně neefektivní (nevíte, zda to zmenšení pole není zbytečné).
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 23. 09. 2019, 08:26:04
Nebo:

Kód: [Vybrat]
int[] itemsToRemove = {0, 5, 1, 4};
Arrays.sort(itemsToRemove);
Arrays.reverse(itemsToRemove);

for(int i = 0; i<itemsToRemove.length; i++) {
  list.remove(itemsToRemove[i]);
}
for-each cyklus je v Javě už 15 let.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: gill 23. 09. 2019, 12:44:54
Metoda ArrayList.removeAll() provadi remove v cyklu, coz zvysuje vypocetni slozitost.

removeAll hlavně dělá něco jiného, než na co se ptal tazatel. Odstraňuje položky podle hodnot, on chce odstranit podle indexů.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 23. 09. 2019, 13:12:40
Metoda ArrayList.removeAll() provadi remove v cyklu, coz zvysuje vypocetni slozitost.

removeAll hlavně dělá něco jiného, než na co se ptal tazatel. Odstraňuje položky podle hodnot, on chce odstranit podle indexů.

To je samozrejme pravda, ale vase pozorovani neni v rozporu s tim, co jsem napsal.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 23. 09. 2019, 13:49:18
Algoritmu, ktery jsem uvedl v prispevku, je maximalne efektivni
Je dost odvážné tvrdit o něčem, že je to maximálně efektivní, když neznáte přesné zadání. Váš algoritmus ponechá původní velikost podkladového pole, takže není paměťově efektivní. Kdybyste to chtěl spravit zavoláním trimToSize(), bude zase výpočetně neefektivní (nevíte, zda to zmenšení pole není zbytečné).

Presne zadani jsem ocekaval v prvnim prispevku tohoto fora.

Ponechava puvodni velikost podkladoveho pole a povazuji to za dobrou vlastnost. To z toho duvodu, ze 1) pro jakoukoliv dalsi naslednou operaci, ktera ma za nasledek zmenu velikosti listu neni rozumne toto provadet automaticky a 2) mame onu metodu trimToSize, ktera toto dela na vyzadani. To, ze tam nejake pole je, je vlastnosti ArrayListu a je treba s tim pracovat. Nasledna prace se zmenou velikosti pole nebyla pozadovana.

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).
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) nebo odstranovani prvku z puvodniho listu (volanim metody remove) jsou mene efektivni. Odstranovani pro kazde volani posouva zbytek pole za odstranenym elementem. To je nevyhoda ArrayListu. Je to wrapper nad polem, ktery dela presne to, co ma delat a jeho vlastnosti plynou uz ze jmena teto struktury *Array*List.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 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í…
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: gill 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 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".
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Kit 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
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Standa Blábol 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Standa Blábol 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: gill 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 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.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Standa Blábol 26. 09. 2019, 18:25:45
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.

Kód: [Vybrat]
ArrayList<String> strings = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
Set<Integer> indexes = new HashSet<>(Arrays.asList(2,3));

List<String> filteredStrings = IntStream.range(0, strings.size()).filter(i -> !indexes.contains(i)).mapToObj(i -> strings.get(i)).collect(Collectors.toList());

System.out.println("Filtered list: " + filteredStrings);
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 27. 09. 2019, 00:35:19
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.

Java:

val list = Arrays.asList("one", "two", "three", "four");
val toremove = Arrays.asList(1, 2);
val filteredIdx = toremove.stream().map(list::get).collect(Collectors.toList());
System.out.println(filteredIdx); // [two, three]
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 27. 09. 2019, 00:43:54
ConcurrentModificationException ale může vypadnout i v jednovláknové aplikaci. Připadá mi to jako dost základní znalost.

Jak by jste to jako zaridil? To do metody na promazani podle indexu chcete poslat roziterovany list?

Vy zase předpokládáte, že co nevidíte, to neexistuje. Já jsem tady ale modifikaci vašeho algoritmu popisoval.

Neco jste sem napsal, ale algoritmus to rozhodne nebyl. Tak se nestydte a sem s nim!

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.

Rozhodne:
- velikost pole dat 5, 50, 500, 5_000, 50_000 , 500_000 a 5_000_000 zaznamu
- velikost pole indexu 1%, 5%, 10%, 20%, 50%, 70%, 90%, 95 a 99% velikost pole dat.
Porovnavam svuj (pro vas neefektivni) algoritmus s vasim efektivnim na zahrate JVM s primerenym poctem iteraci.
Je to pro vas dost zretelne?

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.

Jiste, cekam az mne poucite...
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 27. 09. 2019, 01:25:53
val filteredIdx = toremove.stream().map(list::get).collect(Collectors.toList());

Je tam otocena podmink. Takhle tedy ne, pardon.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 27. 09. 2019, 10:58:52
Jak by jste to jako zaridil? To do metody na promazani podle indexu chcete poslat roziterovany list?
Třeba. Nebo to podle vás nejde?

Rozhodne:
- velikost pole dat 5, 50, 500, 5_000, 50_000 , 500_000 a 5_000_000 zaznamu
- velikost pole indexu 1%, 5%, 10%, 20%, 50%, 70%, 90%, 95 a 99% velikost pole dat.
Porovnavam svuj (pro vas neefektivni) algoritmus s vasim efektivnim na zahrate JVM s primerenym poctem iteraci.
Je to pro vas dost zretelne?
Je zvláštní, že jste vynechal zrovna ten parametr, o kterém se celou dobu bavíme – tedy jaká je distribuce indexů určených ke smazání. Víte o tom, že třeba třídící algoritmy jsou různě efektivní v závislosti na tom, zda mají třídit náhodně seřazená data, už seřazená data, částečně seřazené data nebo data seřazená v opačném pořadí? I kdybych tu nepsal o algoritmu, který bude tím efektivnější, čím větší souvislé bloky se budou mazat, alespoň ta podobnost s řazením vás mohla trknout.

Jiste, cekam az mne poucite...
Dávno už se stalo.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: gill 27. 09. 2019, 15:48:05
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.

Java:

val list = Arrays.asList("one", "two", "three", "four");
val toremove = Arrays.asList(1, 2);
val filteredIdx = toremove.stream().map(list::get).collect(Collectors.toList());
System.out.println(filteredIdx); // [two, three]


prvky z toremove naopak zachova.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 28. 09. 2019, 00:58:10
Třeba. Nebo to podle vás nejde?

Jiste ze jde, ale tohle lze rict o kazde metode, ktera meni stav listu, napriklad ArrayList.remove(...).
Takze voda je morka, vitr fouka a vy jste mi vysvetlil, ze lze vyvolat vyjimku chybou v programu...

Je zvláštní, že jste vynechal zrovna ten parametr, o kterém se celou dobu bavíme – tedy jaká je distribuce indexů určených ke smazání. Víte o tom, že třeba třídící algoritmy jsou různě efektivní v závislosti na tom, zda mají třídit náhodně seřazená data, už seřazená data, částečně seřazené data nebo data seřazená v opačném pořadí? I kdybych tu nepsal o algoritmu, který bude tím efektivnější, čím větší souvislé bloky se budou mazat, alespoň ta podobnost s řazením vás mohla trknout.

Ne, pouze jsem nepredpokladal, ze vam ty % nebudou zrejme.
Proc jen jsou odstupnovane..? Tak zapojte hlavu a zkuste to vymyslet, at to to nemusim vysvetlovat zcela polopaticky.

Dávno už se stalo.

Nekolikrat jste napsal, ze jste neco dokazal. Ne.
Pouze jste jedno poprel a druhe se snazil odiskutovat. To ale neni zadny dukaz, to je tlachani.
Zadny aloritmus k porovnani jsem od vas nevidel a zadny zrejme ani neuvidim.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 28. 09. 2019, 10:19:31
vy jste mi vysvetlil, ze lze vyvolat vyjimku chybou v programu...
Nikoli, já jsem vám vysvětlil, že ConcurrentModificationException nemá nic společného s vícevláknovým přístupem. Ono je to s vlastně skoro opačně. ArrayList není bezpečné používat z více vláken bez explicitní synchronizace přístupu, a pokud se ho pokusíte používat z více vláken bez synchronizace, může se vám stát, že např. pokud budete v jednom vlákně iterovat a v druhém vlákně seznam modifikovat, výjimka ConcurrentModificationException nevypadne.

Sice jsem vám zase jen opsal to, co je napsané v JavaDocu, ale doufám, že to k něčemu bylo, ten JavaDoc si teď dostudujete a příště nebudete ArrayList a ConcurrentModificationException spojovat s více vlákny.

Ne, pouze jsem nepredpokladal, ze vam ty % nebudou zrejme.
Proc jen jsou odstupnovane..? Tak zapojte hlavu a zkuste to vymyslet, at to to nemusim vysvetlovat zcela polopaticky.
Dost ubohý pokus, já si pamatuju, o čem jsem psal, a kdybych si to nepamatoval, můžu si to přečíst. Psal jsem, že vám v tom přehledu benchmarků dost podstatná kategorie chybí. Což nezamaskujete tím, že se budete pokoušet vrátit k těm, kter jste vyjmenoval, a vymýšlet si, že je nechápu.

Nekolikrat jste napsal, ze jste neco dokazal. Ne.
Pouze jste jedno poprel a druhe se snazil odiskutovat. To ale neni zadny dukaz, to je tlachani.
Zadny aloritmus k porovnani jsem od vas nevidel a zadny zrejme ani neuvidim.
Problém je v tom, že nevíte, co je to algoritmus. Algoritmus je popis řešení problému určený pro lidi – a ten já jsem napsal. Na rozdíl od vás, vy jste napsal implementaci algoritmu, v konkrétním programovacím jazyce. Z vašeho kódu není tak těžké algoritmus odvodit, ale algoritmus to není.

Ten mnou popsaný algoritmus není nijak složitý, měl byste být schopen ten kód napsat sám. Zvlášť pokud chcete dělat jeho benchmark – udělat rozumný benchmark není nic snadného, není to jen změřit pár čísel, která nic neznamenají. Umět nějaký kód napsat je nutná podmínka toho, abyste na něj mohl udělat dobrý benchmark – protože tomu kódu musíte rozumět, musíte vědět, jaká jsou jeho slabá a silná místa. Jinak tím svým benchmarkem klidně změříte nějakou výjimečnou situaci, kde ten kód bude náhodou výjimečně efektivní nebo výjimečně neefektivní.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: raskal 30. 09. 2019, 03:41:53
vy jste mi vysvetlil, ze lze vyvolat vyjimku chybou v programu...
Nikoli, já jsem vám vysvětlil, že ConcurrentModificationException nemá nic společného s vícevláknovým přístupem. Ono je to s vlastně skoro opačně. ArrayList není bezpečné používat z více vláken bez explicitní synchronizace přístupu, a pokud se ho pokusíte používat z více vláken bez synchronizace, může se vám stát, že např. pokud budete v jednom vlákně iterovat a v druhém vlákně seznam modifikovat, výjimka ConcurrentModificationException nevypadne.

Sice jsem vám zase jen opsal to, co je napsané v JavaDocu, ale doufám, že to k něčemu bylo, ten JavaDoc si teď dostudujete a příště nebudete ArrayList a ConcurrentModificationException spojovat s více vlákny.

Ne, pouze jsem nepredpokladal, ze vam ty % nebudou zrejme.
Proc jen jsou odstupnovane..? Tak zapojte hlavu a zkuste to vymyslet, at to to nemusim vysvetlovat zcela polopaticky.
Dost ubohý pokus, já si pamatuju, o čem jsem psal, a kdybych si to nepamatoval, můžu si to přečíst. Psal jsem, že vám v tom přehledu benchmarků dost podstatná kategorie chybí. Což nezamaskujete tím, že se budete pokoušet vrátit k těm, kter jste vyjmenoval, a vymýšlet si, že je nechápu.

Nekolikrat jste napsal, ze jste neco dokazal. Ne.
Pouze jste jedno poprel a druhe se snazil odiskutovat. To ale neni zadny dukaz, to je tlachani.
Zadny aloritmus k porovnani jsem od vas nevidel a zadny zrejme ani neuvidim.
Problém je v tom, že nevíte, co je to algoritmus. Algoritmus je popis řešení problému určený pro lidi – a ten já jsem napsal. Na rozdíl od vás, vy jste napsal implementaci algoritmu, v konkrétním programovacím jazyce. Z vašeho kódu není tak těžké algoritmus odvodit, ale algoritmus to není.

Ten mnou popsaný algoritmus není nijak složitý, měl byste být schopen ten kód napsat sám. Zvlášť pokud chcete dělat jeho benchmark – udělat rozumný benchmark není nic snadného, není to jen změřit pár čísel, která nic neznamenají. Umět nějaký kód napsat je nutná podmínka toho, abyste na něj mohl udělat dobrý benchmark – protože tomu kódu musíte rozumět, musíte vědět, jaká jsou jeho slabá a silná místa. Jinak tím svým benchmarkem klidně změříte nějakou výjimečnou situaci, kde ten kód bude náhodou výjimečně efektivní nebo výjimečně neefektivní.

S vama je to jak s malym chlapcem, ktery vsude byl a vsechno videl. Upozornujete na veci zrejme jako by v nich v kontextu tohoto fora slo o neco duleziteho a nehodlate pripustit celkem zakladni principy. Jste pro me jen ztratou casu.
Název: Re:Java - jak vymazat z ArrayListu množinu položek
Přispěvatel: Filip Jirsák 30. 09. 2019, 10:15:08
Upozornujete na veci zrejme jako by v nich v kontextu tohoto fora slo o neco duleziteho
Na vašem místě bych se radši zamyslel, proč vám někdo musí ty zřejmé věci vysvětlovat – že ConcurrentModificationException nijak nesouvisí s vícevláknovým přístupem, že efektivitu algoritmu lze měřit z různých hledisek, že efektivita algoritmu pracujícího s podmnožinou prvků seznamu závisí na tom, jak jsou rozložené prvky z té podmnožiny… To, že opravuju vaše chybná vyjádření, neznamená, že jsem všude byl a všechno viděl. Znamená to akorát to, že vidím chyby, které vy nevidíte. Když na sto metrech předběhnete kulhajícího důchodce, neznamená to, že jste mistr světa v běhu na sto metrů, ale jenom to, že jste alespoň o fous rychlejší, než ten kulhající důchodce.