<jupyter_start><jupyter_text>파이썬 프로그래밍 실습 4  문제 1 아래 기준을 만족하는 `has_duplicates` 함수를 구현하라.* 인자: 하나의 리스트* 반환값: 리스트에 특정 항목이 두 번 사용되면 `True`,    그렇지 않으면 `False`.예제:```python    >>> has_duplicates([1, 2, 1, 3])True>>> has_duplicates(['hello', 'hi', 'hey'])False```힌트: 집합(`set`) 자료형 활용<jupyter_code># pass와 None을 각각 적절한 명령문과 값으로 대체하라.

def has_duplicates(xs):
    pass
    return None<jupyter_output><empty_output><jupyter_text>견본답안<jupyter_code>def has_duplicates(xs):
    n = len(xs)
    m = len(set(xs))
    duplicated = (n > m)
    
    return duplicated
has_duplicates([1, 2, 1, 3])
has_duplicates(['hello', 'hi', 'hey'])<jupyter_output><empty_output><jupyter_text>긴 리스트 다루기 [words.txt](https://raw.githubusercontent.com/AllenDowney/ThinkPython2/master/code/words.txt) 파일은 113,783 개의 단어를 한 줄에 하나씩 갖고 있다. 먼저 아래 코드를 이용하여 언급된 `words.txt` 파일을 인터넷으로부터 다운로드해서 저장한다.<jupyter_code>import urllib.request

file_url = "https://raw.githubusercontent.com/AllenDowney/ThinkPython2/master/code/words.txt"
file_name = "words.txt"
urllib.request.urlretrieve(file_url, file_name)<jupyter_output><empty_output><jupyter_text>`make_word_list()` 함수는 다운로드한 파일을 연 다음 각각의 줄에 포함된 내용으로 구성된 리스트를 생성한다.<jupyter_code>def make_word_list(file_name):
    file_open = open(file_name)   # 파일을 메모리에 불러오기
    
    t = []                          # 각각의 줄로 구성된 리스트 생성
    for line in file_open:
        word = line.strip()         # 화이트스페이스(공백, 줄바꿈 등) 제거
        t.append(word)
        
    return t<jupyter_output><empty_output><jupyter_text>위 함수를 이용하여 `words.txt` 파일에 포함된 단어로 구성된 리스트를 생성하자.<jupyter_code>words_list = make_word_list('words.txt')<jupyter_output><empty_output><jupyter_text>리스트의 길이가 112,783이다.<jupyter_code>print(len(words_list))<jupyter_output>113783<jupyter_text>처음 10개 단어는 다음과 같다.<jupyter_code>words_list[:10]<jupyter_output><empty_output><jupyter_text>마지막 10개 단어는 다음과 같다.<jupyter_code>words_list[-10:]<jupyter_output><empty_output><jupyter_text>문제 2 주어진 리스트에 특정 항목이 포함되어 있는지 여부를 확인하는 함수`list_elem()`를리스트 자료형의 `in` 연산자 활용하여 구현하라.* 인자: 하나의 문자열과 하나의 리스트* 반환값: 지정된 리스트에 지정된 문자열이 포함되어 있으면`True`,     그렇지 않으면 `False`. 예제:```python    >>> list_elem(3, [1, 2, 1, 3])True>>> list_elem('python', ['hello', 'hi', 'hey'])False```<jupyter_code># pass와 None을 각각 적절한 명령문과 값으로 대체하라.

def list_elem(x, xs):
    pass
    return None<jupyter_output><empty_output><jupyter_text>견본답안<jupyter_code>def list_elem(x, xs):
    contained = x in xs
    
    return contained
list_elem(3, [1, 2, 1, 3])
list_elem('python', ['hello', 'hi', 'hey'])<jupyter_output><empty_output><jupyter_text>문제 3 문제 2를 이진탐색 알고리즘을 이용하여 구현한 후에두 함수의 실행속도의 차이를 비교하라.    시간 비교를 위해 많은 양의 단어를 포함한 `words_list` 리스트를 이용하라.__참고:__ 이진탐색 개념에 대한 설명은 [GeeksforGeeks: Binary Search](https://www.geeksforgeeks.org/binary-search/)를참조할 수 있다.<jupyter_code># pass와 None을 각각 적절한 명령문과 값으로 대체하라.

def binsearch(x, xs):
    pass
    return None<jupyter_output><empty_output><jupyter_text>견본답안 아래에서 정의되는 `binsearch()` 함수는 단순히 `True` 또는 `False`를반환하는 함수가 아니다.리스트에서 항목을 찾을 수 있으면 해당 인덱스와 찾을 때까지 걸리는 시간을while 반복문의 실행횟수로 함께 반환한다.또한 반환된 인덱스의 값이 -1인 경우 리스트에 존재하지 않음을 의미한다.<jupyter_code>def binsearch(x, xs):
    low, high = 0, len(xs)-1
    location = -1

    # while 반복문 실행횟수 확인용    
    loop_count = 0

    while low <= high and location == -1:
        loop_count += 1
        mid = (low + high)//2

        if x == xs[mid]:
            location = mid
        elif x < xs[mid]:
            high = mid - 1
        else:
            low = mid + 1
    
    return (location, loop_count)<jupyter_output><empty_output><jupyter_text>이진탐색 알고리즘을 사용한 함수가 10배 이상 빠르다.__경고:__ 빠른 컴퓨터를 사용하는 경우 이진탐색 알고리즘 실행시간이 0초로 계산될 수 있다.<jupyter_code>import time

# 리슽 in 연산자
start_time = time.time()
t = list_elem('python', words_list)
elapsed_time_1 = time.time() - start_time

print("list_elem():\t", elapsed_time_1, '초')

# 이진탐색 알고리즘
start_time = time.time()
t = binsearch('python', words_list)
elapsed_time_2 = time.time() - start_time

print("binsearch():\t", elapsed_time_2, '초')<jupyter_output>list_elem():	 0.0009984970092773438 초
binsearch():	 0.0 초<jupyter_text>문제 4 words.txt 파일의 내용을 사전 자료형으로 저장한 후에,생성된 사전에 특정 단어가 키로 사용되었는지 여부를 확인하는 함수를사전 자료형의 `in` 연산자 활용하여 구현하라.또한 앞서 리스트를 활용한 구현 방식과 비교하여 사전 자료형을 이용한 `in` 연산자의 실행속도가 얼마나 빠른지 확인하라.힌트: `words.txt` 파일에서 단어를 읽어 들인 후 각각의 단어를 키로 사용한다. 모든 키의 값은 `True`로 정한다.  견본답안 먼저 `words_list`를 이용하여 사전을 생성한다.이때 키(key)는 각 단어이고 값은 무조건 `True`를 사용한다.<jupyter_code>words_dict = dict()

for word in words_list:
    words_dict[word] = 'True'<jupyter_output><empty_output><jupyter_text>총 113,783개의 단어가 키로 사용되었음을 확인할 수 있다.<jupyter_code>len(list(words_dict.keys()))<jupyter_output><empty_output><jupyter_text>사전의 `in` 연산자를 이용한 함수는 다음과 같다.<jupyter_code>def dict_elem(x, xs):
    contained = x in xs
    # contained = x in xs.keys()   # keys() 메서드는 굳이 사용할 필요 없음
    
    return contained<jupyter_output><empty_output><jupyter_text>사전의 `in` 연산자가 이진탐색 알고리즘보다 좀 더 빠르다.<jupyter_code>import time

# 리스트 in 연산자
start_time = time.time()
t = list_elem('python', words_list)
elapsed_time_1 = time.time() - start_time

print("list_elem():\t", elapsed_time_1, '초')

# 이진탐색 알고리즘
start_time = time.time()
t = binsearch('python', words_list)
elapsed_time_2 = time.time() - start_time
print("binsearch():\t", elapsed_time_2, '초')

# 사전 in 연산자
start_time = time.time()
t = dict_elem('python', words_dict)
elapsed_time_3 = time.time() - start_time
print("dict_elem():\t", elapsed_time_3, '초')<jupyter_output>list_elem():	 0.0010001659393310547 초
binsearch():	 0.0 초
dict_elem():	 0.0 초
{'fraction_non_alphanumeric': 0.13038714390065742, 'fraction_numerical': 0.023192111029948868, 'mean_word_length': 4.3226433430515065, 'pattern_counts': {'":': 0, '<': 68, '<?xml version=': 0, '>': 79, 'https://': 3, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '558511', 'license': 'Apache-2.0', 'n_tokens_mistral': 3148, 'n_tokens_neox': 3707, 'n_words': 550, 'path': 'practices/practice04.ipynb', 'repo_name': 'codingalzi/mle', 'size': '5476'}