[edu] 컬렉션에서 아이템 찾기 (검색 성능)

두 함수는 똑같아 보입니다. 하지만 검색 성능은 확연히 다릅니다. lookup_set 함수가 파이썬에서 셋(set)은 해시테이블이라는 사실을 이용하기 때문입니다. 리스트 안에 어떤 아이템이 존재하는지 확인하려면 파이썬은 그 아이템과 매칭되는 것을 찾을 때까지 각각의 아이템을 모두 검사해야만 합니다. 이 작업에는 시간이 걸립니다. 리스트가 긴 경우에는 더욱 그렇습니다. 반면에 셋(set)에서는 각 아이템의 해시가 셋 안에의 어느 곳에 매칭되는 아이템이 위치하는지 알려줍니다. 결과적으로 셋(set)이 크더라도 검색이 빠르게 완료됩니다. 딕셔너리(dictionary)에서의 검색도 마찬가지로 수행됩니다. 더 많은 정보를 윈하시면 StackOverflow 를 참조하세요. 데이터 구조에 따라 각 연산자들이 어느 정도의 시간을 소모하는지에 대한 자세한 정보는 이 페이지 를 참고하세요.

이러한 성능의 차이 때문에 다음과 같은 경우에는 리스트 대신 셋(set)이나 딕셔너리(dictionary)를 사용하는 편이 좋습니다:

• 컬렉션이 아이템을 많이 가질 경우

• 컬렉션 안의 아이템을 반복적으로 검색할 경우

• 중복 아이템이 없는 경우

크기가 작거나 검색을 자주 하지 않는 컬렉션의 경우에는 오히려 해시테이블을 만드는데 필요한 추가적인 시간과 메모리가 검색할 때 절약되는 시간에 비해 더 큰 경우도 많습니다.

def lookup_set(s):
    return 'a' in s


def lookup_list(l):
    return 'a' in l


alpha = ['a', 'b', 'c', 'd']
s = set(alpha)
l = alpha