조대 협의 블로그 : : ' 해 쉬 ' 태그 의 글 목록 
 total 6 , 063 , 282 
 today 6 , 771 
 yesterday 7 , 174 
 ' 해 쉬 ' 에 해당 되 는 글 2 건 
 2017 . 06 . 24 텐서 플로우 에서 array index 를 문자열 로 변환 하 는 방법 
 2016 . 02 . 06 Hashtable 의 이해 와 구현 # 1 ( 5 ) 
 텐 서 플로우 에서 array index 를 문자열 로 변환 하 는 방법 
 빅 데 이타 / 머신 러닝 | 2017 . 06 . 24 00 : 15 | Posted by 조대 협 
 예전 에 , 얼굴 인식 모델 을 만들 때 , 라벨 숫자 로 하 지 않 고 사람 이름 문자열 로 했 다가 이 문자열 의 배열 인덱스 를 구하 는 것 을 구현 하 지 못해서 라벨 을 다시 숫자 로 데 이타 를 재생성 한 적 이 있 었 다 . 텐 서 플로우 에서 텐서 는 파이썬 의 일반 자료 형 이 아니 기 때문 에 , 파이썬 의 배열 등 을 사용 하 지 못해서 생기 는 문제 였 는데 , 포기 하 고 있 다가 다른 코드 를 보 던 중 에 , 이 부분 을 해결 해 주 는 코드 를 찾 아서 , 정리 해 놓 는다 . 
 tf . contrib . lookup 에 이 를 지원 하 기 위한 함수 들 이 정의 되 어 있 다 . 
 https : / / www . tensorflow . org / api _ docs / python / tf / contrib / lookup 
 배열 인덱스 로 문자열 로 리턴 하 기 
 tf . constant ( [ ' Jessica ',' Jolie ',' Kidman ',' Sulyun ']) 
 # Initialize Table 
 print p 1 . eval ( ) 
 print p 2 . eval ( ) 
 tf . contrib . lookup . index _ to _ string _ from _ tensor ( ) 메서 드 를 이용 하 여 , index 를 string 으로 lookup 하 기 위한 테이블 을 생성 한다 . 이 때 테이블 에 들어가 는 배열 은 tf . constant 로 정의 해서 전달 한다 . 
 다음 이렇게 정의 된 테이블 을 사용 하 기 위해서 는 테이블 을 초기 화 해 줘야 한다 . 초기 화 는 
 를 사용 한다 . 이렇게 초기 화 된 테이블 은 세션 이 시작 된 후 에 , table . lookup ( $ 배열 의 인덱스 ) 를 호출 하 면 , 그 인덱스 에 해당 하 는 문자열 배열 값 을 리턴 한다 . 
 Sulyun 
 [ ' Jessica ' ' Kidman '] 
 문자열 로 배열 인덱스 구하 기 
 반대 로 문자열 로 배열 의 인덱스 를 리턴 할 수 도 있 다 . 함수 는 tf . contrib . lookup . index _ table _ from _ tensor ( ) 를 이용 하 여 , 문자열 이 들어간 배열 을 tf . constant 형태 로 넘기 면 되 고 , 찾 을 때 는 마찬가지 로 lookup ( ) 함수 를 이용 하 면 된다 . 
 연예인 얼굴 인식 모델 을 만들 어 보 자 - # 2 . CNN 모델 을 만들 고 학습 시켜 보 자 ( 12 ) 
 TAG Hashtable , index to string , look up , LOOKUP , number to string , string to index , string to number , table , tensorflow , tf . contrib , 강좌 , 문법 , 배열 , 인덱스 , 조대 협 , 초보 , 텐서 플로우 , 해 쉬 
 Hashtable 의 이해 와 구현 # 1 
 프로그래밍 / 알고리즘 | 2016 . 02 . 06 02 : 40 | Posted by 조대 협 
 해 쉬 테이블 의 이해 와 구현 ( Hashtable ) 
 기본 적 인 해 쉬 테이블 에 대한 이해 
 해 쉬 테이블 의 기본 적 인 개념 은 다음 과 같 다 . 
 이름 을 키 로 , 전화 번호 를 저장 하 는 해 쉬 테이블 구조 를 만든다고 하 자 . 전체 데 이타 양 을 16 명 이 라고 가정 하 면 
 ( 출처 : https : / / en . wikipedia . org / wiki / Hash _ table ) 
 이런 형식 으로 데 이타 를 저장 하 면 , key 에 대한 데 이타 를 찾 을 때 , hash _ function 을 한 번 만 수행 하 면 array 내 에 저장 된 index 위치 를 찾아낼 수 있 기 때문 에 , 데 이타 의 저장 과 삭제 가 매우 매우 빠르 다 . 
 충돌 처리 방식 에 따른 알고리즘 분류 
 그런데 , 이 해 쉬 테이블 문제 는 근본 적 인 문제 가 따르 는데 , hash _ function ( key ) / size _ of _ array 의 값 이 중복 이 될 수 가 있 다 . 
 예 를 들 어 저장 하 고자 하 는 key 가 정수 라고 하 고 , hash _ function 이 key % 10 이 라고 하 자 . 그리고 size _ of _ array 가 10 일 때 , key 1 , 11 , 21 , 31 은 같 은 index 값 을 가지 게 된다 . 이 를 collision ( 충돌 ) 이 라고 하 는데 , 이 충돌 을 해결 하 는 방법 에 따라서 여러 가지 구현 방식 이 존재 한다 . 
 1 . Separate chaining 방식 
 JDK 내부 에서 도 사용 하 고 있 는 충돌 처리 방식 인데 , Linked List 를 이용 하 는 방식 이 다 . 
 각 index 에 데 이타 를 저장 하 는 Linked list 에 대한 포인터 를 가지 는 방식 이 다 . 
 만약 에 동일 index 로 인해서 충돌 이 발생 하 면 그 index 가 가리키 고 있 는 Linked list 에 노드 를 추가 하 여 값 을 추가 한다 . 이렇게 함 으로써 충돌 이 발생 하 더라도 데 이타 를 삽입 하 는 데 문제 가 없 다 . 
 데 이타 를 추출 을 하 고자 할 때 는 key 에 대한 index 를 구한 후 , index 가 가리키 고 있 는 Linked list 를 선형 검색 하 여 , 해당 key 에 대한 데 이타 가 있 는지 를 검색 하 여 리턴 하 면 된다 . 
 삭제 처리 
 key 를 삭제 하 는 것 역시 간단 한데 , key 에 대한 index 가 가리키 고 있 는 linked list 에서 , 그 노드 를 삭제 하 면 된다 . 
 Separate changing 방식 은 Linked List 구조 를 사용 하 고 있 기 때문 에 , 추가 할 수 있 는 데 이타 수 의 제약 이 작 다 . 
 참고 : 동일 index 에 대해서 데 이타 를 저장 하 는 자료 구조 는 Linked List 뿐 아니 라 , Tree 를 이용 하 여 저장 함 으로써 , select 의 성능 을 높일 수 있 다 . 실제로 , JDK 1 . 8 의 경우 에 는 index 에 노드 가 8 개 이하일 경우 에 는 Linked List 를 사용 하 며 , 8 개 이상 으로 늘어날 때 는 Tree 구조 로 데 이타 저장 구조 를 바꾸 도록 되 어 있 다 . 
 2 . Open addressing 방식 
 Open addressing 방식 은 index 에 대한 충돌 처리 에 대해서 Linked List 와 같 은 추가 적 인 메모리 공간 을 사용 하 지 않 고 , hash table array 의 빈 공간 을 사용 하 는 방법 으로 , Separate chaining 방식 에 비해서 메모리 를 덜 사용 한다 . Open addressing 방식 도 여러 가지 구현 방식 이 있 는데 , 가장 간단 한 Linear probing 방식 을 살펴보 자 
 Linear Probing 방식 은 index 에 대해서 충돌 이 발생 했 을 때 , index 뒤 에 있 는 버킷 중 에 빈 버킷 을 찾 아서 데 이타 를 넣 는 방식 이 다 . 그림 에서 key % 10 해 쉬 함수 를 사용 하 는 Hashtable 이 있 을 때 , 그림 에서 는 충돌 이 발생 하 지 않 았 다 . 
 아래 그림 을 보 자 , 그런데 , 여기 에 11 을 키 로 하 는 데 이타 를 그림 과 같이 넣 으면 1 이 키 인 데 이타 와 충돌 이 발생 한다 . ( 이미 index 가 1 인 버킷 에 는 데이 타가 들어가 있 다 . ) Linear Probing 에서 는 아래 그림 과 같이 충돌 이 발생 한 index ( 1 ) 뒤 의 버킷 에 빈 버킷 이 있 는지 를 검색 한다 . 2 번 버킷 은 이미 index 가 2 인 값 이 들어가 있 고 , 3 번 버킷 이 비 어 있 기 3 번 에 값 을 넣 으면 된다 . 
 검색 을 할 때 , key 11 에 대해서 검색 을 하 면 , index 가 1 이 기 때문 에 , array [ 1 ] 에서 검색 을 하 는데 , key 가 일치 하 지 않 기 때문 에 뒤 의 index 를 검색 해서 같 은 키 가 나오 거나 또는 Key 가 없 을 때 까지 검색 을 진행 한다 . 
 이러 한 Open Addressing 의 단점 은 삭제 가 어렵 다는 것 인데 , 삭제 를 했 을 경우 충돌 에 의해서 뒤 로 저장 된 데 이 타 는 검색 이 안 될 수 있 다 . 아래 에서 좌측 그림 을 보 자 , 2 번 index 를 삭제 했 을 때 , key 11 에 대해서 검색 하 면 , index 가 1 이 기 때문 에 1 부터 검색 을 시작 하 지만 앞 에서 2 번 index 가 삭제 되 었 기 때문 에 , 2 번 index 까지 만 검색 이 진행 되 고 정작 데이 타가 들 어 있 는 3 번 index 까지 검색 이 진행 되 지 않 는다 . 
 그래서 이런 문제 를 방지 하 기 위해서 우측 과 같이 데 이타 를 삭제 한 후 에 , Dummy node 를 삽입 한다 . 이 Dummy node 는 실제 값 을 가지 지 않 지만 , 검색 할 때 다음 Index 까지 검색 을 연결 해 주 는 역할 을 한다 . 
 Linear probing 에 대한 샘플 코드 는 
 http : / / www . cs . rmit . edu . au / online / blackboard / chapter / 05 / documents / contribute / chapter / 05 / linear - probing . html 
 http : / / www . tutorialspoint . com / data _ structures _ algorithms / hash _ data _ structure . htm 
 Dummy Node 를 이용 해서 삭제 를 할 때 , 삭제 가 빈번 하 게 발생 을 하 면 , 실제 데 이타 가 없 더라도 검색 을 할 때 , Dummy Node 에 의해서 , 많 은 Bucket 을 연속 적 으로 검색 을 해야 하 기 때문 에 , 이 Dummy Node 의 개수 가 일정 수 를 넘 었 을 때 는 새로운 array 를 만들 어서 , 다시 hash 를 리빌 딩 함 으로써 , Dummy Node 를 주기 적 으로 없애 줘야 성능 을 유지 할 수 있 다 . 
 Open addressing 의 경우 , 고정 크기 배열 을 사용 하 기 때문 에 데 이타 를 더 넣 기 위해서 는 배열 을 확장 해야 한다 . 또한 Separate changing 에 경우 에 도 버킷 이 일정 수준 으로 차 버리 면 각 버킷 에 연결 되 어 있 는 List 의 길이 가 늘어나 기 때문 에 , 검색 성능 이 떨어지 기 때문 에 버킷 의 개수 를 늘려 줘야 한다 . 이 를 Resizing 이 라고 하 는데 , Resizing 은 별다른 기법 이 없 다 . 더 큰 버킷 을 가지 는 array 를 새로 만든 다음 에 , 다시 새로운 array 에 hash 를 다시 계산 해서 복사 해 줘야 한다 . 
 해 쉬 테이블 데 이타 구조 에서 중요 한 것 중 하나 가 해 쉬 함수 ( hash function ) 인데 , 좋 은 해 쉬 함수 란 , 데 이타 를 되 도록 이 면 고르 게 분포 하 여 , 충돌 을 최소 화 할 수 있 는 함수 이 다 . 수학 적 으로 증명 된 여러 가지 함수 가 있 겠 지만 , 간단 하 게 사용 할 수 있 는 함수 를 하나 소개 하 고자 한다 . 배경 에 대해서 는 http : / / d 2 . naver . com / helloworld / 831311 에 잘 설명 되 어 있 으니 참고 하 기 바란다 . ( 필요 하 면 그냥 외워서 쓰 자 ) 
 Cache 를 이용 한 성능 향상 
 해 쉬 테이블 에 대한 성능 향상 방법 은 여러 가지 가 있 지만 , 눈 에 띄 는 쉬운 방식 이 하 나 있 어서 마지막 으로 간략 하 게 짚 고 넘어가 자 . 해 쉬 테이블 의 get ( key ) 과 put ( key ) 에 간단 하 게 , 캐쉬 로직 을 추가 하 게 되 면 , 자주 hit 하 는 데 이타 에 대해서 바로 데 이타 를 찾 게 함 으로써 , 성능 을 간단 하 게 향상 시킬 수 있 다 . 
 다음 은 실제로 간단 한 HashTable 클래스 를 구현 하 는 방법 에 대해서 알아보 도록 하 겠 다 . 
 Hashtable 의 이해 와 구현 # 1 ( 5 ) 
 dynamic array resizing 에 대해서 . ( 5 ) 
 알고리즘 관련 유용 한 사이트 모음 ( 0 ) 
 그래프 노드 간 연결 파악 을 위한 Dynamic Connectivity 알고리즘 ( 0 ) 
 TAG hash map , Hashtable , linear probing , open addressing , separate chaning , 알고리즘 , 자료 구조 , 해 쉬 , 해 쉬 테이블