Java - hledání duplicit v poli - Optimalizace kódu

.. optimalizovat sa da hladanie duplicit tak ze si to zoradujes a potom pri hladani noveho oproti usporiadanemu zoznamu sa da dosiahnut tusim len zlozitost O(N*log(N) ci kolk oneviem zhlavy som 20rokov po univezite :D). Ci tvoja kniznica ma implementovany usporiadany zoznam a jeho hladanie netusim. Ale cyklus tam byt musi aspon jednoduchy (pre to normalne riesenie O(N^2) by bol cyklus dvojity vnoreny)

Ak uvažujeme, že HashSet.add sa blíži k O(1), tak zložitosť jeho algoritmu je O(N). Takže ak by to mal zoradiť a následné hľadať, tak by bola zložitosť vyššia.

Ten add to musi prehladat aby vedel ci sa to tam uz vyskytuje, takze to bude skor N a ne 1. (ak si to ten set zoraduje, tak to moze ist k tomu log(N) o ktorom som pisal). Prehladavat zoradeny zoznam je optimalnejsie jak prehladavat nezoradeny (zoradovat to nebude extra, staci ak to vklada na spravne miesta)

To je HashSet, čiže hešovacia tabuľka, takže pri pridávaní nemusí prehľadávať celý obsah. Za zvyčajných okolností to je naozaj O(1) operácia.

Jediná optimalizácia, ktorá sa tam dá spraviť, je ukončenie cyklu v prípade, že metóda add vráti false. Cyklu sa nevyhneš.

A co tohle?

public void check_diffrents(ObjectArrayList<Player> color_player, int number) {
        ObjectOpenHashSet hash = new ObjectOpenHashSet();
        try {
          setDisable(false);
          for (int i = number - 1; ; i -= 1) {
            if (!hash.add(color_player.get(i).getFill())) {
               setDisable(true);
               break;
            }
          }
        } catch (ArrayIndexOutOfBoundsException e) {
        }   
}

Neviem síce, prečo si vymenil poradie prechádzania prvkov v tom for cykle, ale pridaj tam podmienku i >= 0, nech tam nemusí byť ani ten try-catch kvôli zbytočnej výnimke. Metódu setDisable voláš 2x, ten predchádzajúci spôsob bol lepší.

Pokud umi ta tvoje kolekce z externi knihovny streamy, tak se muzes na oko zbavit cyklu pri tvorbe toho Setu takto:

Set<TO_CO_VRACI_GETFILL> names = color_player.stream().map(Player :: getFill).collect(Collectors.toSet());

Díky, tohle jsem potřeboval. (Hlavně že jsem stream před týdnem používal).

public void check_diffrents(ObjectArrayList<Player> color, int number) {
         ObjectSet<Paint> original_color = new ObjectOpenHashSet(color.stream().map(Player :: getFill).collect(Collectors.toSet()));
         setDisable(original_color.size() != number);
}

Tak ještě jsem to upravil, poněvadž jsem to nedostatečně otestoval a teď jsem zjistil, že parametr number vůbec nepoužívám a proto to nefunguje 100% dobře.

public void check_diffrents(ObjectArrayList<Player> color, int number) {
        ObjectSet<Paint> pure_color = new ObjectOpenHashSet(color.stream().limit(number).map(Player :: getFill).collect(Collectors.toSet()));
        setDisable(pure_color.size() != number);
}

Sice ses vyhnul cyklu, ale tipnul bych si, že jsi to tímhle ve skutečnosti o něco zpomalil.

Ale no tak, beztak tam ma 10 prvku, o tolik pomalejsi to zas nebude... Pokud ma 10 milionu, tak muze pouzit parallelStream() a bude to jeste rychlejsi, nez ten puvodni zapis (na vicejadrovem CPU)...

Pro 10 prvků nemá smysl optimalizovat ani úplně první zápis.

Ja to chapal tak, ze chce hezci kod bez cyklu. Ne, ze ma problemy s performance...

EDIT: ale ten kod je hnus i tak, metody a promenne s podtrzitky... To je hnus, velebnosti!

public void check_diffrents(ObjectArrayList<Player> color_player, int number) {
    ObjectOpenHashSet hash = new ObjectOpenHashSet();
    for (int i = 0; i < number; i++) {
        if (!hash.add(color_player.get(i).getFill())) {
            setDisable(true);
            return;
        }
    }
    setDisable(false);
}