StringBuilder 에 저장되어 있는 내용을 바꾸려다 replace() 와 setCharAt() 이 있음을 알게 되었다. 함수명만 봐도 replace()가 느릴거라 생각했지만, 속도차이가 조금일거라 예상했다. 써본 결과 replace() 의 속도가 너무나도 느렸다. 왜 그렇게나 느린지에 대해 궁금증이 생겼고, 코드를 보면서 해결해보기로 했다.

먼저 setCharAt() 이다

1
2
3
4
5

public void setCharAt(int index, char ch) {
    if ((index < 0) || (index >= count))
        throw new StringIndexOutOfBoundsException(index);
    value[index] = ch;
}

보시다시피 간단하다. 단순히 인덱스에 char 를 넣는다. 시간복잡도는 O(1) 이다.

그다음 replace() 이다.

1
2

StringBuilder sb = new StringBuilder("abcde");
sb.replace(0, 4, "fg");

위와 같이 호출하여 스트링이 어떻게 변환되어가는지를 관찰하겠다. “abcde” 에서 0 ~3 번째까지의 문자를 “fg” 로 치환하는 결과를 예상한다. 참고로 두번째 파라미터는 해당 인덱스 전까지 치환한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public AbstractStringBuilder replace(int start, int end, String str) {
    if (start < 0)
        throw new StringIndexOutOfBoundsException(start);
    if (start > count)
        throw new StringIndexOutOfBoundsException("start > length()");
    if (start > end)
        throw new StringIndexOutOfBoundsException("start > end");
    if (end > count)
        end = count;
    int len = str.length();
    int newCount = count + len - (end - start);
    ensureCapacityInternal(newCount);
    System.arraycopy(value, end, value, start + len, count - end);
    str.getChars(value, start);
    count = newCount;
    return this;
}

유심히 봐야할 부분은 15, 16 번째 코드이다.

arraycopy() 와 getChars() 를 통해 “abcde”가 어떻게 “fg” 로 되는지 확인해보겠다.

• 변환전 초기값

  StringBuilder의 default 크기가 21이기에 “abcdef” 외에도 여분의 여유공간이 있다. 이것은 성능상 문제를 야기함으로 되도록 최초 크기값을 설정하는 것이 좋다. 일단 변환전의 모습을 아래에서 확인할 수 있다.

• System.arraycopy 실행 후 변환된 값

  arraycopy() 는 src 에 있는 문자열을 dest 에 복사하는 기능이다. 아래에서 보면 첫번째 value의(src) end 인덱스부터 count - end까지 copy하여 두번째 value의(dest) start + len인덱스에 삽입하는 것을 확인할 수 있다.

• String.getChars 실행 후 변환된 값

  getChars()의 내부는 다시 System.arraycopy()를 호출하는 구조이다. 허나 dest 문자열에 String 문자열을 start 인덱스부터 덮어쓰는 구조이다. 아래에서 보면 value 문자열의(dest) start인덱스부터 str문자열로 덮어쓰는 것을 확인할 수 있다.

그럼 여기서 생기는 의문점은 “ StringBuilder의 버퍼에 “fgefef”가 저장되어 있으니 출력값은 “fgefef”가 된다는 말인가?” 일 것이다. 결과는 그렇지 않다.

결과는 “fgef”이다. 왜 일까? 그건 StringBuilder의 count 값 때문이다. StingBuilder의 크기는 버퍼가 갖고있는 문자열의 실제 크기가 아닌 논리 구조상의 길이인 count가 가지고 있다. 따라서 length를 출력하여도 4가 나오고 문자열을 출력하여도 “fgef”가 나오는 것이다.

1

int newCount = count + len - (end - start);

replace() 함수 실행시 count 의 값은 위 코드에 의해 결정되기 때문에 실제 버퍼의 크기가 아닌 replace 결과에 맞게 크기가 재설정된다.

결론
두 함수를 살펴본 결과 문자를 하나만 바꾸거나 같은 크기의 문자열을 대치하는 경우 replace()의 arraycopy()는 같은 문자열을 덮어쓰는 불필요한 작업을 하게 되며 따라서 오버헤드가 발생한다. 알고리즘이나 반복적으로 문자열을 대치해야하는 경우 시간이 더욱 오래걸리는 것을 체험할 수 있다. 시간복잡도는 O(2N) 이지만 setCharAt()와 비교할때 N이 클수록 그리고 중첩 for문 앞에서 실행될수록 성능저하가 발생할 수 있다. 문자를 하나만 바꾸거나 같은 크기의 문자열을 대치하는 경우는 setCharAt()을 써야겠다.