28279: 덱2

문제 링크:https://www.acmicpc.net/problem/28279

유튜브 링크: https://youtu.be/cMwwVljEZfg

 

---

나의 정답(340ms)

import sys
n =iter(sys.stdin.buffer.read().split())
next(n)
def solve(n):
    from collections import deque

    queue = deque()
    output=[]


    for token in n:
        if token == b'1':
            queue.appendleft(next(n))

        elif token == b'2':
            queue.append(next(n))

        elif token == b'3':
            output.append(queue.popleft() if queue else b'-1')

        elif token == b'4':
            output.append(queue.pop() if queue else b'-1')

        elif token == b'5':   
            output.append(b'%d' %len(queue))

        elif token == b'6':
            output.append( b'0' if queue else b'1')

        elif token == b'7':
            output.append(queue[0] if queue else b'-1')

        elif token == b'8':
            output.append(queue[-1] if queue else b'-1')

    sys.stdout.buffer.write(b'\n'.join(output))

solve(n)

---

Q&A

질문
output.append(b'%d' %len(queue)) 이게 빨라

output.append(len(queue).encode()) 이게 빨라?

 

답변
비교를 시작하기 전에, 두 번째 코드에 아주 작은 함정이 하나 숨어 있어요.
len(queue)의 결과는 정수(int)인데, 파이썬에서 정수형 객체는 .encode() 메서드를 가지고 있지 않습니다.

 

그래서 이 코드가 실제로 에러 없이 돌아가려면 정수를 먼저 문자열로 바꿔주는 과정을 거쳐야 해요.

즉, str(len(queue)).encode() 형태가 되어야 합니다.

 

자, 그럼 실제로 작동하는 두 코드가 파이썬 내부에서 어떤 과정을 거치는지 비교해 봅시다.

b'%d' % len(queue): 정수 값을 받아 곧바로 바이트(byte) 형태의 문자열로 포맷팅해서 만들어 냅니다.

str(len(queue)).encode(): 먼저 정수를 일반 텍스트 문자열(str) 객체로 변환하고, 그 만들어진 문자열 객체를 다시 바이트 객체로 인코딩(변환)합니다.

 

,즉 output.append(b'%d' %len(queue))가 더 빠릅니다

---

 

질문
왜 일반 문자열을 쓰는게 byte를 써서 처리하는 것 보다 빠르지?

 

답변
바이트(byte) 단위로 날것의 데이터를 처리하는 코드가 더 빠를 것이라는 예상은 컴퓨터 구조상 아주 합리적이고 훌륭한 추론입니다. 하지만 파이썬이라는 언어의 '내부 사정' 때문에 완전히 예상 밖의 결과가 나왔네요.

 

이 현상을 이해하려면 우리가 작성한 코드를 실행해 주는 프로그램(인터프리터)의 특징을 알아야 합니다.

파이썬은 기본적으로 사람들이 가장 많이 사용하는 일반 텍스트 문자열(str) 처리에 엄청난 최적화를 공들여왔습니다.

 

예를 들어 "1", "2" 같은 짧고 자주 쓰이는 문자열은 파이썬이 실행될 때 메모리에 미리 만들어두고(캐싱) 필요할 때마다 빛의 속도로 재사용합니다.

 

반면, 바이트(bytes) 객체는 파일 입출력이나 네트워크 통신 등 특수한 상황에서 주로 쓰이다 보니, 텍스트 문자열만큼 극단적인 최적화가 되어 있지 않은 경우가 많습니다.

 

특히 우리가 사용한 b'%d' % len(queue) 같은 바이트 포맷팅 연산은 일반적인 str() 변환보다 내부적으로 처리 과정이 더 무거울 수 있습니다.

 

또 하나의 원인이 될 수 있는 건 숫자를 문자로 바꿔주는 파이썬 최하단(C언어) 내장 함수인 str()을 직접 호출하는 방식이고, 다른 하나는 b'%d'라는 형태(포맷)를 먼저 읽고 분석한 뒤 그 자리에 숫자를 연산하여 끼워 넣는 % 연산 방식입니다.

 

 

 

---