왜 배열 방식이 더 빠를까? - Java 문자열 처리 고찰

한·2024년 12월 1일
GCJavaStringBuilderarraystream공간복잡도시간복잡도

https://school.programmers.co.kr/learn/courses/30/lessons/181942

주말에 프로그래머스 해당 코딩 문제를 풀다가 의문이 생겼다.
과연 어떤 방식으로든 같은 효율성이 나올까?

먼저 프로그래머스의 문자열 섞기 문제를 보자

필자는 StringBuilder, Stream, Array 방식으로 3가지로 풀어보았다. 먼저 과연 시간 복잡도와 공간 복잡도는 같을까?

문자열 섞기 문제의 시간 복잡도 및 공간 복잡도 비교

StringBuilder

class Solution {
    public String solution(String str1, String str2) {
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < str1.length(); i++) {
            char ch1 = str1.charAt(i);
            char ch2 = str2.charAt(i);
            sb.append(ch1 + "" + ch2); // 문자열 연결
        }
        
        return sb.toString();
    }
}

시간 복잡도

  • for 루프: 문자열 길이 n에 따라 n번 순회 → O(n)
  • StringBuilder.append: 각 호출은 O(1)이지만, n번 호출 → O(n)
    ⇒ 총 시간 복잡도: O(n)

공간 복잡도

  • StringBuilder 내부 배열: 길이 2n의 char[] 배열 생성 → O(n)
  • 최종 문자열(String): 길이 2n의 char[] 배열 생성 → O(n)
    ⇒ 총 공간 복잡도: O(n)

Stream

import java.util.stream.IntStream;

class Solution {
    public String solution(String str1, String str2) {
        return IntStream.range(0, str1.length()) // 인덱스 생성
                        .mapToObj(i -> "" + str1.charAt(i) + str2.charAt(i)) // 각 위치의 문자 결합
                        .reduce("", String::concat); // 문자열 연결
    }
}

시간 복잡도:

  • IntStream.range: 길이 n 스트림 생성 → O(n)
  • mapToObj: n번 호출, 각 호출은 O(1) (문자 결합) → O(n)
  • Collectors.joining: n개의 부분 문자열을 병합 → O(n)
    ⇒ 총 시간 복잡도: O(n)

공간 복잡도:

  • 스트림 처리 중간 객체: 각 i에 대해 새 String 객체 생성 → O(n) (중간 객체 크기 누적)
  • 최종 문자열(String): 길이 2n의 char[] 배열 생성 → O(n)
    ⇒ 총 공간 복잡도: O(n)

Array

class Solution {
    public String solution(String str1, String str2) {
        char[] result = new char[str1.length() * 2];

        for (int i = 0; i < str1.length(); i++) {
            result[2 * i] = str1.charAt(i);
            result[2 * i + 1] = str2.charAt(i);
        }

        return new String(result); // 배열을 문자열로 변환
    }
}

시간 복잡도:

  • for 루프: 문자열 길이 n에 따라 n번 순회 → O(n)
  • 배열 인덱스 연산 및 할당: 각 i에 대해 2번 연산 → O(n)
    ⇒ 총 시간 복잡도: O(n)

공간 복잡도 :

  • 배열 생성: 길이 2n의 char[] 배열 생성 → O(n)
  • 최종 문자열(String): 길이 2n의 char[] 배열 생성 → O(n)
    ⇒ 총 공간 복잡도: O(n)

그럼 실행 시간도..?

시간복잡도와 공간복잡도가 유사하다면, 측정 시간도 유사할까?
궁금증에 a,b 각 데이터를 50_000 개 가량 반복 문자열을 만드는 코드로 살펴보자 

public class Main {
    public static void main(String[] args) {
        // 테스트 데이터
        String str1 = "a".repeat(50_000);
        String str2 = "b".repeat(50_000);

        // JVM 워밍업 및 초기 실행
        warmUp(str1, str2);

        // 최종 성능 테스트
        testPerformance("StringBuilder", () -> StringBuilderApproach.stringBuilderApproach(str1, str2));
        testPerformance("Array-Based", () -> ArrayBasedApproach.arrayBasedApproach(str1, str2));
        testPerformance("Stream", () -> StreamApproach.streamBasedApproach(str1, str2));
    }

    // JVM 워밍업 메서드
    private static void warmUp(String str1, String str2) {
        for (int i = 0; i < 10; i++) {
            StringBuilderApproach.stringBuilderApproach(str1, str2);
            ArrayBasedApproach.arrayBasedApproach(str1, str2);
            StreamApproach.streamBasedApproach(str1, str2);
        }
    }

    // 성능 측정 메서드
    private static void testPerformance(String name, Runnable method) {
        System.gc(); // GC 강제 호출, 이를 통해 이전 테스트에서 사용된 메모리를 강제로 해제한다.
        long totalElapsed = 0;

        for (int i = 0; i < 10; i++) { // 10회 반복
            long startTime = System.nanoTime();
            method.run();
            long endTime = System.nanoTime();

            totalElapsed += (endTime - startTime);
        }

        double avgTime = totalElapsed / 10_000_000.0; // 평균 시간 (ms)
        System.out.println(name + " Average Time: " + avgTime + " ms");
    }

    private static class StreamApproach {
        public static String streamBasedApproach(String str1, String str2) {
            return java.util.stream.IntStream.range(0, str1.length())
                    .mapToObj(i -> "" + str1.charAt(i) + str2.charAt(i))
                    .collect(java.util.stream.Collectors.joining());
        }
    }


    private static class ArrayBasedApproach {
        public static String arrayBasedApproach(String str1, String str2) {
            int n = str1.length() + str2.length();
            char[] result = new char[n];
            int idx = 0;
            for (int i = 0; i < str1.length(); i++) {
                result[idx++] = str1.charAt(i);
                result[idx++] = str2.charAt(i);
            }
            return new String(result);
        }
    }

    private static class StringBuilderApproach {
        public static String stringBuilderApproach(String str1, String str2) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < str1.length(); i++) {
                sb.append(str1.charAt(i));
                sb.append(str2.charAt(i));
            }
            return sb.toString();
        }
    }
}
  • 워밍업을 하는 이유는 반복 실행으로 JIT 컴파일러가 최적화를 마친 후 실행 시간의 차이점을 정확히 파악하기 위해서이다.
  • JIT 관련 참고 블로그 : https://hyeinisfree.tistory.com/26

결과는 과연 같았을까?

StringBuilder Average Time: 1.21184 ms
Array-Based Average Time: 0.58769 ms
Stream Average Time: 2.97328 ms
  • StringBuilder는 평균적으로 1.2ms 정도의 시간이 소요되었고
  • Array 방식은 약 0.59ms로 가장 빠른 성능을 보였다.
  • Stream 방식은 가장 느리며, 2.97ms 정도 시간이 소요되었다.

왜 이렇게 되었을까? 시간복잡도와 공간복잡도는 같았다. 그렇다면, 왜 이렇게 시간이 차이가 날까?

메모리 사용량

왜냐하면 각 방법에 따라 메모리 사용량이 달라지기 때문이다.

배열에서는 필요한 크기의 배열을 한 번만 생성한다.
그러나 StringBuilder, Stream은 중간에 객체 생성으로 인한 추가 메모리를 사용하게 된다.

방식메모리 사용량
StringBuilder1개의 StringBuilder 객체 + 내부 char[] 배열 (n x 2) + 최종 String 객체 (n x 2)
Stream여러 중간 객체(String 인스턴스) 생성 + 최종 String 객체 (n x 2)
Array1개의 char[] 배열 (n x 2) + 최종 String 객체 (n x 2)

예시

문자열 길이 10이라 가정할 경우

(1) StringBuilder 방식 메모리 사용량

StringBuilder sb = new StringBuilder();
for (int i = 0; i < str1.length(); i++) {
    sb.append(str1.charAt(i));
    sb.append(str2.charAt(i));
}

배열 객체 메모리 구조

배열 객체 헤더: 약 24바이트
char 데이터: 20 * 2바이트 = 40바이트
총 배열 객체 메모리: 64바이트

최종 String 객체 메모리

String 객체 자체: 약 24바이트
char[] 참조: 4-8바이트
총 String 객체 메모리: 32바이트

전체 메모리 사용량

배열 객체: 64바이트
String 객체: 32바이트
총합: 96바이트

(2) Stream 방식 메모리 사용량

IntStream.range(0, str1.length())
    .mapToObj(i -> "" + str1.charAt(i) + str2.charAt(i))
중간 객체 메모리

임시 문자열 객체: 10개 * 평균 40바이트 = 400바이트

각 객체는 문자열 데이터, 객체 헤더 등 포함

최종 문자열 객체

char[20]: 40바이트
String 객체 오버헤드: 약 24바이트

전체 메모리 사용량

중간 객체들: 약 400바이트
최종 문자열: 64바이트
총합: 464바이트
추가 GC 비용 발생

(3) Array 방식 메모리 사용량

char[] result = new char[str1.length() * 2]; // 길이 20
배열 객체

char[20]: 40바이트
배열 객체 헤더: 약 24바이트
총 배열 메모리: 64바이트

최종 문자열 객체

char[20]: 40바이트
String 객체 오버헤드: 약 24바이트
총 String 객체 메모리: 64바이트

전체 메모리 사용량

배열 객체: 64바이트
String 객체: 64바이트
총합: 약 128바이트

StringBuilder와 Array는 왜 차이가 날까?

StringBuilder의 초기 생성자의 코드를 보자.

StringBuilder는 길이가 16인 char 배열을 생성한다.
그러나 만약 16을 초과하게 될 경우, 자동으로 2배로 새로 생성된다.
즉, 확장할 때마다 메모리를 추가로 사용하게 된다.

반대로 위 Array 코드를 보면 처음부터 크기를 지정하고 작업한다.
StringBuilder와 달리 중간에 확장하거나 복사할 경우가 없기에 메모리 사용이 없다.

즉,차이가 나는 주된 이유는 중간 과정에서 메모리를 사용하지 않았다는 점이다.

결론

배열 방식이 가장 빨랐던 이유는 크기를 고정함으로, 처음부터 배열을 할당하고 추가 복사나 확장이 없었다.

n이 작으면 이렇게 까지 세밀하게 볼 필요는 없지만, 백 단위 이상부터는 생각하고 구현해야겠다.

방법중간 메모리 사용시간 차이의 원인
StringBuilder배열 확장 및 복사데이터 복사로 인해 추가 메모리와 시간이 소모
Stream여러 중간 객체(String 인스턴스) 생성반복으로 인한 객체 생성, GC(가비지 컬렉션) 비용
Array없음시작부터 끝까지 메모리 일정
profile
한
장기적 성장하기
이전 포스트

컬렉션 프레임워크(Collection Framework)의 핵심 인터페이스

다음 포스트

차분배열(Difference Array Technique)

0개의 댓글