streamalism.org

1. Prehľad

V tomto rýchlom výučbe sa dozvieme, ako zistiť, či sú všetky prvky v a Zoznam sú rovnaké.

Taktiež sa pozrieme na časovú zložitosť každého riešenia pomocou notácie Big O, čo nám poskytne najhorší scenár.

2. Príklad

Predpokladajme, že máme nasledujúce 3 zoznamy:

notAllEqualList = Arrays.asList ("Jack", "James", "Sam", "James"); emptyList = Arrays.asList (); allEqualList = Arrays.asList ("Jack", "Jack", "Jack", "Jack");

Našou úlohou je navrhnúť rôzne riešenia, ktoré sa vrátia pravda len pre emptyList a allEqualList.

3. Základné opakovanie

Po prvé, je pravda, že aby sa všetky prvky rovnali, musia sa všetky rovnať prvému prvku. Využime to v slučke:

public boolean verifyAllEqualUsingALoop (List list) {for (String s: list) {if (! s.equals (list.get (0))) return false; } návrat pravdivý; }

To je pekné, pretože aj keď je časová zložitosť taká O (n), môže často odísť skôr.

4. HashSet

Môžeme tiež použiť a HashSet pretože všetky jeho prvky sú odlišné. Jaf prevedieme a Zoznam do a HashSet a výsledná veľkosť je menšia alebo rovná 1, potom vieme, že všetky prvky v zozname sú rovnaké:

public boolean verifyAllEqualUsingHashSet (List list) {return new HashSet (list) .size () <= 1; }

Prevod a Zoznam do HashSet náklady O (n) čas pri volaní veľkosť berie O (1). Stále teda máme celkovú časovú zložitosť O (n).

5. Zbierky API

Ďalším riešením je použitie frekvencia (zbierka c, objekt o) metóda API Collection. Táto metóda vracia počet prvkov v a Zbierka c zodpovedajúce an Objekt o.

Ak sa teda výsledok frekvencie rovná veľkosti zoznamu, vieme, že všetky prvky sú rovnaké:

verejný boolean verifyAllEqualUsingFrequency (zoznam) návratový zoznam.isEmpty () 

Podobne ako v predchádzajúcich riešeniach je časová zložitosť O (n) keďže vnútorne, Collections.frequency () používa základné opakovanie.

6. Prúdy

The Prúd API v Jave 8 nám poskytuje ešte viac alternatívnych spôsobov zisťovania, či sú všetky položky v zozname rovnaké.

6.1. odlišný()

Pozrime sa na jedno konkrétne riešenie využívajúce odlišný() metóda.

Ak chcete overiť, či sú všetky prvky v zozname rovnaké, počítame odlišné prvky jeho toku:

public boolean verifyAllEqualUsingStream (List list) {return list.stream () .distinct () .count () <= 1; }

Ak je počet tohto prúdu menší alebo rovný 1, potom sú všetky prvky rovnaké a my sa vrátime pravda.

Celkové náklady na operáciu sú O (n), čo je čas potrebný na prechod cez všetky prvky streamu.

6.2. allMatch ()

The Prúd API allMatch () metóda poskytuje dokonalé riešenie na určenie, či sa všetky prvky tohto streamu zhodujú s poskytnutým predikátom:

verejný boolean verifyAllEqualAnotherUsingStream (zoznam), návrat zoznam.isEmpty () 

Podobne ako v predchádzajúcom príklade s použitím streamov, aj tento má O (n) časová zložitosť, čo je čas na prechod celým prúdom.

7. Knižnice tretích strán

Ak narazíme na staršiu verziu Javy a nemôžeme používať Stream API, môžeme využiť knižnice tretích strán ako napr Google Guava a Apache Commons.

Tu máme dve veľmi podobné riešenia, prechádzajúce zoznamom prvkov a porovnávajúce ich s prvým prvkom. Môžeme teda ľahko vypočítať časovú zložitosť, ktorá má byť O (n).

7.1. Maven závislosti

Ak chcete použiť ktorúkoľvek z nich, môžeme pridať jednu z nich guava alebo spoločné zbierky4 respektíve k nášmu projektu:

 com.google.guava guava 23.0 

     org.apache.commons commons-collections4 4.1 

7.2. Google Guava

V Google Guava, statická metóda Iterables.all () vracia pravda ak všetky prvky v zozname vyhovujú predikátu:

public boolean verifyAllEqualUsingGuava (List list) {return Iterables.all (list, new Predicate () {public boolean apply (String s) {return s.equals (list.get (0));}}); }

7.3. Apache Commons

Podobne Apache Commons Knižnica tiež poskytuje triedu nástrojov IterableUtils so sadou statických úžitkových metód, s ktorými sa dá pracovať Iterable inštancie.

Najmä statická metóda IterableUtils.matchesAll () vracia pravda ak všetky prvky v zozname vyhovujú predikátu:

public boolean verifyAllEqualUsingApacheCommon (zoznam List) {return IterableUtils.matchesAll (list, new org.apache.commons.collections4.Predicate () {public boolean evaluate (String s) {return s.equals (list.get (0));} }); } 

8. Záver

V tomto článku sme sa naučili rôzne spôsoby overovania, či sú všetky prvky v a Zoznam sú si rovné, počnúc jednoduchou funkčnosťou Java a potom ukazujúce alternatívne spôsoby pomocou Prúd API a knižnice tretích strán Google Guava a Apache Commons.

Tiež sme sa dozvedeli, že každé z riešení nám dáva rovnakú časovú zložitosť O (n). Je však na nás, aby sme si vybrali ten najlepší podľa toho, ako a kde bude použitý.

A nezabudnite si pozrieť kompletnú sadu vzoriek na GitHub.