Preskoči na glavni sadržaj

Java Arrays: alatka stvorena za nizove

Chenmo Wang ErJava jezgroČesto korišćene alatke2255 reči8 minuta

"Erge, da li je alatka namenjena nizovima zaista stvorena za rad sa nizovima? Na primer, kreiranje nizova, sortiranje nizova, pretraga nizova i tako dalje." Pitanje koje je Sanmej postavila zapravo je već sadržalo odgovor.

"Jeste, alatka za nizove o kojoj govorimo je klasa java.util.Arrays; za skoro sve uobičajene operacije nad nizovima ova klasa nudi statičke metode koje možete direktno pozvati. Uostalom, samom nizu je prilično nezgodno da izvrši ove operacije, a uz ovaj sloj enkapsulacije sve je mnogo jednostavnije." Dok sam odgovarao Sanmej, otvorio sam Intellij IDEA i pronašao izvorni kod klase Arrays.

package java.util;
/**
 * @author Josh Bloch
 * @author Neal Gafter
 * @author John Rose
 * @since  1.2
 */
public class Arrays {}

"Konkretno, operacije nad nizovima mogu se podeliti u sledećih 9 vrsta."

  • Kreiranje nizova
  • Poređenje nizova
  • Sortiranje nizova
  • Pretraga nizova
  • Niz u tok (stream)
  • Štampanje niza
  • Niz u List
  • setAll (još uvek bez srpskog naziva)
  • parallelPrefix (još uvek bez srpskog naziva)

"Hajde da ih učimo jedno po jedno."

01. Kreiranje nizova

Kreiranje nizova pomoću klase Arrays može se izvesti kroz sledeće tri metode:

  • copyOf, kopira zadati niz, skraćuje ili dopunjuje sa null
  • copyOfRange, kopira niz u zadatom opsegu u novi niz
  • fill, popunjava niz

1) copyOf

Hajde da pogledamo primer direktno:

String[] intro = new String[] { "Chen", "mo", "Wang", "Er" };
String[] revised = Arrays.copyOf(intro, 3);
String[] expanded = Arrays.copyOf(intro, 5);
System.out.println(Arrays.toString(revised));
System.out.println(Arrays.toString(expanded));

revised i expanded su novi nizovi nakon kopiranja, dužina im je 3 odnosno 5, dok je dužina zadatog niza 4. Hajde da pogledamo rezultat:

[Chen, mo, Wang]
[Chen, mo, Wang, Er, null]

Vidite? revised je odsekao poslednji element, jer mu je dužina 3; expanded je dopunio sa null, jer mu je dužina 5.

Metoda grow() u izvornom kodu klase ArrayList (čija interna struktura podataka koristi upravo nizove) poziva metod copyOf(): kada inicijalna veličina ArrayList više ne može da primi rast broja elemenata, vrši se proširenje.

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
            newCapacity(minCapacity));
}

2) copyOfRange

Hajde da pogledamo primer direktno:

String[] intro = new String[] { "Chen", "mo", "Wang", "Er" };
String[] abridgement = Arrays.copyOfRange(intro, 0, 3);
System.out.println(Arrays.toString(abridgement));

Metod copyOfRange() zahteva tri parametra: prvi je zadati niz, drugi je početna pozicija (uključujući), a treći je krajnja pozicija (ne uključujući). Hajde da pogledamo rezultat:

[Chen, mo, Wang]

Pozicija 0 je "Chen", pozicija 3 je "Er", što znači da su uzeti elementi niza od pozicije 0 (uključujući) do pozicije 3 (ne uključujući). A šta bi se desilo kada bi indeks prešao dužinu niza?

String[] abridgementExpanded = Arrays.copyOfRange(intro, 0, 6);
System.out.println(Arrays.toString(abridgementExpanded));

Krajnja pozicija je sada 6, što prelazi dužinu 4 zadanog niza. Hajde da pogledamo rezultat:

[Chen, mo, Wang, Er, null, null]

I dalje je korišćeno null za dopunu.

"Zašto se to radi tako?" Posle ovog perioda učenja, Sanmej je sve oštroumnija i pita pitanja koja pogađaju suštinu.

"Hmm, mislim da su projektanti klase Arrays imali u vidu problem prelaska granica niza, inače bismo pri svakom pozivu klase Arrays morali mnogo puta da proveravamo dužinu, što bi bilo vrlo nezgodno." Posle kraćeg razmišljanja, dao sam joj ovakav odgovor.

3) fill

Hajde da pogledamo primer direktno:

String[] stutter = new String[4];
Arrays.fill(stutter, "Chenmo Wang Er");
System.out.println(Arrays.toString(stutter));

Ključnom reči new napravljen je niz dužine 4, a zatim je metod fill() popunio sva 4 mesta vrednošću "Chenmo Wang Er". Hajde da pogledamo rezultat:

[Chenmo Wang Er, Chenmo Wang Er, Chenmo Wang Er, Chenmo Wang Er]

Kada vam treba niz sa potpuno istim elementima, metod fill() baš tad dolazi do izražaja.

02. Poređenje nizova

Metod equals() klase Arrays služi da utvrdi da li su dva niza jednaka. Hajde da pogledamo sledeći primer:

String[] intro = new String[] { "Chen", "mo", "Wang", "Er" };
boolean result = Arrays.equals(new String[] { "Chen", "mo", "Wang", "Er" }, intro);
System.out.println(result);
boolean result1 = Arrays.equals(new String[] { "Chen", "mo", "Wang", "San" }, intro);
System.out.println(result1);

Rezultat je sledeći:

true
false

Zadati niz sadrži četiri znaka imena Chenmo Wang Er, a nizovi za poređenje su jedan Chenmo Wang Er i jedan Chenmo Wang San, pa je result true, a result1 false.

Hajde da ukratko pogledamo izvorni kod metode equals():

public static boolean equals(Object[] a, Object[] a2) {
    if (a==a2)
        return true;
    if (a==null || a2==null)
        return false;

    int length = a.length;
    if (a2.length != length)
        return false;

    for (int i=0; i<length; i++) {
        if (!Objects.equals(a[i], a2[i]))
            return false;
    }

    return true;
}

Pošto je niz objekat, prvo se koristi operator "==" za proveru; ako nisu jednaki, zatim se proverava da li je neki od njih null — ako je jedan null, vraća se false; zatim se proverava length, i ako nije isti, vraća se false; u suprotnom se redom poziva Objects.equals() da uporedi elemente na istim pozicijama.

"Ovaj kod je prilično strog, zar ne? Sanmej, upravo to je smisao učenja izvornog koda — dok ga cimo, možemo usvojiti i jasnu logiku autora koda." Govorio sam Sanmej iskreno i toplo.

Pored metode equals(), postoji još jedan trik za proveru jednakosti dva niza, iako može doći do odstupanja. To je metod Arrays.hashCode(). Hajde da prvo pogledamo njegov izvorni kod:

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

Sam heš algoritam je vrlo strog, tako da ako su heš vrednosti dva niza jednake, skoro da se može zaključiti da su nizovi jednaki.

String[] intro = new String[] { "Chen", "mo", "Wang", "Er" };

System.out.println(Arrays.hashCode(intro));
System.out.println(Arrays.hashCode(new String[] { "Chen", "mo", "Wang", "Er" }));

Hajde da pogledamo rezultat:

868681617
868681617

Heš vrednosti oba niza su jednake, jer su elementi isti. Ali ovo zaista nije dovoljno strogo; primarno koristite metod Objects.equals(). Kada želimo da brzo potvrdimo da li su dva niza jednaka, možemo ih uporediti preko hashCode — to je svojevrsna prečica, visok rizik uz visok dobitak, haha.

03. Sortiranje nizova

Metod sort() klase Arrays služi za sortiranje nizova. Hajde da pogledamo sledeći primer:

String[] intro1 = new String[] { "chen", "mo", "wang", "er" };
String[] sorted = Arrays.copyOf(intro1, 4);
Arrays.sort(sorted);
System.out.println(Arrays.toString(sorted));

Pošto sortiranje menja originalni niz, koristili smo metod copyOf() da napravimo novu kopiju. Hajde da pogledamo rezultat:

[chen, er, mo, wang]

Vidi se da je raspoređeno rastuće po prvom slovu. Primitivni tipovi podataka sortiraju se pomoću dual-pivot quicksort, dok se referentni tipovi podataka sortiraju pomoću TimSort, koji koristi tehnike iz rada Petera McIlroya "Optimistic Sorting and Information Theoretic Complexity".

"Erge, uopšte ne razumem te algoritme sortiranja o kojima pričaš!" rekla je Sanmej trepćući očima.

"Nije problem, kada kasnije naučiš strukture podataka i algoritme, razumećeš; za sada je dovoljno da samo otprilike znaš za ovo." Brzo sam krenuo sa utešnim rečima.

04. Pretraga nizova

Nakon sortiranja niza možemo koristiti metod binarySearch() klase Arrays za binarnu pretragu. U suprotnom ostaje samo linearna pretraga, što je znatno manje efikasno.

String[] intro1 = new String[] { "chen", "mo", "wang", "er" };
String[] sorted = Arrays.copyOf(intro1, 4);
Arrays.sort(sorted);
int exact = Arrays.binarySearch(sorted, "wang");
System.out.println(exact);
int caseInsensitive = Arrays.binarySearch(sorted, "Wang", String::compareToIgnoreCase);
System.out.println(caseInsensitive);

Metod binarySearch() može da pretražuje i precizno i približno, na primer zanemarujući velika i mala slova. Hajde da pogledamo rezultat:

3
3

Sortirani rezultat je [chen, er, mo, wang], pa je dobijeni indeks 3.

"Sanmej, zapamti: kasnije, kada tražiš element iz niza ili kolekcije, prvo sortiraj kad god možeš, a zatim koristi binarnu pretragu — to će znatno povećati efikasnost pretrage."

Sanmej je zamišljeno klimnula glavom.

05. Pretvaranje niza u tok (stream)

"Šta je to tok (stream)?" upitala je Sanmej radoznalo.

"Engleska reč za tok je Stream; on u velikoj meri može povećati produktivnost Java programera i omogućiti im da pišu efikasan, čist i sažet kod. Ovaj stil posmatra kolekciju koja se obrađuje kao tok — zamislite kako voda teče kroz cevi; unutar te cevi možemo vršiti obradu toka, na primer filtriranje, sortiranje i tako dalje. Kako se Stream konkretno koristi, ostavićemo za kasnije da detaljno obradimo; ovde je dovoljno da stekneš opšti utisak." odgovorio sam.

Metod stream() klase Arrays može pretvoriti niz u tok:

String[] intro = new String[] { "Chen", "mo", "Wang", "Er" };
System.out.println(Arrays.stream(intro).count());

Mogu se zadati i početni i krajnji indeks za metod stream():

System.out.println(Arrays.stream(intro, 1, 2).count());

Kada opseg indeksa nije ispravan, na primer od 2 do 1, program će baciti izuzetak ArrayIndexOutOfBoundsException:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: origin(2) > fence(1)
	at java.base/java.util.Spliterators.checkFromToBounds(Spliterators.java:387)

06. Štampanje niza

Pošto je niz objekat, ako direktno pozovemo System.out.println, rezultat izgleda ovako:

[Ljava.lang.String;@3d075dc0

Najelegantniji način štampanja jeste upotreba metode Arrays.toString(), koju smo zapravo već pomenuli. Hajde da pogledamo njen izvorni kod:

public static String toString(Object[] a) {
    if (a == null)
        return "null";

    int iMax = a.length - 1;
    if (iMax == -1)
        return "[]";

    StringBuilder b = new StringBuilder();
    b.append('[');
    for (int i = 0; ; i++) {
        b.append(String.valueOf(a[i]));
        if (i == iMax)
            return b.append(']').toString();
        b.append(", ");
    }
}
  • Najpre se proverava null; ako jeste, vraća se niska "null";
  • Zatim se uzima dužina niza; ako je dužina niza 0 (ekvivalentno tome da je length - 1 jednako -1), vraćaju se uglaste zagrade "[]" koje označavaju da je niz prazan;
  • Ako niz nije null, a dužina mu nije 0, deklariše se StringBuilder objekat, doda se početna oznaka niza "[", a zatim se prolazi kroz niz i dodaje svaki element; jedan mali trik je u tome što se, kada se naiđe na poslednji element (i == iMax), više ne dodaje zarez i razmak ", ", već završna oznaka niza "]".

"Erge, mogu li da te pitam nešto?"

"Pitaj."

"Zašto se pri proveri da li je dužina niza 0 zapravo poredi vrednost umanjena za 1 sa -1? Zašto se ne poredi direktno sa 0?"

"O, to je veoma dobro pitanje!" Hteo sam da kažem Sanmej "respect", baš je oštra! "Zapravo je to u vezi sa proverom i == iMax prilikom obilaska niza; inače bismo ovde morali da koristimo i == iMax - 1 da bismo proverili da li smo stigli do poslednjeg elementa niza."

"Ooo..." Izgledalo je da je Sanmej nešto shvatila.

07. Pretvaranje niza u List

Iako su nizovi veoma moćni, oni sami imaju malo pratećih metoda — na primer, provera da li niz sadrži neku vrednost. Ako ih pretvorimo u List, postaje mnogo jednostavnije, jer je u okviru za kolekcije List u Javi enkapsulirano mnogo često korišćenih metoda.

String[] intro = new String[] { "Chen", "mo", "Wang", "Er" };
List<String> rets = Arrays.asList(intro);
System.out.println(rets.contains("Er"));

Treba obratiti pažnju na to da Arrays.asList() vraća java.util.Arrays.ArrayList, a ne java.util.ArrayList; njegova dužina je fiksna i ne dozvoljava brisanje niti dodavanje elemenata.

rets.add("San");
rets.remove("Er");

Ovo se mora imati na umu pri pisanju koda, inače će pri izvršavanju ovih dveju metoda biti bačen izuzetak:

Exception in thread "main" java.lang.UnsupportedOperationException
	at java.base/java.util.AbstractList.add(AbstractList.java:153)
	at java.base/java.util.AbstractList.add(AbstractList.java:111)

Da biste manipulisali elementima, potreban je još jedan korak konverzije u pravi java.util.ArrayList:

List<String> rets1 = new ArrayList<>(Arrays.asList(intro));
rets1.add("San");
rets1.remove("Er");

08. setAll

Java 8 je dodala metod setAll(), koji pruža ulaz u funkcionalno programiranje i kojim se mogu popuniti elementi niza:

int[] array = new int[10];
Arrays.setAll(array, i -> i * 10);
System.out.println(Arrays.toString(array));

"Šta znači ovaj kod?" upitala je Sanmej.

i je zapravo indeks niza, sa vrednostima od 0 do 9, pa i * 10 znači da vrednosti idu od 0 * 10 do 9 * 10. Hajde da pogledamo rezultat:

[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

To se može iskoristiti za popunjavanje novog niza elementima izvedenim iz prethodnog niza.

09. parallelPrefix

Metod parallelPrefix(), kao i setAll(), takođe je na raspolaganju od Jave 8; pruža ulaz u funkcionalno programiranje tako što, prolazeći kroz elemente niza, uzima element na trenutnom indeksu i elemente pre njega, obavlja operaciju, a zatim rezultat te operacije upisuje nazad na trenutni indeks.

int[] arr = new int[] { 1, 2, 3, 4};
Arrays.parallelPrefix(arr, (left, right) -> left + right);
System.out.println(Arrays.toString(arr));

U gornjem kodu postoji Lambda izraz ((left, right) -> left + right); šta znači? Gornji kod je ekvivalentan sa:

int[] arr = new int[]{1, 2, 3, 4};
Arrays.parallelPrefix(arr, (left, right) -> {
    System.out.println(left + ", " + right);
    return left + right;
});
System.out.println(Arrays.toString(arr));

Pogledajte rezultat i biće vam jasno:

1, 2
3, 3
6, 4
[1, 3, 6, 10]

Drugim rečima, Lambda izraz je izvršen tri puta:

  • Prvi put sabiraju se 1 i 2, rezultat je 3, koji zamenjuje element na indeksu 1
  • Drugi put sabiraju se 3 i 3, rezultat je 6, što je zbir rezultata prvog puta i elementa na indeksu 2
  • Treći put sabiraju se 6 i 4, rezultat je 10, što je zbir rezultata drugog puta i elementa na indeksu 3

10. Rezime

"Dobro, Sanmej, učimo toliko za sada. Kasnije, kada budeš listao kroz izvorni kod Jave, svuda gde se koriste nizovi — posebno u klasi ArrayList — videćeš mnogo tragova klase Arrays."

"Dobro, da ponovim najpre sadržaj ovog odeljka. Erge, idi da se odmoriš."

Otišao sam u dnevnu sobu, seo na kauč, uzeo roman gospodina Huang Yongyua "Lutalica na reci bez tuge — osam godina, svezak 1" i počeo da čitam sa zadovoljstvom...