Kurs Java Podstawy - rozszerzony

Arrays - operacje na tablicach

Częstymi operacjami jakie wykonujemy w naszych programach są różnego rodzaju działania na tablicach, a w śród nich przede wszystkim wyszukiwanie i sortowanie. Pisanie algorytmów samodzielnie nie miałoby więc w takim wypadku większego senesu - ponieważ musielibyśmy to przenosić praktycznie do każdego programu wykorzystującego tablice. Na szczęście w Javie dostępna jest gotowa klasa Arrays, która udostępnia te podstawowe metody. Są one w wersji statycznej, więc ich wywołanie powinno wyglądać schematycznie następująco:

Arrays.nazwaMetody(parametry);

Dostępnych jest kilka metod, a każda z nich posiada oczywiście kilka przeciążonych odpowiedników podstawowych typów liczbowych, a także typów obiektowych. W drugim przypadku niezbędne jest także utworzenie odpowiedniego komparatora, czyli tak naprawdę klasy implementującej interfejs Comparable i udostępniającej metodę compareTo(). Przyjmuje ona dwa obiekty i zawiera utworzony przez nas schemat postępowania kiedy traktować obiekt jako równe, a kiedy jako różne.

Klasa Arrays udostępnia nam również statyczną metodę asList(), która zwraca reprezentację tablicy w formie listy. Jest to przydatne, gdy musimy zamienić tablicę na bardziej odpowiedni typ dynamiczny.

Metody tej klasy to:

  • asList() - zwraca listową reprezentację tablicy
  • binarySearch() - wyszukuje parametr param w podanej tablicy array[]. Posiada przeciążone metody dla typów prostych, a w przypadku typów obiektowych należy podać trzeci parametr, którym jest odpowiedni komparator.
  • equals() - porównuje dwie tablice dowolnych typów
  • fill() - metoda ta pozwala w łatwy sposób wypełnić całą tablicę odpowiednią wartością podaną jako argument. Zaoszczędza nam to używania w tym celu pętli.
  • sort() - sortuje tablicę używając implementacji sortowania szybkiego (quicksort) zaproponowanego przez Jon L. Bentley and M. Douglas McIlroy's, które zapewnia logarytmiczną złożoność obliczeniową. Pozwala zarówno na sortowanie tablic dowolnego typu (do typów obiektowych potrzebny odpowiedni komparator), a także ich pewnego zakresu.

W celu pokazania praktycznego zastosowania tej klasy utworzymy tablicę obiektów typu pracownik i zobaczymy działanie odpowiednich metod. Do niektórych niezbędne jest także stworzenie odpowiedniego komparatora, co także uczynimy.

public class Pracownik {
	private String imie;
	private String nazwisko;
	private double wyplata;

	public Pracownik(String imie, String nazwisko, double wyplata){
		this.imie = imie;
		this.nazwisko = nazwisko;
		this.wyplata = wyplata;
	}

	String getImie(){ return imie; }
	String getNazwisko(){ return nazwisko; }
	double getWyplata(){ return wyplata; }

	public String toString() {
		return "Imię: "+imie+", Nazwisko: "+nazwisko+", Wypłata: "+wyplata;
	}
}

Klasa pracownik przechowuje podstawowe informacje: imię i nazwisko, a także wysokość wypłaty. Dodatkowo przesłonięto metodę toString() klasy Object w celu wygodnego wyświetlania danych w późniejszej części.

import java.util.Comparator;

public class Komparator implements Comparator<Pracownik>
{

	@Override
	public int compare(Pracownik p1, Pracownik p2) {
		if(p2 == null) return -1;
		if(p1.getWyplata() > p2.getWyplata()) return 1;
		else if(p1.getWyplata() < p2.getWyplata()) return -1;
		else return 0;
	}
}

Nasz komparator porównuje dwa obiekty typu pracownik za pomocą metody compare(). Porównanie odbywa się na podstawie wysokości wypłat w naturalnym rosnącym porządku. Warto zauważyć, że jest to klasa generyczna, w naszym przypadku wyspecjalizowana do porównywania obiektów typu Pracownik.

import java.util.Arrays;

public class Test {
	public static void main(String args[]){
	//Tworzymy kilku pracowników
	Pracownik krzysiek = new Pracownik("Krzysiek", "Piotrowicz", 2000);
	Pracownik piotrek = new Pracownik("Piotrek", "Wolny", 3000);
	Pracownik kasia = new Pracownik("Kasia", "Krotwicka", 2500);
	Pracownik wlodek = new Pracownik("Wlodek", "Zieba", 2300);

	//umieszczamy naszych pracowników w tablicy
	Pracownik[] prac = {krzysiek, piotrek, kasia, wlodek};
	//tworzymy obiekt komparatora, który wcześniej napisaliśmy
	Komparator komp = new Komparator();
	//sortujemy tablicę przy użyciu komparatora
	Arrays.sort(prac, komp);
	//wyświetlamy posortowaną tablicę
	wyswietl(prac);
	}

	//metoda wyświetlajca tablicę w ładnej formie
	public static void wyswietl(Pracownik[] prac){
		for(Pracownik p: prac)
			System.out.println(p);
	}
}

Na koniec klasa testowa. Najpierw utworzyliśmy kilku pracowników i dodaliśmy ich do tablicy tego typu. Następnie musieliśmy utworzyć także odpowiedni komparator do porównywania elementów. Za pomocą statycznej metody sort() z klasy Arrays posortowaliśmy wcześniej przygotowaną tablicę w rosnącym porządku według wysokości wypłat. Warto zauważyć, że tablice możemy traktować jak struktury implementujące interfejs Iterable i operować na nich przy pomocy foreach - u nas w celu wyświetlenia kolejnych elementów.

Komentarze

YeeeZooo

wkleiłem te trzy kody bez tej ostatniej pętli i jest taki błąd:

Test.java:21: class, interface, or enum expected
import java.util.Comparator;
nie wiem co poprawić :(

rh

Być może problemem jest to, że dajesz "import java.util.Comparator;" pomiędzy klasami. Importy powinny być chyba na początku.

YeeeZooo

Ostatni kod jest nie do końca widoczny.

YeeeZooo

Muszę przyznać, że ta lekcja jest dość trudna. Nie umiem z dokumentacji API wyczytać jak użyć tych metod :(((

Slawek

Kurdę, faktycznie jest jakiś problem z ucinaniem kodu po pętlach for, muszę to jakoś zmienić :/

LOREK

Drobny błąd w komparatorze:
if(p1.getWyplata() > p2.getWyplata()) return 1;
else if(p1.getWyplata() > p2.getWyplata()) return -1;


W takim wypadku nic się nie posortuje ale wystarczy zmienić znak na dole z > na na < dla sortowania malejącego.
Swoją drogą to bardzo dobry kurs, ogarnąłem jave w dwa dni a nie tak jak z tym ... Thinking in Java gdzie ogarnąłbym to dopiero po miesiącu. Krótko, zwięźle i na temat, to mi się podoba.

LOREK

hehe ucięło pól wiadomości w nawiasach kwadratowych
if(p1.getWyplata() > p2.getWyplata()) return 1;
else if(p1.getWyplata() < p2.getWyplata()) return -1;

Slawek

dzięki za poprawkę, przekleństwio wykropkowałem :P

Kamil

problem jest w tej metodzie, gdyz porownywane sa Stringi ze soba a oczekuje double ;)

Kamil

A sorki moj blad zamiast zdefiniowac wyplate pod double zdefiniowalem pod Stringa ;)

Michał

Quicksort nie działa w czasie logarytmicznym tylko n*log(n) (wartość oczekiwana czasu działania).

Marcin

Tez tak wlasnie chcialem zrobic. Moj wykladowca powiedzial ze to dobry pomysl ale komputer bedzie potrzebowal wiecej czasu na sprawdzenie pliku zewnetrznego niz jakbym przechowal go jako Array. Niestety wyklad o Arrays opuscilem :( wiec moge cos mylic.

Marcin

Mam pytanie, nie wiem czy do dpowiedniej lekcji. Mianowicie jezeli posiadam plik (slownik jezyka angielskiego) jak wgrac go do programu rzeby byl przechowywany jako Array. Pisze prace zaliczeniowa na 1 semestrze I mam napisac program, ktory bedzie pytal uzytkownika czy chce spolgloske czy samogloske. Po wyborze java ma wylosowac odpowiednio samogloske lub spolgoska (I tak 8 razy). Potem program powinien z tych 8 liter utworzyc jak najdluzsze slowa. wlasnie tu pojawia sie potrzeba zaladowania slownika do programu. Nasz wykladowca zaproponowal nam uzycie Arrays. Czy wiecie jak to zrobic? Przepraszam jesli wybralem zly temat lekcji

Sławek Ludwiczak

Za pomocą Arrays raczej nie wczytasz tablicy, o tym jak to zrobić możesz zobaczyć tutaj: http://javastart.pl/podstawy-jezyka/zapis-i-odczyt-z-plikow/ - gdzieś w komentarzach znajdziesz.
Arrays może się natomiast przydać do jakiegoś wyszukiwania w słowniku.

sammerro

Witam, przypuścimy, że mam dwie tablice tab1 i tab2 tego samego typu. Istnieje sposób, żeby połączyć je w jedną tab3, która ma elementów tyle co tab1+tab2 i najpierw są elementy z tab1, potem z tab2? Ogólnie móiwąc, czy da się tą drugą "doczepić" do pierwszej?

Sławek Ludwiczak

W standardowej bibliotece javy nie ma (albo ja nie kojarzę) metody, która pozwalałaby złączyć dwie tablice. Podejrzewam, że jest to związane np. z tym, że w tablicy możesz przechowywać zarówno typy proste jak i obiektowe - a w obu tych przypadkach kopiowanie, czy złączanie powinno odbywać się w diametralnie inny sposób - częściowo jest to wyjaśnione tutaj http://javastart.pl/efektywne-programowanie/plytkie-i-glebokie-kopiowanie-klonowanie-obiektow/

DawidJ

Na jakiej zasadzie działa metoda compare jak te poszczególne elementy tablicy są porównywane ?

DawidJ



DawidJ:

Na jakiej zasadzie działa metoda compare jak te poszczególne elementy tablicy są porównywane ?


tfu źle :D chodzi mi o Array.sort(prac, komp) do komparatora wpadaja dwa pierwsze elementy tablicy i zostaja porównane i co dalej ?
Marcin Kunert

Sortowanie oparte jest na algorytmie sortowania quicksort z podwójną karetką. Możesz o nim poczytać np tutaj: http://pl.wikipedia.org/wiki/Sortowanie_szybkie

whydakk

A jeśli klasa Szef dziedziczy po klasie Pracownik to w jaki sposób posortować tablicę szefów wg. premii?
Przykład klasy Szef:

public Szef extends Pracownik {
private int premia;

public Szef(, int premia){
;
this.premia = premia;
}

public int getPremia() {
return premia;
}

//jak tutaj przesłonić metodę compareTo, skoro interface Comparator jest typu ?

}

whydakk

Ucięło koniec zdania; ma być:
jak tutaj przesłonić metodę compareTo, skoro interface Comparator jest typu Pracownik?