[Python] 문자열 덧셈 vs Join 함수

# [+] 방식
PyObject *result = PyUnicode_New(new_len, maxchar);  // 👈 새로운 문자열 객체 생성

# join 방식
result = PyUnicode_New(total_length + sep_len * (count - 1), maxchar);  // 👈 한 번에 메모리 할당

백준 2448번을 풀다가 일반적인 문자열 덧셈에서는 시간초과가 뜨는 것을 보고 둘을 비교하게 되었습니다.

 

우선 아래는 파이썬의 일반적인 문자열 누적의 예시입니다.

parts=['a', 'b', 'c', '1', '2', '3']

# 문자열 덧셈
s = ""
for part in parts:
    s += part
print(s)

# join은 "구분자"를 기준으로 parts에 있는 문자열들을 하나의 문자열로 concat해줍니다.
s = "".join(parts)
print(s)

s = "|".join(parts)
print(s)

-----result-----
abc123
abc123
a|b|c|1|2|3

 

둘의 시간을 비교하기 위해 10만개의 'abc' 문자열을 concat해본 결과 상당한 시간 차이가 납니다.

10만 개의 문자열 연산 비교 결과
[+] 문자열 덧셈 시간: 0.315794초
[join] 기본 join 시간: 0.000483초

 

 

그 이유는 둘의 구현체(CPython)에 있습니다.

두 연산 다 아래의 코드 처럼 새로운 객체를 생성하지만 + 연산은 매번 새로운 객체를 생성하여 느려지고,  join은 입력의 길이를 계산하여 한 번만 생성합니다.

result = PyUnicode_New(sz, maxchar)

 

 

Join의 CPython을 보면 아래처럼 _PyUnicode_JoinArray에 길이 정보를 주고, 마지막에 한 번만 객체를 생성하고 return합니다.

_PyUnicode_JoinArray(PyObject *separator, PyObject *const *items, Py_ssize_t seqlen)
--생략--
sz = 0;
for (i = 0; i < seqlen; i++) {
        size_t add_sz;
        item = items[i];
       	--생략--
        if (i != 0) {
            add_sz += seplen;
        }
        if (add_sz > (size_t)(PY_SSIZE_T_MAX - sz)) {
            PyErr_SetString(PyExc_OverflowError,
                            "join() result is too long for a Python string");
            goto onError;
        }
        sz += add_sz;
        if (use_memcpy && last_obj != NULL) {
            if (PyUnicode_KIND(last_obj) != PyUnicode_KIND(item))
                use_memcpy = 0;
        }
        last_obj = item;
    }

res = PyUnicode_New(sz, maxchar);#한 번만 생성

 

반복적으로 문자열을 합칠 때는 join을 이용해야겠습니다. ㅎㅎ

 

아래는 2448번 코드입니다. 재귀방식은 정말 러프하고 최적화를 더 해야하지만 활용 예시로 넣어두겠습니다.

from collections import deque
N = int(input())
q=[]
q.append([' ', ' ', '*', ' ', ' '])
q.append([' ', '*', ' ', '*', ' '])
q.append(['*', '*', '*', '*', '*'])
space = [' ', ' ', ' ']#이전 것들에 추가할 공백 

def Add_Star(a):
    global N
   
    if a==N//3:
        return
    l = len(q)
    for i in range(l):
        q.append(q[i] + [' '] + q[i])

    for i in range(l):
        q[i] = space*a + q[i] + space*a
    
    Add_Star(a*2)

Add_Star(1)

#문자열 덧셈은 계속 새로운 객체를 생성하여 느리지만 join은 미리 최종 문자열을 계산하고 진행하여 빠름 
print("".join(["".join(q[i])+"\n" for i in range(len(q))]))

 

 

감사합니다.