StringBuilder, StringBuffer, System.out.print, append

StringBuilder와 StringBuffer의 차이점은 간단하다.

synchoronized(동기화)가 있고 없고의 차이일 뿐이다.

StringBuilder는 synchoronized가 없고 StringBuffer는 synchoronized가 있다.

synchoronized는 Thread에 락을 걸어주는 역할을 한다.

다시 말해서 Thread에 락을 걸어줌으로써 다른 Thread에서 접근할 수 없게 된다는 말이다.

이로 인해 synchoronized를 해준 메소드나 변수는 thread safe 하게 된다.

즉 멀티스레드 환경에서 안정성을 가지게 된다.

하지만 synchoronized 해주게 되면 락을 걸고 풀어주는 과정에서 오버헤드가 발생하게 된다.

이 오버헤드는 한두 번이면 속도 차이가 별로 나지 않지만 만약 백만 번이라면 속도는 확연하게 차이 난다.

결론적으로 StringBuilder는 synchoronized를 하지 않는 대신 속도가 빠르지만
멀티스레드 환경에서 thread safe 하지 않다.

StringBuffer는 synchoronized를 해주는 대신 속도가 느리지만 멀티스레드 환경에서 thread safe 하다.

우리가 자주 사용하는 메소드 중에서 synchoronized를 사용하는 또 하나의 메소드가 있다.

바로 System.out.print()이다.

위에서도 말했듯이 synchoronized는 thread safe 하지만 속도가 느리다. 호출하는 횟수가 커지면 커질수록 말이다. 때문에 로그를 찍거나 디버깅을 할 때 System.out.print로 찍지 말라는 것이다.

알고리즘 문제를 풀 때도 여러 번 출력을 하는 문제에서 System.out.print로 일일이 출력을 하게 되면 속도가 상당히 저하된다.

그러므로 StringBuilder의 append메소드를 사용해서 문자열을 합쳐놨다가 한 번에 출력을 하는 것이 훨씬 더 효율적이다.

그렇다면 append메소드는 어떤 식으로 구성되어 있으며 시간 복잡도는 어떻게 될까.

StringBuilder와 StringBuffer는 동적 배열이다. 동적 배열을 구현하는 것은 공통적으로 그냥 배열의 크기를 계속해서 늘리는 것뿐이다.

append메소드 또한 배열의 크기를 늘리고 전 배열을 System.arraycopy메소드를 통해 복사하고 붙여 넣는 식으로 작동하게 된다.

배열을 복사하고 붙여 넣는 작업은 필연적으로 O(n)의 시간 복잡도를 갖게 된다.

System.arraycopy메소드 또한 시간 복잡도는 O(n)이다. 하지만 StringBuilder의 append메소드는 O(1)의 시간 복잡도를 가진다.

왜냐하면 append메소드에서 배열의 크기를 늘릴 때 전에 크기의 2배씩 확장하기 때문에 크기를 늘리는 O(n)의 작업은 그렇게 자주 발생하지 않게 된다.

그렇기에 append메소드는 상환 복잡도를 분석하면 amortized(분할상환 분석) O(1) 임을 알 수 있다.

결론적으로 계속 append를 했을 때 평균 복잡도는 O(1)인 것이다.

amortized(분할상환 분석)은 자료구조를 수행하는 경우에 필요한 시간을 비용으로 산정하고

이 비용의 평균을 구하는 분석방법이다.