#String_slicing #문자열 슬라이싱하기

 

   코드를 짤 때, 이젠 코드의 시간 복잡도를 꼭 염두하며 짜는 습관이 생겼다. 오늘 풀었던 문제는 문자열이 주어졌을 때, index로 접근하고자 할 때, 문자열 자체가 1,000,000까지 늘어날 수 있다면 이를 어떻게 효과적으로 접근할지에 대해서 다루고자 한다. 

바이너리 시퀀스형(bytes, bytearray, memoryview)를 사용하면, silcing을 할 때 copying 하는 방식으로 접근하지 않아 보다 효율적이라고 한다. (*문제에서는 엄밀히 말하면, slicing이 아니라 index를 통한 접근이기 때문에 사실 memoryview를 활용했을 때, 그렇지 않았을 때보다 훨씬 성능이 좋지 않았다. Slicing문제에서는 memoryview를 통해서만 풀어야 한다.) 슬라이싱 문제의 경우 시간복잡도가 memoryview의 경우, 데이터의 크기가 증가할 때마다 선형으로 증가한다. 하지만 일반 string[1:]의 접근법으로는 n제곱(n은 데이터 크기)으로 증가한다. 

#메모, python 3.x 의 경우 memoryview를 사용할 때 유의해야 할 점

memoryview에 들어오는 자료형태는 바이너리 시퀀스형이다. data(문자열)을 bytes로 수정해주어야 한다! 

memoryview(bytes(data, 'utf-8')) 

 

#인덱스로 한 개씩 접근하는 경우

import time
for n in (100000, 200000, 300000, 400000):
    data = 'x'*n
    start = time.time()
    b = data
    length = len(b)
    for i in range(length):
        b[i]
    
    print ('bytes', n, time.time()-start)
    
bytes 100000 0.0173490047454834
bytes 200000 0.028964757919311523
bytes 300000 0.03465008735656738
bytes 400000 0.0429689884185791

for n in (100000, 200000, 300000, 400000):
    data = 'x'*n
    start = time.time()
    b = memoryview(bytes(data, 'utf-8'))
    length = len(b)
    
    for i in range(length):
        b[i]
    print ('memoryview', n, time.time()-start)
memoryview 100000 0.010936975479125977
memoryview 200000 0.030824899673461914
memoryview 300000 0.0329432487487793
memoryview 400000 0.03961610794067383

#슬라이싱으로 접근하는 경우

import time
for n in (100000, 200000, 300000, 400000):
    data = 'x'*n
    start = time.time()
    b = data
    m = b[1:]
    print ('memoryview', n, time.time()-start)


for n in (100000, 200000, 300000, 400000):
    data = 'x'*n
    start = time.time()
    b = memoryview(bytes(data, 'utf-8'))
    
    m = b[1:]
    print ('memoryview', n, time.time()-start)
    
memoryview 100000 2.7179718017578125e-05
memoryview 200000 2.9802322387695312e-05
memoryview 300000 4.982948303222656e-05
memoryview 400000 9.822845458984375e-05

memoryview 100000 5.3882598876953125e-05
memoryview 200000 2.384185791015625e-05
memoryview 300000 3.409385681152344e-05
memoryview 400000 4.506111145019531e-05

 

#The minion game 

Hint : 자음(consonant), 모음(vowel) 구별해야 한다. 모음의 개수가 더 적으므로 이를 리스트해서 만들었다.