달력

112017  이전 다음

  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  •  
  •  

Set은 intset과 hashtable을 사용합니다.


hashtable은 hashes에서 설명한것처럼 dict을 사용합니다.

intset에 대해 알아보겠습니다.


contents에 value값이 들어가고 encoding에는 현재 어떤 int형인지 (INTSET_ENC_INT16/32/64)

length에는 현재 저장한 value의 갯수가 저장됩니다.


insert할때는 binary search로 해당값이 있는지 확인하고 없으면 min 위치에 값을 저장합니다.


처음에 encoding은 int16_t로 하는데 그 범위에 벗어나는 값이 들어오면 전체 데이타를 다 수정합니다.;;;
intsetUpgradeAndAdd
아~~ 같은값이 있으면 뭐 상관없는데, 아니라면 아래 작업을 수행합니다.
resize후에 memmove로 저장할 위치 비워두는것 (포인터 안쓰면 이방법밖에 없는거겠죠? 덜덜)

t_set.c에서 intset과 hashtable중 어떤걸 쓸지 결정하는데, list나 hashed처럼 entry갯수제한이 있습니다.
(set_max_intset_entries)
또한 입력되는값들이 숫자면 intset, 문자열이 입력되면 그때부터 hashtable을 사용합니다.
직접 실행한 화면입니다.



마지막으로 intset은 object로 관리되지않기 때문에 decrRefCount, hashtable은 incrRefCount 입니다.


set 데이타 명령어중에 Intersect ,union 기능이 있습니다. 그중에 Intersect 부분이 어떻게 작성됐는지 궁금했습니다.
소스보니까;;; 간단하네요. 결론부터 말하자면 intset으로 Intersect 하는게 가장~!! 좋네요; ㅎㅎ

먼저 Intersect 할 데이타들을 qsort로  갯수기준으로 오름차순 정렬합니다.
그럼 가장 첫번째애가 가장 적은 set이겠죠?

그럼 대강 아래와 같은 방식으로 intersect를 수행합니다.

오오 Set은 간단하게 끝~!!

저작자 표시 비영리
신고
Posted by 오산돌구
TAG