Zapytano mnie o niezmienne łańcuchy w Javie. Zadanie polegało mi na napisaniu funkcji, która połączyła liczbę „a” z łańcuchem.
Co napisałem:
public String foo(int n) {
String s = "";
for (int i = 0; i < n; i++) {
s = s + "a"
}
return s;
}
Zapytano mnie wtedy, ile ciągów wygenerowałby ten program, zakładając, że nie nastąpi wyrzucanie elementów bezużytecznych. Moje myśli dla n = 3 były
- „”
- "za"
- "za"
- „aa”
- "za"
- „aaa”
- "za"
Zasadniczo w każdej iteracji pętli tworzone są 2 łańcuchy. Jednak odpowiedź brzmiała n 2 . Jakie łańcuchy zostaną utworzone w pamięci przez tę funkcję i dlaczego tak jest?
Odpowiedzi:
Ciągi 1 (
""
) i 2 ("a"
) są stałymi w programie, nie są one tworzone jako część rzeczy, ale są „internowane”, ponieważ są stałymi, o których kompilator wie. Przeczytaj więcej na ten temat na stronie interning String na WikipediiTo również usuwa ciągi 5 i 7 z liczby, ponieważ są one takie same
"a"
jak Ciąg # 2. To pozostawia ciągi # 3, # 4 i # 6. Odpowiedź brzmi: „Tworzone są 3 ciągi dla n = 3” przy użyciu kodu.Liczba n 2 jest oczywiście niepoprawna, ponieważ przy n = 3 byłoby to 9, a nawet w najgorszym przypadku odpowiedź to tylko 7. Jeśli twoje nie internowane łańcuchy były poprawne, odpowiedź powinna wynosić 2n + 1.
Więc pytanie, w jaki sposób należy to zrobić?
Ponieważ String jest niezmienny , potrzebujesz mutowalnej rzeczy - czegoś, co możesz zmienić bez tworzenia nowych obiektów. To jest StringBuilder .
Pierwszą rzeczą do obejrzenia są konstruktory. W tym przypadku wiemy, jak długi będzie łańcuch, i istnieje konstruktor,
StringBuilder(int capacity)
co oznacza, że przydzielamy dokładnie tyle, ile potrzebujemy.Następnie
"a"
nie musi to być ciąg znaków, ale raczej postać'a'
. Ma to niewielki wzrost wydajności podczas wywoływaniaappend(String)
vsappend(char)
- dziękiappend(String)
metodzie metoda musi dowiedzieć się, jak długi jest ciąg znaków i trochę nad tym popracować. Z drugiej stronychar
zawsze ma dokładnie jedną postać.Różnice w kodzie można zobaczyć w StringBuilder.append (String) vs StringBuilder.append (char) . Nie należy się tym zbytnio przejmować, ale jeśli próbujesz wywrzeć wrażenie na pracodawcy, najlepiej zastosować najlepsze możliwe praktyki.
Więc jak to wygląda, kiedy go poskładasz?
Utworzono jeden StringBuilder i jeden String. Nie trzeba było internować żadnych dodatkowych łańcuchów.
Napisz inne proste programy w Eclipse. Zainstaluj pmd i uruchom go na pisanym kodzie. Zwróć uwagę na to, na co narzeka i napraw te rzeczy. Znalazłby modyfikację ciągu za pomocą + w pętli, a gdybyś zmienił ją na StringBuilder, może znalazłby początkową pojemność, ale z pewnością dostrzegłby różnicę między
.append("a")
i.append('a')
źródło
Przy każdej iteracji operator
String
tworzy nową+
i przypisuje jąs
. Po powrocie wszystkie oprócz ostatniego są zbierane.Stałe ciągów, takie jak
""
i"a"
nie są tworzone za każdym razem, są to ciągi wewnętrzne . Ponieważ ciągi są niezmienne, można je dowolnie udostępniać; dzieje się tak ze stałymi ciągów.Aby skutecznie łączyć łańcuchy, użyj
StringBuilder
.źródło
Jak wyjaśnia MichaelT w swojej odpowiedzi, twój kod przydziela O (n) ciągów. Ale przydziela także O (n 2 ) bajtów pamięci i działa w czasie O (n 2 ).
Przydziela O (n 2 ) bajtów, ponieważ przydzielane ciągi mają długości 0, 1, 2,…, n-1, n, co sumuje się do (n 2 + n) / 2 = O (n 2 ).
Czas jest również równy O (n 2 ), ponieważ przydzielenie i-tego ciągu wymaga skopiowania (i-1) -tego ciągu, który ma długość i-1. Oznacza to, że każdy przydzielony bajt musi zostać skopiowany, co zajmie czas O (n 2 ).
Może właśnie to mieli na myśli ankieterzy?
źródło