[Java] String의 split() 메소드 뜯어보기

코테를 풀다가 split()의 내부를 몰라 시간복잡도를 구할 수 없어서 공부해보고자 한다.

 

1. 호출

String [] str = br.readLine().split("/");

코드 작성 후 실행 후 "10/20/30/40"을 입력한다.

 

2. String의 split() 실행

public String[] split(String regex) {
    return split(regex, 0);
}

 

3. 구분자 포함여부가 있는 split() 실행

private String[] split(String regex, int limit, boolean withDelimiters) {
    /* fastpath if the regex is a
     * (1) one-char String and this character is not one of the
     *     RegEx's meta characters ".$|()[{^?*+\\", or
     * (2) two-char String and the first char is the backslash and
     *     the second is not the ascii digit or ascii letter.
     */
    char ch = 0;
    if (((regex.length() == 1 &&
            ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
            (regex.length() == 2 &&
                    regex.charAt(0) == '\\' &&
                    (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&
                    ((ch-'a')|('z'-ch)) < 0 &&
                    ((ch-'A')|('Z'-ch)) < 0)) &&
            (ch < Character.MIN_HIGH_SURROGATE ||
                    ch > Character.MAX_LOW_SURROGATE))
    {
        // All the checks above can potentially be constant folded by
        // a JIT/AOT compiler when the regex is a constant string.
        // That requires method inlining of the checks, which is only
        // possible when the actual split logic is in a separate method
        // because the large split loop can usually not be inlined.
        return split(ch, limit, withDelimiters);
    }
    Pattern pattern = Pattern.compile(regex);
    return withDelimiters
            ? pattern.splitWithDelimiters(this, limit)
            : pattern.split(this, limit);
}

매개변수

• `withDelimiters` 변수는 구분자를 포함해서 결과에 반영할지 체크하는 플래그이다. 디폴트로는 false로 구분자는 포함되지 않는다.
• `regex`는 regular expression의 약자로 문자를 분리할 때 사용할 정규식이다. 현재 `/` 문자열이 들어있다.

주석을 해석해보면 특정 조건인 경우 더 빠른 로직으로 실행한다고 한다. 조건은 아래와 같다.

1. 정규 표현식 문자 길이가 1개이면서, 정규표현식의 메타 문자가 아닐 때 "".$|()[{^?*+\\",
2. 정규 표현식 문자 길이가 2개이면서, 첫 번째 문자는 백슬래쉬이고, 두 번째 문자는 아스키 숫자나, 아스키 문자가 아닐 때

 

정규식의 메타 문자란?

• 정규식에서 특별한 의미를 가지는 문자들로, 문자열을 매칭하는 패턴이다.
  • 예: ., $, |, (, [, ^, ?, *, +, \ 등.
• 예를 들어, .는 "아무 문자 하나"를 의미한다. 따라서 이를 단순 문자로 사용하려면 이스케이프(\.)가 필요하다.

우선 "10/20/30/40"은 조건 1에 해당하기 때문에 조건문이 성립하여 다음 함수가 실행된다. 이 경우가 아니라면 Pattern 클래스로 정규식을 사용하여 문자열을 나눈다(이 경우 함수를 봤는데 아래 함수보다 훨씬 복잡하다.. 왜 이 방법이 빠르다는지 알겠는 정도다. 우선 Pattern 인스턴스 생성부터 복잡하고, Pattern -> macher 나오면서 어렵다... 그래도 같은 거는 문자열을 나눈 후 리스트에 담아서 배열 만든 후 리턴한다는 것 )

split(ch, limit, withDelimiters);

 

4. String regex -> char ch로 바뀐 split() 실행

이전 함수와 차이점은 매개변수 String regex가 char ch로 바꼈다. 매개 변수 ch에는 현재 `'/'`가 들어있다.

private String[] split(char ch, int limit, boolean withDelimiters) {
    int matchCount = 0;
    int off = 0;
    int next;
    boolean limited = limit > 0;
    ArrayList<String> list = new ArrayList<>();
    String del = withDelimiters ? String.valueOf(ch) : null;
    while ((next = indexOf(ch, off)) != -1) {
        if (!limited || matchCount < limit - 1) {
            list.add(substring(off, next));
            if (withDelimiters) {
                list.add(del);
            }
            off = next + 1;
            ++matchCount;
        } else {    // last one
            int last = length();
            list.add(substring(off, last));
            off = last;
            ++matchCount;
            break;
        }
    }
    // If no match was found, return this
    if (off == 0)
        return new String[] {this};

    // Add remaining segment
    if (!limited || matchCount < limit)
        list.add(substring(off, length()));

    // Construct result
    int resultSize = list.size();
    if (limit == 0) {
        while (resultSize > 0 && list.get(resultSize - 1).isEmpty()) {
            resultSize--;
        }
    }
    String[] result = new String[resultSize];
    return list.subList(0, resultSize).toArray(result);
}

코드가 많으니 쪼개서 살펴보자.

 

4-1. 변수 선언

int matchCount = 0;
int off = 0;
int next;
boolean limited = limit > 0;
ArrayList<String> list = new ArrayList<>();
String del = withDelimiters ? String.valueOf(ch) : null;

 해당 함수에서 사용할 변수들을 먼저 선언한다.

• matchCount : 몇 개로 쪼개졌는지 세는 카운트이다.
• off : 문자열을 나눌 때 쓰이는 포인터 중 하나로 start 인덱스를 담당한다.
• next: 문자열을 나눌 때 쓰이는 포인터 중 하나로 구분자를 가리키며, end 인덱스를 담당한다.
• limited: 최대 몇 개의 문자열으로 나눌지 결정되었는지 나타내는 플래그
• list : 구분자를 기준으로 나누어진 문자열이 들어가는 리스트
• del: 만약 결과에 구분자를 포함할 때, list에 넣기 위해 있는 String

4-2. 문자열 나누기

이제부터 본격적으로 문자열을 나눈다.

while ((next = indexOf(ch, off)) != -1) {
    if (!limited || matchCount < limit - 1) {
        list.add(substring(off, next));
        if (withDelimiters) {
            list.add(del);
        }
        off = next + 1;
        ++matchCount;
    } else {    // last one
        int last = length();
        list.add(substring(off, last));
        off = last;
        ++matchCount;
        break;
    }
}

 

1. while 조건

우선 while문이 끝나는 조건을 보면 next가 -1이 될 때로 즉 다음 구분자를 못찾을 때이다.

indexOf 함수는 문자열에서 특정 문자가 제일 먼저 발견된 인덱스를 리턴하는 함수이다. 만약 못찾으면 -1을 리턴한다. 

 

String indexOf()

public int indexOf(int ch, int fromIndex) {
    return isLatin1() ? StringLatin1.indexOf(value, ch, fromIndex, length())
            : StringUTF16.indexOf(value, ch, fromIndex, length());
}

 

String indexOfChar()

내부적으로 살펴보면 바이트 자료형으로 바꾼다음 하나 하나 비교하면서 처음 일치하는 것이 나올 때 리턴한다. 즉 문자열의 길이만큼 O(n)이다. 영어는 UTF-8 인코더로 바이트로 바뀌어서 아스키 코드랑 호환되기 때문에 1개의 문자가 1바이트가 될 수 있다.

@IntrinsicCandidate
private static int indexOfChar(byte[] value, int ch, int fromIndex, int max) {
    byte c = (byte)ch;
    for (int i = fromIndex; i < max; i++) {
        if (value[i] == c) {
           return i;
        }
    }
    return -1;
}

 

우선 이제 넘어와서 아래 코드가 실행되면 "10/20/30/40" 의 첫 구분자는 10뒤니깐 next는 2가된다.

next = indexOf(ch, off)

 

2. 문자열 나누기

while문 안으로 들어오면 마지막 문자열인지 아닌지 분기처리한다. limit가 없거나 아직 limit 개수 전이라면 if문 로직이 처리된다. if와 else 문의 차이점은 else의 경우 뒤에 구분자가 더 많이 나와도 하나의 문자열로 처리한다는 것이다.

if (!limited || matchCount < limit - 1) {
    list.add(substring(off, next));
    if (withDelimiters) {
        list.add(del);
    }
    off = next + 1;
    ++matchCount;
} else {    // last one
    int last = length();
    list.add(substring(off, last));
    off = last;
    ++matchCount;
    break;
}

•  공통 로직을 보면 off위치부터 next-1위치까지 substring 함수로 String을 자른 후 리스트에 추가한다. 
• 구분자를 포함하는지 확인 후, 포함되면 구분자도 리스트에 추가한다
• 다음 off을 업데이트 한다. next는 구분자의 인덱스를 가리키니 구분자 바로 뒤를 가리키게 된다.
• matchCount 증가

"10/20/30/40"에 적용해보면 off = 0, next = 2인 상태이고, "10"를 잘라서 `list`에 추가한다. 그리고 0이었던 off는 3이되어 "2"를 가리키게 된다. 

이런 방식으로 리스트에 "10", "20", "30"이 추가된다.

 

+ substring() 내부

 

내부 로직은 어떨까? 유효성 검사후 문자열 데이터가 저장된 내부 배열`value`에서 특정 부분을 참조하여 새로운 `String`을 만든다. 원래 `value`는 char 배열이었는데 Java9 이후부터 byte 배열로 바뀌었다고 한다. 그리고 길이만큼 새로운 메모리가 할당된다.

public String substring(int beginIndex, int endIndex) {
    if (beginIndex < 0) {
        throw new StringIndexOutOfBoundsException(beginIndex);
    }
    if (endIndex > value.length) {
        throw new StringIndexOutOfBoundsException(endIndex);
    }
    int subLen = endIndex - beginIndex;
    if (subLen < 0) {
        throw new StringIndexOutOfBoundsException(subLen);
    }
    return (beginIndex == 0 && endIndex == value.length) ? this
            : new String(value, beginIndex, subLen);
}

 

 

3. 남은 문자열 특수상황 처리

매칭되지 않은 경우 원래 문자열 반환

// If no match was found, return this
if (off == 0)
    return new String[] {this};

구분자와 매치되는 문자열이 하나도 없을 때로, 배열로 감싸서 리턴한다.

 

남아 있는 부분 추가

// Add remaining segment
if (!limited || matchCount < limit)
    list.add(substring(off, length()));

남아 있는 문자열을 처리한다. "10/20/30/40"에서 마지막 구분자는 30뒤에 있는 "/"이다. 그러므로 40을 리스트에 넣지 않은채 while문이 끝난다. 이때를 대비해서 있는 로직으로 마지막 요소를 추가한다.

 

빈 문자열 제거

// Construct result
int resultSize = list.size();
if (limit == 0) {
    while (resultSize > 0 && list.get(resultSize - 1).isEmpty()) {
        resultSize--;
    }
}

결과의 끝부분에 포함된 빈 문자열("")을 제거하여 결과 배열을 정리한다.

 

4. 리스트를 배열로 만들어서 리턴

String[] result = new String[resultSize];
return list.subList(0, resultSize).toArray(result);

이제 마지막이다. 

리스트의 사이즈대로 배열의 사이즈를 지정해서 생성하고, 배열에 값을넣어서 반환한다. 이로써 split의 역할이 끝난다.

 

 

5. 결론

반환 결과는 아래처럼 4개의 요소로 구성된 배열이다.

 

이 글의 목표인 시간 복잡도를 따져보자. split을 할 때 구별자가 1개라서 fast 방식을 사용할 때이다.

우선 탐색은 문자열의 길이 만큼하니 O(n)이다. 하지만 여기서 매번 substring으로 새로운 문자열을 생성하기 때문에 다소 비용이 있다. 그리고 리스트에 담고 마지막에 배열로 복사하니 나누어진 문자열의 개수만큼 비용이 들고, 메모리가 든다.

 

종합하면 O(n : 문자열의 길이) 정도로 걸린다. 생각보다 시간 비용은 크게 안들고 substring할 때마다 새로운 String 객체가 만들어진다는 사실을 염두해두고 사용하면 될 것 같다!