Base11172

The Library of Babel의 한글 버전을 제작하면서 퍼포먼스 문제가 생겼다.

존재 가능한 모든 책의 개수는 11172^(656000)개이고, 0 ~ (11172^656000)-1의 각각의 숫자는 단 하나의 책과 일대일 대응 관계를 가진다. 이 숫자를 연산하여 책의 문자들을 얻어낸다. 일단 의식의 흐름대로 아래 코드를 작성해 테스트해봤다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# withoutBase11172.py
import random

BASE = 11172    # number of Korean Unicode
MAX_CHAR = 40   # number of chars per line
MAX_LINE = 40   # number of lines per page
MAX_PAGE = 410  # number of pages per book

NUMBER_OF_BOOK = BASE**(MAX_CHAR*MAX_LINE*MAX_PAGE) # number of possible books
NUMBER_OF_PAGE = BASE**(MAX_CHAR*MAX_LINE)          # number of possible pages

book = random.randrange(NUMBER_OF_BOOK)  # which book do you want to read?
page_num = 200                              # which page do you want to read?

divisor = NUMBER_OF_PAGE**page_num
book //= divisor        # cut off front pages
book %= (divisor**2)  # cut off behind pages
result = ''
for _ in range(MAX_CHAR*MAX_LINE):
    book, char = divmod(book, BASE)
    result += chr(char+44032)
print(result)

보여줄 페이지 부분만큼 자르는 15, 16번째 줄에서 50초 가량 잡아먹는다. 페이지를 자르지 않으면 아래 for 문에서 그 이상의 시간이 발생한다. 수가 워낙 크기에 나눗셈 연산이 버거운 듯 보였다. 최적화의 여지가 없어보였다.

퍼포먼스 개선을 위해서 11172진법 시스템을 먼저 개발하기로 했다. 배열을 이용해 각 자리의 수들을 따로 따로 담는다면 문자들을 얻기 위해 나누기 연산이나 나머지 연산을 할 필요없이, 슬라이싱으로 자르고 인덱싱으로 문자를 얻어내면 그만이기에 10진법 환경보다는 속도가 빠르리라 예상했다.

기능은 2진법, 8진법, 1739진법 11172진법등등 어떤 n진법이나 구현할 수 있으면서, n진법에서 원하는 자리수를 수학적 연산없이 뽑아낼 수 있다는 것.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# withBase11172.py
from base11172 import Base11172
import random

BASE = 11172    # number of Korean Unicode
MAX_CHAR = 40   # number of chars per line
MAX_LINE = 40   # number of lines per page
MAX_PAGE = 410  # number of pages per book

LENGTH_OF_BOOK = MAX_CHAR*MAX_LINE*MAX_PAGE # length of book
LENGTH_OF_PAGE = MAX_CHAR*MAX_LINE          # length of page

# which book do you want to read?
book = Base11172([random.randrange(BASE) for _ in range(LENGTH_OF_BOOK)], 1)
page_num = 200  # which page do you want to read?

page = book[page_num*LENGTH_OF_PAGE:(page_num+1)*LENGTH_OF_PAGE] # slice page
result = ''
for char in page:
    result += chr(char+44032)
print(result)

성능 차이는 대충 요정도

1
2
withoutBase11172.py: 3209 function calls in 56.617 seconds
withBase11172.py: 2930449 function calls (2930448 primitive calls) in 1.784 seconds

남 보여주기에 매우 부끄러운 코드를 조금은 덜 부끄럽게 손보고 Github에 업로드했다. 문서화는 둘째치고 아직 기능도 다 구현안한 상태지만 알고리즘 같은거 공부한다든지 계속 가지고 놀기에는 꽤 괜찮은 프로젝트 주제처럼 보인다. LOBK 말고도 범용적으로 쓰일 수 있을지는 아직 모르겠다.

Base11172