ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • java string concatenation performance
    카테고리 없음 2007. 3. 10. 14:44
    2002년도에 쓰여진 tech tip에서도 비슷한 문제가 제기된 것을 보니 하루 이틀된 문제는 아니고 일반적으로 알려진 문제인 듯하다.

    저 예제(첫번째)에서의 결과는 내가 테스트한 것보다 정도가 좀 더 심해서 61890/16 =3,868 배의 차이를 보이고 있다. 350이 아닌 3800이다.

    얼핏 생각하기에 이정도의 차이가 나는 것은 좀 심하다는 생각이 들어서 계산을 시작해 보았다.

    tech tip 에 있는 첫번째 예를 들어 계산을 해 보면 다음과 같다. (내가 테스트한 것의 경우 integer를 string을 바꾸는 작업이 들어가고, 그 길이가 가변적이기 때문에(log10(n)) 계산하기 좀 더 쉬운 tech tip case로....)


    매 iteration에서 길이 1만큼의 strng이 추가되므로
    1. 이상적인 경우 copy의 양 - n
    2. 중간에 매번 결과 copy가 한번 일어나야 하는 경우의 copy의 양 - sum(k=(0,n), k))

    sigma 가 한번 더 씌워진다는 것을 의미한다. 즉, 알고리즘의 복잡도가 O(n)에서 O(n^2) 으로 바뀌게 된다. N 이 커지면 커질 수록 그 지수승으로 시간이 걸리게 되므로 수백.. 수천배의 차이가 나게 된다.


    String = string + string; .. java에서 syntatic sugar로 넣어 놓기는 했지만.. 써서는 안될, 혹은 매우 주의해서 써야할 것이다. sugar는 단거 이고, 단거는 danger이다.

    하지만 주의해서 써야한다고는 하지만, 중간 결과를 String으로 외부에 제공해야 하는 경우는 어쩔 수 없는 일인 듯 한다. 외부 interface 자체를 String이 아닌 StringBuffer로 하지 않는 이상 피해갈 수 없는 경우도 많이 있을 수 밖에 없다. tech tip 의 두번째 예가 비슷한 경우이다.

    그렇다면 왜 이런 문제가 생겼는지 python에서나 ruby에서는 왜 이런일이 안생기는지.. 시간나는데로 코드 확인하고 적어보겠다.

    참고로, 현재 짐작으로는 java String 자체가 immutable type이기 때문이리라고 생각하고 있다. 알고 있는가? Java String이 constant라는 것을...

    댓글

Designed by Tistory.