백준 1543번은 문자열에서 특정 단어가 중복되지 않게 최대 몇 번 등장하는지를 구하는 문제다.
처음엔 split()을, 이후엔 replace()를 사용했는데, for문을 사용하는 split()이 오히려 더 빠른 결과를 보였다.
이에 의문이 생겨 두 메소드의 내부 코드를 분석해 성능 차이의 원인을 알아보고자 했다.
여러 번 실행해봐도 후자의 실행시간이 유의미하게 길었다.
심지어 전자의 코드에는 for문까지 있었는데도 그랬다.
split:
input = br.readLine();
search = br.readLine();
result = input.split(search);
beforeSplitCnt = input.length();
afterSplitCnt = 0;
for (String s : result) {
afterSplitCnt += s.length();
}replace:
input = br.readLine();
search = br.readLine();
afterTrimSearch = input;
afterTrimSearch = afterTrimSearch.replace(search, "");🏃♂️ 내부 코드 분석
(1) split
public String[] split(String regex) {
return split(regex, 0);
}split() 메소드는 인자가 한개이면 limit를 0(제한 없이 배열을 만드는 설정)으로 전달하고, 인자가 두개이면 limit까지 받아 전달한다.
public String[] split(String regex, int limit) {
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))
{
int off = 0;
int next = 0;
boolean limited = limit > 0;
ArrayList<String> list = new ArrayList<>();
while ((next = indexOf(ch, off)) != -1) {
if (!limited || list.size() < limit - 1) {
list.add(substring(off, next));
off = next + 1;
} else { // last one
//assert (list.size() == limit - 1);
int last = length();
list.add(substring(off, last));
off = last;
break;
}
}
...
}
return Pattern.compile(regex).split(this, limit);
}문자의 길이가 1~2일 때는 fastpath를 통해 최적화를 진행한다. indexOf와 subString을 사용하였다.
하지만 문자열 길이가 충족되어도 특수문자(., *, +, | 등)가 들어가면 if문에서 탈출한다 🏃♂️➡️🏃♂️➡️
하지만 문자의 길이가 3 이상인 경우에는 compile() 메소드를 통해 정규식 엔진을 이용하게 된다.
하지만 이렇게 정규식을 사용할 때는 속도에 유의해야 한다. 왜냐하면 정규식은 인터프리터 기반의 상태 전이 머신이기 때문이다.
compile()의 내부 구조는 잘 알지 못하지만,
정규식이 복잡해질수록 이를 매칭하기 위한 상태 전이(NFA) 분기가 많아지며, 자바의 정규식 엔진처럼 백트래킹 기반으로 구현된 경우 매칭 시간이 기하급수적으로 증가할 수 있다고 한다.
정규식 엔진의 동작 원리:
정규식 문법을 토큰화 한 뒤 AST(추상 구문 트리) 형태로 변환하고, 이를 인터프리터 방식으로 매칭한다.
자바의 정규식 엔진은 NFA(Nondeterministic Finite Automaton) 기반의 백트래킹 방식으로 동작한다.
Go, Rust와 같이 DFA 기반의 정규식 엔진을 사용하는 언어는 백트래킹으로 인한 속도 저하가 적다.
(2) replace
반면, replace()는 정규식을 사용하지 않고, indexOf()와 StringBuilder를 사용한다.
replaceAll()은 정규식을 사용하기 때문에 두 메서드를 구분해서 봐야 한다.
따라서 길이가 속도에 주는 영향이 작아 비교적 일정한 속도를 보여준다.
public String replace(CharSequence target, CharSequence replacement) {
String trgtStr = target.toString();
String replStr = replacement.toString();
int thisLen = length();
int trgtLen = trgtStr.length();
int replLen = replStr.length();
if (trgtLen > 0) {
if (trgtLen == 1 && replLen == 1) {
return replace(trgtStr.charAt(0), replStr.charAt(0));
}
boolean thisIsLatin1 = this.isLatin1();
boolean trgtIsLatin1 = trgtStr.isLatin1();
boolean replIsLatin1 = replStr.isLatin1();
String ret = (thisIsLatin1 && trgtIsLatin1 && replIsLatin1)
? StringLatin1.replace(value, thisLen,
trgtStr.value, trgtLen,
replStr.value, replLen)
: StringUTF16.replace(value, thisLen, thisIsLatin1,
trgtStr.value, trgtLen, trgtIsLatin1,
replStr.value, replLen, replIsLatin1);
if (ret != null) {
return ret;
}
return this;
} else { // trgtLen == 0
...
StringBuilder sb = new StringBuilder(resultLen);
sb.append(replStr);
for (int i = 0; i < thisLen; ++i) {
sb.append(charAt(i)).append(replStr);
}
return sb.toString();
}
}🏃♂️ 속도 비교
", "와 같이 1~2글자 정도로 탐색하는 경우에는 속도에 최적화된 fastpath가 있는 split()가 유리하지만, 3글자 이상부터는 replace()가 더 안정적으로 속도를 낼 수 있어 보인다.
백준 1543번에서는 검색해야 하는 문자열을 50자까지 받기 때문에, replace()를 사용하는 것이 보다 안전할 것 같다.
+) - Split and join function or the replace function 글에서 코드 스니펫을 통해 성능 테스트를 할 수 있는데, 관련 부분을 잘 알지 못해 더 알아보아야 할 것 같다.
💡 그런데 왜 split가 더 빨랐죠?
나도 모르겠다 ... 🙃
아마 대부분의 테스트 케이스의 입력값이 1~2글자여서 fastpath를 타지 않았을까 추측해본다.
split() 의 속도가 빨랐던 이유를 알고 싶었는데, 의문은 풀리지 않은 채 테스트 데이터만 추측해보게 되었다 🫠
💭 회고 (추가 내용)
메모리 측면에서의 비교
메모리적 측면에서는 replace() 가 더 불리할 수도 있다.
왜냐하면 자바의 String은 불변(Immutable) 자료구조이기 때문에, replace()가 복잡한 연산 과정에서 토큰과 같은 문자열을 계속 새로 생성하기 때문이다.
하지만 split()도 배열 및 문자열 객체를 생성하기 때문에, 이 부분은 직접 속도를 비교해 보는 것이 좋을 것 같다.
자바 라이브러리와 계층적 구조
split() 메소드 안에서 indexOf(), subString() 등의 다른 메소드를 사용하는 것을 보고 순환 참조 문제가 생기진 않을까 생각했었다.
찾아보니 자바 라이브러리는 내부 구조가 계층적으로 설계되어 있어서, 상위 메서드가 하위 메소드를 조합하는 구조이기에 참조가 문제가 되지 않게 설계되었다고 한다.
주요 언어들의 정규식 엔진 비교
정규식에 ReDoS위험이 있어 중첩 반복을 피해야 한다는 것만 알고 있었는데, 원인이 백트래킹과 관련이 있는지는 이번에 처음 알았다.
그보다 정규식 엔진이 AST 구조인 것도 처음 알았다.
| 언어 | 정규식 엔진 | 특징 |
|---|---|---|
| Java | java.util.regex | NFA + 백트래킹 (ReDoS 위험 있음) |
| JavaScript | V8 / SpiderMonkey 내장 regex | NFA + 백트래킹 방식 (대부분 유사하게 느림) |
| Python | re 모듈 (C로 구현된 NFA 백트래킹) | ReDoS 위험 있음 |
| .NET (C#) | System.Text.RegularExpressions | 백트래킹 기반, ReDoS 가능 |
| Go | regexp vs regexp2 | 기본 regexp는 RE2 기반 (DFA, 안전) |
| Rust | regex crate | DFA 기반, ReDoS 방어 |
| Google RE2 | 독립된 엔진 (C++) | DFA 기반, 항상 O(n), 안전 |
| Perl | Perl regex engine | 가장 강력하지만 백트래킹 방식 (취약) |
