Kurs Java Podstawy - rozszerzony

String, StringBuffer i StringBuilder

Istotnym zagadnieniem w każdym języku programowania oraz w większości programów jest przetwarzanie ciągów znaków - Stringów.

W języku Java Stringi zostały utworzone jako niemodyfikowalne - oznacza, to, że nie możemy na przykład dynamicznie dodawać do tego samego ciągu znaków czegoś nowego, aby tego dokonać zawsze musimy utworzyć nowy obiekt String.

Aby to zobrazować spójrzmy na przykład:

String s = "Kasia";
s = s+" i Tomek";

Utworzyliśmy tu jeden obiekt typu String, a następnie za pomocą operatora konkatenacji (łączenia) + dodaliśmy do niego kolejny człon.

Tak naprawdę nie zmodyfikowaliśmy jednak obiektu s, a przypisaliśmy do niego całkiem nową referencję. Gdy używamy operatora + w przypadku obiektów String, tak naprawdę najpierw tworzymy nowy obiekt StringBuilder, następnie wywołujemy jego metodę append() z argumentem w postaci liczby, innego ciągu znaków, lub pojedynczego znaku. Na końcu musimy taki obiekt zamienić oczywiście z powrotem na String za pomocą metody toString().

Powyższy przykład wygląda więc tak naprawdę(niejawnie) następująco:

String s = "Kasia";
s = new StringBuilder(s).append(" i Tomek").toString();
System.out.println(s);

Jak widzimy złożoność obliczeniowa jest w tym wypadku po prostu fatalna i jeśli ktoś chciałby używać operatora + w przypadku Stringów na przykład w pętli to jest to bardzo złą praktyka programistyczną. Spójrzmy więc na przykład i zastanówmy się jak można by go usprawnić.

public class Strings1 {
	public static void main(String[] args) {
		String s = "a";
		long start = System.nanoTime();
		for(int i=0; i<10000; i++) {
			s = s+"a";
			//s = new StringBuilder(s).append("a").toString();
		}
		System.out.println("Time1: "+(System.nanoTime()-start));
	}
}

Jak widzimy nie wykonujemy tutaj zbyt skomplikowanej operacji dodajemy jedynie na końcu naszego Stringa 10 000 razy literę "a" (równie dobrze mógłby to być znak 'a'). W komentarzu widać co tak naprawdę się dzieje. Konkretnie tworzymy 10 000 obiektów typu StringBuilder oraz na każdym z nich wywołujemy 3 metody (w sumie to 2 i konstruktor). Dodatkowo wyświetlamy czas w nanosekundach jaki zajęło wykonanie tego przykładu - przyda się do porównania dalszych, efektywniejszych rozwiązań.

Jak sobie z tym problemem poradzić?

Przecież można utworzyć tylko jeden obiekt StringBuilder jeszcze przed pętlą, a wewnątrz niej wywoływać jedynie metodę append(), na kończu przypisując do s wynik metody toString(). Poprawmy więc nasz przykład:

public class Strings2 {
	public static void main(String[] args) {
		String s = "a";
		long start = System.nanoTime();
		StringBuilder sB = new StringBuilder(s);

		for(int i=0; i<10000; i++) {
			sB.append("a");
		}

		s = sB.toString();
		System.out.println("Time2: "+(System.nanoTime()-start));
	}
}

Porównajmy jeszcze czasy jakie uzyskałem na swoim komputerze (Intel Dual Core T4200, 3GB DDR2):

Time1: 172046024
Time2: 3143797

Jak widać zyskaliśmy aż 2 rzędy czasu, konkretnie metoda z wykorzystaniem jednego obiektu StringBuilder wykonała się ok 55 razy szybciej niż program używający +.

Co ciekawe programiści Javy dają nam do dyspozycji jeszcze jedną klasę do "modyfikowania" ciągów znaków. Jest to konkretnie StringBuffer.

Posiada ona identyczne metody jak StringBuilder i na pierwszy rzut oka nie widać między nimi żadnej różnicy, ponieważ jest ona dosyć subtelna - StringBuffer jest klasą synchronizowaną, natomiast StringBuilder nie. W drugim przypadku powoduje to jeszcze dodatkowe przyspieszenie i na poziomie początkującego programisty i programów jednowątkowych jest najlepszym rozwiązaniem. Sprawdźmy więc jaki wynik uzyskamy przy StringBufferze.

public class Strings {
	public static void main(String[] args) {
		String s = "a";
		long start = System.nanoTime();
		StringBuiffer strB = new StringBuffer(s);
		for(int i=0; i<10000; i++)
			strB.append("a");
		s = strB.toString();
		System.out.println("Time3: "+(System.nanoTime()-start));
        }
}

W tym przypadku czas wyniósł: Time3: 1892437.

Zestawiając wszystkie 3 metody:

Time1: 172046024

Time2: 1892437

Time3: 3143797

Jak widać klasa StringBuilder okazała się dodatkowo ponad 1,5 raza szybsza od StringBuffer.

Najważniejsze w tej lekcji jest to, aby używać operatora + na Stringach, gdy nie kosztuje nas to ani dużo czasu, ani pamięci - czyli w zasadzie jedyne słuszne miejsce, gdzie można to robić to wnętrze metody print i podobnych do wyświetlania pojedynczych wyników. W każdym innym przypadku powinniśmy używać klasy StringBuffer, lub StringBuilder, szczególnie, gdy wielokrotnie dodajemy coś do naszego obiektu jak w podanych powyżej przykładach.

Zadania do samodzielnego wykonania:

Skompiluj powyższe przykłady na swoim komputerze i porównaj czas ich wykonania. Dla testu możesz także zwiększyć zakres pętli z 10 000, do 100 000 i zobaczyć jak wielka jest ta różnica naprawdę (ostrzegam, że wykorzystując operator konkatenacji + można się znudzić czekaniem na wynik).

Komentarze

YeeeZooo

aha czyli najpierw mamy "Kasia" w jakimś miejscu w pamięci, potem w tym samym miejscu w pamięci pojawia się "Kasia i Tomek", a potem "Kasia i Tomek i Bartek" - dobrze rozumiem?

Slawek

Nowy napis (literał) zostaje zapisany w innym, losowym, wolnym miejscu pamięci.

YeeeZooo

W przykładzie pierwszym
String s = "Kasia";
s = s+" i Tomek";
wyświetlając s, wynikiem będzie Kasia i Tomek
Jeśli dodamy kolejną linię np:
s = s+" i Bartek";
i wyświetlimy znowu s, to wynikiem będzie Kasia i Tomek i Bartek
i tego nie rozumiem bo pisząc że nie modyfikujemy obiektu s, myślałem, że będzie w nim cały czas Kasia, więc powinno być w drugim wypadku Kasia i Bartek, czy nie?

Slawek

niemodyfikowalny należy rozumieć tak, że w przypadku, gdy robisz
s = s+” i Tomek”;
albo dalej
s = s+” i Bartek”;
to tworzysz całkiem nowy obiekt, stary, czyli np "Kasia" po prostu przestaje istnieć.

Przemuś

"Tak naprawdę nie zmodyfikowaliśmy jednak obiektu s, a przypisaliśmy do niego całkiem nową referencję."
o ile pamiętam z poprzednich lekcji, nie możemy przypisać do obiektu referencji, tylko obiekt do referencji ;-)

Damian

Wynik dla (AMD Phenom(tm) II X4 955 Processor 3.20 GHz; 12 GB RAM DDR3; Win7 64b), pętle po 1 mln powtórzeń:
Time1: 749535814839 ( ok. 12.5 minuty)
Time2: 20602651 ( ok 0.021 sekundy)
Time3: 15691949 ( ok 0.016 sekundy)
Różnica między 'najpopularniejszą' metodą łączenia stringów, a dwoma pozostałymi naprawdę robi ogromne wrażenie (~36000:1 i ~48000:1). Świetny artykuł, naprawdę otwiera oczy. Z chęcią zobaczyłbym więcej treści o tematyce optymalizacyjnej.

Ja

Co to za dno?
Jak można napisać cały artykuł na temat tylko dodawania literek do stringa?
Może tak łaskawie więcej opisać metod z tych klas?

demonix

a może tak do dokumentacji by się zajrzało, ktoś kto jest początkujący zostanie naprowadzony na temat, a reszta w dokumentacji jest.