PDF에 있는 text를 빠르게 가지고 오자 ! feat. 시간복잡도

 

회사 프로젝트 중 .. 크롤링을 하고 있었다

뉴스 기사들을 가지고 오는 크롤링이었는데,

기사 내에 pdf가 있으면 파일을 다운받아서 간단하게 text만 추출해서 DB에 넣어준다.

 

근데 pdf가 있는 기사와 없는 기사를 스크리핑하는데 시간 차이가 많이 난다고 느꼈다.

그래서 함수를 찾아갔다.

 

기존에 있던 코드:

def current_extract_pdf_text(pdf_url):
    start_time = perf_counter()
    
    response = requests.get(pdf_url, headers={'User-Agent': random.choice(user_agents)})
    response.encoding = response.apparent_encoding
    response.raise_for_status()
    
    pdf_text = ""
    with fitz.open(stream=response.content, filetype="pdf") as doc:
        for i, page in enumerate(doc):
            pdf_text += page.get_text() + "\n"
    
    duration_ms = int((perf_counter() - start_time) * 1000)
    print(f"current_extract_pdf_text duration_ms: {duration_ms}")
    
    return pdf_text.strip()

 

딱 100장짜리 pdf_url로 테스트를 했다.

duration을 측정했다.

current_extract_pdf_text duration_ms: 40476

 

충격적이었다.

아니 pdf에 있는 text만 가지고 오는데 40초가 걸린다고?

 

얼마전 교보문고에 갔다가 무슨 바람이 불었는디 python 자료구조 책이 너무 재밌어보여서 사버렸다.

중간까지만 읽다가 어디있는지 모르겠지만

얼마전에 읽은 책에서 봤다.

지금 문제가 되는건 += 때문이라는 걸 바로 알았다.

 

✔️ 왜 += 때문에 오래 걸리는가?

1. 루프가 돌 때마다 page.get_text() 로 새로운 문자열이 생긴다.

2. pdf_text에 이 새로운 문자열을 더하려면, 파이썬은 기존 pdf_text의 내용과 새로운 문자열을 합친 완전히 새로운 문자열을 위한 메모리 공간을 할당해야한다.

3. 그리고 이전 pdf_text의 모든 내용을 새로 할당된 공간에 복사한 뒤, 그 뒤에 새로운 문자열을 덧붙인다.

4. pdf_text 변수는 이제 이 '새로운' 문자열을 가리키게 된다.

 

→ 이 과정은 페이지가 누적될수록 pdf_text의 길이가 길어지기 때문에, 루프 후반부로 갈수록 복사해야 할 데이터의 양이 기하급수적으로 늘어난다.

→ O(n²)의 시간 복잡도를 가지며 매우 비효율적!

 

이렇게 개선했어요

→ list.append() 사용 !!!

def new_extract_pdf_text(pdf_url: str) -> str:
    start_time = perf_counter()
    try:
        response = requests.get(pdf_url, headers={'User-Agent': random.choice(user_agents)})
        response.raise_for_status()
        
        pdf_bytes = response.content
        pdf_document = fitz.open(stream=pdf_bytes, filetype="pdf")
        
        full_text = []
        for page_num, page in enumerate(pdf_document):
            full_text.append(page.get_text())
        pdf_document.close()
        
        duration_ms = int((perf_counter() - start_time) * 1000)
        print(f"new_extract_pdf_text duration_ms: {duration_ms}")
        
        return full_text

    except requests.exceptions.RequestException as e:
        return f"URL 요청 중 에러 발생: {e}"
    except Exception as e:
        return f"PDF 처리 중 에러 발생: {e}"

new_extract_pdf_text duration_ms: 1756

 

같은 pdf_url로 요청을 했는데, 1.75초가 나왔따

 

40476ms에서 1756ms로 개선했으니,, 95.7% 개선한 것,, 넘 뿌듯하다

 

✔️ list.append()는 왜 빠른가!

1. 파이썬의 list는 가변객체다. 기존 리스트에 요소를 추가하는 append() 연산은 매우 빠르다. O(1)

2. 루프가 끝난 후, "\n".join(full_text)는 최종적으로 만들어질 문자열의 전체 길이를 미리 계산한다.

3. 그 크기에 맞는 메모리 공간을 단 한 번만 할당하고, 리스트의 모든 문자열을 그 공간에 순서대로 복사하여 최종 문자열을 만든다.

 

 

시간 측정도 하고, 추출된 text 확인차 txt파일로 뽑아봤다

(왼) 기존 코드 출력물, (오) 개선한 코드 출력물

 

추출되는 text을 파일로 변환해서 확인해보니 ..

기존 코드로 추출도 잘 못 되고 있었다? 아니.. 왜.. 흐음..

 

항상 하나하나 잘 확인하고 뇌에 힘주고 코드 봐야지! 내가 다 수정할꺼야 ~~