python에서 set은 집합형 자료구조라고 배웠다. 특징으로는 중복을 허용하지 않는다는 특징과 순서를 보장하지 않는다는 특징이 있다. 사용예시는 아래와 같다.
setStructure = set()
setStructure = {}
setStructure = set()
print(setStructure)
Out : set()
print(hex(id(setStructure)))
Out : 0x7f99716cd9e0
setStructure.add(3)
print(setStructure)
Out : {3}
print(hex(id(setStructure)))
Out : 0x7f99716cd9e0
간단히 원소 3(int)을 삽입하는 예시이고, set은 Mutable 자료형이므로 3을 삽입하더라도 주소값이 변경되지 않았다.
mutable? 파이썬의 메모리 관리기법 보러가기
print(setStructure)
Out : {1, 2, 3, 4} # 이미 1,2,3,4 네개의 원소가 있는 상태
setStructure.remove(4)
print(setStructure)
Out : {1, 2, 3} # 4 원소가 잘 삭제되었다.
setStructure.remove(4)
KeyError : 4
없는 원소를 삭제하려고 하면 error를 뱉는다.
print(setStructure)
Out : {1, 2, 3, 4} # 이미 1,2,3,4 네개의 원소가 있는 상태
setStructure.discard(4)
print(setStructure)
Out : {1, 2, 3} # 4 원소가 잘 삭제되었다.
setStructure.discard(4)
print(setStructure)
Out : {1, 2, 3}
원소가 없는 상태에서 discard를 하더라도 error를 뱉지 않는다. 명시적으로 확실히 있는 원소를 삭제할 때 remove, 있든 없든 무조건 삭제가 되었으면 하면 discard를 쓰면 되겠다.
popList = list()
popList.append(-3)
popList.append(-1)
popList.append(2)
print(popList)
Out : [-3, -1, 2]
print(popList.pop())
Out : 2
append한 순서대로 값이 삽입되고 pop을 하자 가장 마지막에 들어간(last in) 2가 먼저 pop(first out)됨을 알 수 있다. set에서는 어떨까
popSet = set()
popSet.add(-3)
popSet.add(-1)
popSet.add(2)
print(popSet)
Out : {2, -3, -1}
print(popSet.pop())
Out : 2
애초에 add한 순서대로 출력되지도 않는다.(순서가 보장되지 않음) 그리고 pop을 했을 때 가장 앞에 출력된 2가 출력됨을 알 수 있다. 이는 set이 python 내부적으로 hashtable data structure로 구성되어 있기 때문이다.
python의 set, dict 객체는 모두 hashtable data structure이다. 둘의 차이는 set는 value가 존재하지 않고 Key만 존재하는 데이터 구조이고, dict는 key, value가 매핑되어있는 데이터 구조이다. 그럼 그 구조차이는 어디에서 오는가? C python의 코드를 보며 알아보자.
< 참조 >
dictobject.c
setobject.c
위 링크를 참조하면 알 수 있는 점이 있다.
1 . dict는 hashtable 로 구현했다.
2 . set은 dict를 참조해서 구현했다.
3 . set struct와 dict struct의 차이
struct 는 이곳에 있다. dictobject.h setobject.h
언뜻 보면 비슷해 보이지만 큰 차이가 있다. dictentry에는 value를 가르키는 주소값이 추가로 저장되어 있고 setentry에는 value없이 key만 저장하고 있음을 알 수 있다. 실제로 c 코드를 보니 set에는 value가 없고 dict에는 key, value로 매핑되어 있는지 확실히 알 수 있다.
hash table을 구현해보면 알겠지만 hash table을 순회하면 첫번째 bucket부터 안의 키를 순회하고 다음 bucket으로 가는 식으로 순회한다.
이렇게 순회를 하니 pop을 한다고 가장 뒤에 있는 값까지 순회해서 내뱉는 것이 아닌 가장 처음에 나온 값을 뱉게되는 것이다.
간단히 말하면, while에서 존재하는 key가 나올 때까지 순회를 하고 나오면 해당 key를 return한다.
순서가 중요할 때(set, dict는 순서없음)
중복없이 특정값이 이미 있는지 여부만 알면되고 순서는 필요없을 때
key와 함께 value가 필요할 때(list, set은 key, value mapping 없음) 그리고 그 값을 효과적으로 찾고싶을 때
hash table 특성 상 member를 찾을 때 시간복잡도는 평균 O(1), 최악의 경우 O(n)(python set에서는 그럴일 거의 없음)이기 때문에 이분탐색 등 다른 탐색법 보다 훨씬 빠른 속도를 갖는다.
풀어보면 좋은 문제 백준 소수경로 1964번
위 문제를 이분탐색으로 풀어보고 set을 사용해서 두번 풀어보자.
inSet = set([1,2,3]) # 이렇게도 선언 가능하다.
print(1 in inSet)
Out : True
전공책도 읽어보고 구글링도 오래 해봤는데 명쾌한 답이 나오지 않는다. 아마 차이가 없어서 그런 것일 수도... 또 각 언어마다 사용하는 단어가 조금씩 다른 것 같다. 특히 java는 아예 저런 객체가 존재한다.(hashmap vs hashtable in java) 혹시 잘 아시는 분은 피드백 부탁드립니다.
조만간 시간내서 C로 구현해보고 블로그 작성해보겠습니다. 특히 bucket을 single linked list 혹은 double linked list로 구현했을 때의 삭제에서의 시간차이에 대해서 매우 궁금하기 때문에 직접 해보고 작성하도록 하겠습니다.
언어를 많이 안다는 것이 무조건 좋은 건 아닌 것 같다는 생각이 들었다. 잘 안다고 생각하는 언어를 실제로 잘 아는 것일까? 겸손한 마음으로 깊은 공부를 해야겠다는 다짐을 했다. 😀
"2 . C로 해쉬테이블을 구현해보자" 이걸 해요?? 보기만해도 토나오는군요 벌써 C 다 까먹은거 같아요. 현기증 나니까 들어갈게요