연습문제 10-9

words.txt 파일*을 읽어서 단어 하나에 원소 하나로 된 리스트를 생성하는 함수를 작성하라. 이 함수는 두 가지 버전을 작성해야 한다. 한 가지 버전은 append 메서드를 사용하고, 다른 버전은 t = t + [x]를 사용한다. 어떤 버전이 실행하는 데 더 오래 걸리는가? 왜 그럴까?

해법: http://thinkpython2.com/code/wordlist.py

연습문제 10-10

단어 목록에 단어가 있는지 확인하는 데 in 연산자를 사용할 수 있지만, in 연산자는 단어를 순서대로 검색하므로 느려진다.

단어는 알파벳 순서이므로 이분 검색(bisection search)은 이진 검색(binary search)이라고도 하는데, 이를 이용하면 검색 속도를 개선할 수 있다. 이분 검색은 우리가 사전에서 단어를 찾는 방식과 비슷하다. 중앙에서 시작해서 찾으려는 단어가 리스트의 가운데보다 앞에 있는지 확인한다. 중앙보다 앞에 있다면 리스트의 전반부에서 같은 방법으로 검색한다. 그렇지 않다면 리스트의 후반부에서 같은 방법으로 검색한다.

전반부나 후반부, 어느 쪽을 선택해도 검색 공간은 절반만 남게 된다. 단어 목록에 113,809단어가 있다면 17단계면 단어를 찾거나 찾는 단어가 없다는 결론에 도달할 수 있다.

정렬된 리스트와 찾으려는 값을 받아서 리스트에 값이 있으면 해당 값의 인덱스를 반환하고, 그렇지 않으면 None을 반환하는 in_bisect 함수를 작성하라.

아니면 공식 문서에서 bisect 모듈을 읽고 이를 이용해라!

해법: http://thinkpython2.com/code/inlist.py