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

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 ² . Jakie łańcuchy zostaną utworzone w pamięci przez tę funkcję i dlaczego tak jest?

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

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.

Jak wyjaśnia MichaelT w swojej odpowiedzi, twój kod przydziela O (n) ciągów. Ale przydziela także O (n ² ) bajtów pamięci i działa w czasie O (n ² ).

Przydziela O (n ² ) bajtów, ponieważ przydzielane ciągi mają długości 0, 1, 2,…, n-1, n, co sumuje się do (n ² + n) / 2 = O (n ² ).

Czas jest również równy O (n ² ), 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 ² ).

Może właśnie to mieli na myśli ankieterzy?