java split 메소드 : stringtokenizer보다 항상 느릴까요?

 네이버 블로그에 올린 옛날 글에 질문이 하나 달렸습니다. 그 질문에 대한 답변을 해 보겠습니다. java에서 어떠한 구분자를 기준으로 나누기 위해서 StringTokenizer를 쓰는 방법이 있습니다. 그런데, split라는 메서드도 존재합니다. 이 둘은 언제 잘 쓰면 좋을까요? 그리고 토크나이저를 쓰는 게 항상 올바른 선택이고, 항상 빠를까요? StringTokenizer의 내부를 보겠습니다.

 

 

---

 먼저 토크나이저의 생성자를 보면, 3개의 인자를 가지는 생성자를 호출한다는 것을 알 수 있습니다.

 

 

 여기에서, delimiters, currentPosition, newPosition 등을 setting 하는 것을 알 수 있습니다. hasSurrogate 라는 boolean 변수도 있다는 것을 알 수 있습니다. 그리고 delimCodepoints 라는 int 배열도 있음을 알 수 있는데요. 이모지와 같은, utf16에서 2byte로 표현이 안 되는 문자가 delimiter로 들어오는 경우, hasSurrogate를 true로 바꿔놓고 delimCodepoints를 활성화 시킵니다.

 

 일단 저는 한글, 영문자로만 이루어진 어느 문자열을 가지고 조작할 것입니다. 그러니, surrogate는 생각하지 않으셔도 됩니다. 토크나이저에서 많이 쓰이는 것은 hasMoreTokens와 nextToken이 있을 겁니다. 이들이 어떤 메서드를 호출하는지 보겠습니다.

 

 

 일단, hasMoreTokes는 skipDelimiters를 호출합니다.

 

 

 다음에 nextTokens는 skipDelimiters와 scanTokens를 호출합니다. 이 둘의 복잡도에 지배가 되겠네요.

 

 

 scanToken 안에는 String의 indexOf 메서드가 있습니다.

 

 

 skip 안에도 indexOf가 있습니다. charAt를 제가 복잡도에 고려하지 않는 이유는, 구분자 문자열이 상당히 클 경우에는 charAt보다, 구분자 문자열에서 c라는 것을 찾는 비용이 훨씬 많이 들어가기 때문입니다. 그리고 이것은 while loop를 1번 돌 때마다 호출됩니다. 1번 돌 때 마다 position은 1만큼 증가합니다.

 

 

indexOf(ch) 안으로 들어가 보겠습니다. 그러면, 내부적으로 indexOf(ch,0)을 호출합니다.

 

 

 다른 것은 볼 필요가 없습니다. 1558번째 줄의 for loop만 보시면 됩니다. fromIndex가 0이였고, max가 value.length였습니다. 그런데, value는 Tokenizer의 구분자 배열의 진짜 내용을 담고 있는 char형 배열입니다.

 

 

 당연한 이야기겠지만, indexOf는 this의 value 배열의 길이가 길면 길수록 오래 걸립니다. 따라서, StringTokenizer를 써서, 토큰을 자르는 연산을 할 때 시간 복잡도는 O(|string| x |delimiter|)가 됩니다. |delimiter|가 별 거 아니여 보입니다만, 영문자와 숫자, 한글이 섞여 있는 문자열에서 한글을 구분자로 삼아서 토큰을 끊어내려고 하는 경우에 문제가 발생할 수 있어요.

 

 한글 집합은 11000개가 넘기 때문입니다. 연산의 대상이 되는 문자열의 길이가 200만이라고 한다면 어떨까요?

 

 

 delim.indexOf('K')? 생각만 해도 매우 끔찍합니다. for loop가 2중으로 걸려있고, 하나는 target의 길이, 다른 하나는 구분자의 길이만큼 정직하게 돌 테니까요.

 

 

---

 간단하게 실험을 해 보겠습니다. 프로그램은 복잡하지 않습니다.

 

 Random 클래스를 이용해서 길이 200만의, 소문자로만 이루어진 랜덤한 문자열을 생성합니다. 다음에 구분자는 한글 문자가 됩니다. deli에 '가'부터 '힣'을 넣는 것만 봐도 알 수 있는 부분입니다.

 

 

 타겟 문자열 string 안에는 구분자가 없으므로, Token이 1개가 나올 겁니다. 저는 그 Token 중에서 가장 앞에 있는 문자만 뽑도록 하겠습니다. 다음에, 토큰을 구분하는데 걸리는 시간을 측정하기 위해서 currentTimeMillis를 호출하였습니다.

 

 

 그랬더니 5992가 나왔습니다. 5.9초가 걸렸다는 의미입니다.

 

 

---

 그런데, 한글만을 구분자로 걸러내야 하는 경우에는 아주 간단하게 정규식으로 작성할 수 있습니다.

 

 

 일단 build를 3번 호출합니다. 그리고 중간에 "가나요"와 "꼴지를 가나요" 라는 문자열을 넣습니다. string에는 split 메서드가 있습니다. 이것은 정규식 표현을 받는데요. [가-힣]은 한글 집합 전체를 의미합니다. 그리고 1단어입니다. 이 메서드는 조심해야 할 점이, 길이가 0인 문자열도 나올 수 있다는 점입니다.

 

 

 그렇기 때문에, length가 0인 경우는 따로 걸러냅니다.

 

 

 build 메서드를 보니, 666666의 길이를 가지는, 알파벳 소문자로만 이루어진 문자열을 넣는 것으로 보입니다. 그러면, 대충 길이가 200만 정도네요. 길이가 200만인 문자열에서 한글을 구분자로 끊어내는 작업은 split로 했을 경우에 얼마나 걸릴까요?

 

 

 놀랍게도 47만큼이 걸립니다. 0.047초. StringTokenizer보다 빨랐습니다. 구분자가 한글 집합이라던지, 한자 집합이라던지. 즉, 구분자가 매우 많은 경우에 StringTokenizer는 상당히 비효율적으로 동작합니다. delimiter 배열의 길이가 굉장히 길어지기 때문입니다. 그 상황에서 split하고, 토크나이저 둘 중에 하나를 쓰라고 하면, split가 좋은 선택이 될 수 있습니다. 당연하게도, regex 패턴을 이용해서 끊어야 하는 경우에도 split는 고려해 볼 만한 옵션입니다.

 

 이 메서드는 regex 표현을 받기 때문에, 정규 표현식만 잘 써먹는다면, 꽤 유용한 함수가 될 수 있습니다. 이것이 내부적으로 어떻게 동작하는지는 추후에 다시 언급을 하도록 하겠습니다.