[Python] 검색기능에서 Set 의 활용성

특정 List 에서 어떤 member 가 있는지를 찾아보는 계산에서는 set 이 더 유용하다.

예를 들어

a = []
for i in range(10000):
    a.append(i)

이렇게 list 를 만들었다고 했을때, 특정 member 가 list 에 있는지 찾아보는 방법에는

if 22 in a : print "True"

와 같은 방식으로 찾을 수 있을 것이다. 그러나 이러한 "x in list" 계산은 O(n) 의 complexity 를 갖는다. 이럴 경우 set() 을 사용하면 O(1) 의 time complexity 로 검색이 가능하다.

aSet = set(a)
if 22 in aSet : print "True"

이렇게 해주면 좀더 효율적으로 검색할 수 있다. (그런데 실제적으로 이 예제에서는 계산시간을 눈에 띄게 확인하기는 어렵다..)