[개발일지] 2일차 - 파이썬으로 이분 탐색

grefer·2021년 9월 29일
0

오늘한일

  • 제주 및 도서산간 지역 여부 가르기 구상

도서산간 지역은 어떻게 구분하지

보통 택배 시킬 때, 도서산간은 가격이 추가된다고 써있다. 근데 이걸 어떻게 구분하는지 궁금했다. api가 있나?

실제로 api가 제공된다거나 하지는 않는다. 도서산간의 기준에는 정해진 표준이 없기 때문이다. 그래서 한 택배회사에서 사용하는 도서산간 기준표를 가지고 구분하기로 했다. (어차피 택배로 보낼거니까)

도서산간 db는 우편번호, 주소, 제주 및 도서산간 여부의 컬럼을 가진다.
우리 address 모델은 우편번호 필드가 없는데 어쩐담...

피키팜의 주소 입력은 다음 우편번호 api를 사용하고 있다. (이름 부터 우편번호 api인데 이걸 모르고 있었다) 사용자가 주소를 입력해서 선택하면 우편번호를 포함한 각종 데이터를 넘기는데, 이 우편번호와 도서산간 db를 대조해 여부를 가린다.

결국 이걸 어떻게 코드로 나타내느냐의 문제

로직은 이론상 깔끔한데, 이걸 코드로 옮기자니 고민되는 사항이 있다.
도서산간 db는 csv의 형태로 저장되어 있고, zipcode를 인자로 넣으면 도서산간 여부를 출력하는 함수가 있다고 생각해보자. 두가지의 방법을 생각할 수 있다

  1. 매 함수 호출시마다 pandas를 이용해 csv를 읽기
  2. csv에서 zipcode만 추출해 코드상에 list로 저장

1번이 파일을 관리하기 좋을 것 같다는 생각이 들지만, 퍼포먼스 측면에서 2번이 유리하다는 생각도 들기 시작한다.

그래서 결국 2번을 선택했는데 이유는 아래와 같다.

  • 도서산간 db는 새로운 산이나 섬이 생기지 않는 이상 바뀔 일이 없다.
  • 암만봐도 함수 호출때마다 pandas로 읽는건 오버헤드가 크다

깔끔하게 만들기 위해서,,,

도서산간 db는 약 8000개의 row를 가진다. 그런데 zipcode가 중복되는 경우가 꽤 됐다. 그래서 중복을 제거하니 약 1300개의 row로 줄었다.

그래서 리스트로 저장하기에 충분한 크기라고 생각이 들었는데, 문제는 이걸 깔끔하게 표시하는 방법이었다.
1300줄의 리스트를 함수 로직과 같이 넣기엔 가독성이 박살날 것 같았다.

import문을 변수에 대해서만 쓸수 있을까?

가능했다.

#zipcode.py

ZIPCODE_LIST = [
	# some zipcodes that is mountain, island, jeju, and so on...
] 

zipcode 리스트만 가지는 파일을 하나 선언 한 다음에,

from zipcode import ZIPCODE_LIST


def check_address_by_zipcode(request, zipcode):
    if zipcode in ZIPCODE_LIST:
        # some logics that check argument zipcode is in the ZIPCODE_LIST 

이걸 함수 로직에서 불러오면 된다.

더 나아가 보자면,,

사실 1300개의 데이터를 검색하는 데에는 O(n)O(n)O(logn)O(logn)이 퍼포먼스 측면에서 큰 차이가 없다고 생각이 들었다.
그렇지만 수많은 요청의 가능성이 있는 피키팜 서비스의 특성상, 모든 부분에서 최적화가 필요하다.

그래서 ZIPCODE_LIST에서 zipcode를 찾기 위해 binary search를 사용하기로 했는데, 물론 직접 구현할수도 있겠지만 python은 없는게 없다. bisect라는 모듈이 있다.

bisect

파이썬의 이진탐색 모듈, bisect_left(), bisect_right(), bisect() 등이 있다.
bisect_left(arr, x) 는 정렬된 리스트 arr에서 x가 삽입될 때 들어갈 수 있는 인덱스를 왼쪽에서 부터 세서 리턴한다.

그리하여 위의 zipcode 확인 함수는 다음과 같이 바꿔줄 수 있겠다.

from zipcode import ZIPCODE_LIST
from bisect import bisect_left


def check_address_by_zipcode(request, zipcode):
    idx = bisect_left(ZIPCODE_LIST, zipcode)

    return True if ZIPCODE_LIST[idx] == zipcode else False

만약 zipcodeZIPCODE_LIST에 포함된다면, bisect_left()의 결과로 리턴되는 idx로 리스트에 접근한 값이 인자로 받은 zipcode와 같을 것이다. (도서산간 db의 우편번호는 0으로 시작하는 경우가 없기 때문에 integer로 처리해도 문제가 없다)

TIL

  • python에는 이진탐색을 지원하는 모듈이 있다, bisect
profile
개발자가 되고싶다 열심히하자

0개의 댓글