Ile łańcuchów jest tworzonych w pamięci podczas łączenia łańcuchów w Javie?

17

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

  1. „”
  2. "za"
  3. "za"
  4. „aa”
  5. "za"
  6. „aaa”
  7. "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?

ahalbert
źródło
15
Jeśli dostaniesz propozycję tej pracy, uciekaj, biegnij bardzo szybko .......
mattnz
@mattnz z wielu powodów (i nie tylko z powodu napisanego kodu).
3
To zajmuje środowisko wykonawcze O (n ^ 2), chyba że JIT zoptymalizuje pętlę, ale nie tworzy ciągów n ^ 2.
użytkownik2357112 obsługuje Monikę

Odpowiedzi:

26

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 (7)

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 Wikipedii

To 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ływania append(String)vs append(char)- dzięki append(String)metodzie metoda musi dowiedzieć się, jak długi jest ciąg znaków i trochę nad tym popracować. Z drugiej strony charzawsze 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?

public String foo(int n) {
    StringBuilder sb = new StringBuilder(n);
    for (int i = 0; i < n; i++) {
        sb.append('a');
    }
    return sb.toString();
}

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')

Społeczność
źródło
9

Przy każdej iteracji operator Stringtworzy 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.

9000
źródło
Ludzie podczas wywiadu faktycznie debatowali nad tym, czy literał był, czy nie, i zdecydowali, że literały powstają za każdym razem. Ale to ma większy sens.
ahalbert
6
Jak „debatujesz” nad tym, co robi język, na pewno czytasz specyfikację i wiesz na pewno, albo nie jest ona zdefiniowana, a zatem nie ma poprawnej odpowiedzi .....
mattnz
@mattnz Może być interesujące wiedzieć, co robi kompilator / środowisko wykonawcze, którego używasz, nawet jeśli chodzi o szczegóły implementacji. Dotyczy to zwłaszcza wydajności.
svick
1
@svick: Możesz dużo zyskać, przyjmując założenia, następnie kompilator jest aktualizowany, optymalizacja zmieniana itp. Zachowanie zmienia się powodując błędy, ponieważ polegałeś na nieokreślonym zachowaniu, a raczej na zachowaniu zdefiniowanym. Wiesz, co mówią o optymalizacji - a) pozostaw to ekspertom i b) jeszcze nie jesteś ekspertem. :) Jeśli zależność opiera się wyłącznie na wydajności, ale nadal na specyfikacji języka, tracisz tylko wydajność. Wiele razy widziałem kod, który opierał się na nieokreślonym lub specyficznym dla kompilatora zachowaniu, psującym się w nieoczekiwany sposób (głównie C i C ++).
mattnz
@mattnz Więc jak proponujesz podejmować decyzje związane z wydajnością? Zazwyczaj najlepsze, co można uzyskać ze specyfikacji / dokumentacji, to złożoność dużych O, ale to nie wystarczy. W każdym razie wydajność zawsze będzie zależeć od implementacji, więc myślę, że można polegać na szczegółach implementacji, jeśli chodzi o wydajność.
svick
4

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?

svick
źródło
Czy równanie nie powinno być (n ^ 2 + n) / 2, jak tutaj ?
HeyJude,