이 글에 달린 답글중에 답을 미처 못 한 부분이 있었습니다.
>in loop 안에 변수 선언하는게 O(1)이고 O(N) 이라는게 무슨 말인지 모르겠네요.
> int 고 string 이고 컴파일러 상에서의 차이는 아마 없을텐데요. 단지 스코프를 최소화하는게 정설이기 때문에 in loop 안에 선언하는걸 권장 할 뿐 아닌가요.
다른 부분에 신경을 쓰느라 답이 늦었습니다.
여하튼 설명하죠.
원글에서 논하던 부분은 오브젝트 형성에 관련한 부분입니다.
루프 안의 local variable을 지정해서 소모하는 문제지요.
이게 primitive 타입이라면 상관 없는데 object 타입에 연산자를 지원한다면 문제가 됩니다.
편의상 getNumber()와 getWord()란 함수가 있다고 치고, 예제를 봅시다.
A)
int sum = 0;
while() {
int i = getNumber();
sum += i;
}
B)
String line = "";
while() {
String word = getWord();
line += word;
}
A)와 B)는 로직상으로 보면 거의 동일한 알고리즘입니다.
매 루프에 정보의 일부분을 받고, 그걸 축적하는 거죠.
문제는 A)의 int는 primitive인데 B)의 String은 오브젝트입니다. 게다가 수정이 불가능한 immutable한 놈이죠.
이러면 어찌되느냐?
A)의 루프안에서 sum을 업데이트하는 건 sum에 담겨있는 정보를 바꾸는 거에 불과합니다. 더 이상의 메모리 사용이 없죠.
B)의 루프안에서 line을 업데이트하는 건 사실 새로운 오브젝트를 생성합니다. 추가로 메모리를 사용하는 겁니다.
가령 예를 들면
"this sentence is short"가 인풋이라면,
첫번째 루프에선
word = "this" 가 생성되고, line = "this"가 따로 생성됩니다. 전에 있던 line = ""는 GC에 붙들려갑니다(고 알고 있습니다).
두번째 루프에선
word = "sentence"가 생성되고, line = "this sentence"가 또 따로 생성됩니다. 전에 있던 line = "this"는 또 사라집니다.
즉 오브젝트의 내용을 바꾸는 게 아니라 오브젝트 하나를 새로 만들어내는 일이죠.
자바는 주 언어가 아니기때문에 잘 모르겠습니다만, 루프 안에서 GC에 매번 보내면 O(N)만큼의 시간이 추가로 소모됩니다.
루프가 끝난 뒤에 한꺼번에 포인터 정리를 하는 알고리즘이라면 그게 해소될 때까지 O(N)만큼의 메모리가 잡혀있는 셈입니다.
유명한 마인크래프트 퍼포먼스 문제는 후자의 경우가 발동되었던 거고요.
이걸 피하기 위해 그러면 어떻게 하느냐?
StringBuilder를 쓰면 됩니다.
StringBuilder sb = new StringBuilder();
while() {
String word = getWord();
sb.append(word);
}
return sb.toString();
이러면, 매 루프에서 새로운 오브젝트를 생성하지 않습니다. 단지 sb 하의 정보가 업데이트될 뿐이죠.
글을 좀 급하게 쓰느라 O(N)이라고 대충 써 넘겼습니다.
이렇게 답을 남깁니다.
이상.
글쓰기