다음 내용은 정익사의 화일구조의 마지막에 나온 소스 (부록3. 디스크 기반 해시) 를 기반으로 설명된다.



                                                             (그림 - 1)


그림에서 주요 포인트는 :  디스크 , HashPage , HashRecord  이다. 


1. 초기화 


    -  디스크에 저장하기위해 파일을 만든다.(creat 함수, fopen 함수이용) 

    -  페이지 자체의 크기를 4096byte 로 설정한다.   (실제 디스크의 블럭크기와 일치시키면 좋을듯) 

    -  페이지의 갯수를 3000개로 설정한다. (자신이 만들 어플리케이션의 용도에 맞추면 좋고~) 

    -  HashPage  객체하나로  1->2999 번  (1개는 헤더용)  값을 바꾸어서 , 그 내용을 디스크상에 그대로 쓴다.

    -  아직 HashPage 안에 recArray 는 아직 아무 값이 없겠지요.

    -  결국 HashPage 는 아래처럼 초기화 된다. (pageNo 만 의미있는 수치를 갖음) 

           HashPage->pageNo = 1~2999

           HashPage->numOfRecords = 0;

     HashPage->prePageNo = -1;

     HashPage->nextPageNo = -1;

           HashPage->recArray = NULL;


                

2. 삽입 


 - 10,  'helloworld'  를 삽입한다고 치자.  (key 가 10 ,  value 가 "helloworld) 


1. 먼저  임의의 HashPage 객체를 만든다.

2. 10을 해쉬함수를 통해서 목표지점을 얻는다. ( key % 3000 => 10 ) 목표지점은 10 페이지. 

3. 디스크상의 10 번째 페이지를 검색해서  (검색방법은 아래 3.검색에서 살펴보자) 

     3-1. 동일한 키가 존재하면 FALSE 혹은 NULL 을 리턴한다.  (동일키 삽입 불가 정책) 

     3-2. 동일한 키가 없으면 4번으로 

4. 10번 페이지를 디스크상에서 읽어서 HashPage 객체에 저장. 

5. 해당 페이지(10번 페이지) 에 여유공간이 있는지 살펴본다.

     5-1. 여유 공간이 있으면 6 번으로 간다.

     5-2. 여유 공간이 없으면 다음 페이지 (11번 페이지) 로 넘어가서 여유공간을 확인한다.

     5-3. 모든 페이지에 여유 공간이 없으면 새로운 페이지를 만든다.  (3000개 -> 3001개의 페이지가 되겠지 )

6. HashPage 객체에 (10, "helloworld") 를 추가해서

7. 위의 객체를  디스크상의 해당 페이지 위치에 쓴다.



3. 검색 


- 위에서 말한  디스크상의 10번째 페이지를 검색해서 key 10 번이 있는지 확인해보자

1.  해당 10번 페이지를 디스크에서 읽어옴 

2.  recArray 에서 key 가 10번이 있는지 확인한다. 

     2-1.  있으면  멈추고  리턴 해줌.  ( 동일 키가 있다고 알려줌)  

3. 해당 페이지 (10 번 페이지) 에 키가 없으면 , 다음 페이지를 검색한다.( 페이지 끝까지 검색한다. 좀 비효율적) 

4. 모든 페이지에서 key 10 번을 못찾으면 FALSE 를 리턴해준다. 



정리를 해보자.


- 디스크상에 파일을 통해서 고정크기를 할당해두고, 고정크기만큼 나누어준다.

- 고정크기를 페이지라고하고 , 해당 페이지에는 같은 값으로 해슁된 키를 우선 넣어둔다.

- 한곳의 페이지에 키들이 몰리면, 나머지 페이지들의 공간에 낭비가 생기기때문에,

  페이지에 공간이 없으면 다음 페이지에 키를 넣어둔다. (다음페이지도 없으면 다다음) 

- 덕분에, 검색할때는 모든 페이지를 검색해야하는 단점이 있다.



코드 몇 조각  (전체소스는 책 참고. 인터넷에 소스는 없는듯)


struct hashRecord{

Key key;

Value value;

} ;


struct hashPage{

int pageNo;

int numOfRecords;

int prevPageNo;

int nextPageNo;

HashRecord * recArray;

};


struct BufferManger{

File * fp;

int pageSize;

int maxPageNo;

int lastFreePageNo;

};


BOOL readPage(int pageNo, BYTE* buffer){

int ret;

fseek(bufferManger->fp, pageNo * bufferManager->pageSize, SEEK_SET);

ret = (int) fread(buffer, sizeof(BYTE), bufferManger->pageSize, bufferManager->fp);

if(ret>0) return TRUE;

else return FALSE;

}

저작자표시 비영리 변경금지 (새창열림)

'알고리즘,자료구조' 카테고리의 다른 글

레드블랙트리 vs 해쉬테이블 (TreeMap vs HashMap)  (0) 2015.09.14
레드블랙트리 (red-black tree) 삽입  (0) 2015.09.10
Finding Kth largest element in Array  (0) 2015.05.12


C++ 의 map 은 레드블랙트리로 구현되있으며, java 의 treeMap 또한 레드블랙트리로 구현되어있습니다.

C++ 진영에서 해쉬테이블이 표준으로 구현되지 않았었기때문에,  많은 경우 해쉬를 굳이 외부라이브러리등

을 통하거나,만들어서 사용하지 않았는데, 그 의미는 많은 경우에 있어서 레드블랙트리로 맵을 사용하는게 충

분하다는 방증(circumstantial evidence) 이겠지요. Java 진영에서는 많은 경우 HashMap 을 사용하더군요.  

이런걸 보면 , 두개 알고리즘의 각각의 특징에 따라서 맵을 사용한다기보다는 , 대개의 프로그래머들은 그냥 

아무 생각없이 많이 쓰여 지는것을 쓴다고 볼수있습니다. 이 얘기는 프로그래머들이 게을러서라고 생각치 않

습니다. 많은 경우 두개의 알고리즘의 성능차이는 80대20법칙에서 중요치 않은 쪽에 속한다고 볼수있겠지

요. 어플리케이션 성능 체크를 해볼때, 병목이 일어나는 곳은 다른곳에 있었을 테니깐요.


그래도 우리는 소프트웨어 개발자이기때문에, 가끔 먼가 꺼림칙하기도 합니다. 따라서 여기에 

레드블랙트리의 장점을 간략히 기술해보면 


레드블랙트리의 장점 (해쉬에 비해)

- 순서가 있는 자료일 경우.  (해쉬는 순서가 없습니다) 

- 일관성있는 퍼먼스를 보여줍니다. (해쉬는 rehashing 될때 비정상적인 시간이걸릴수있음)

- 해쉬는 페이지폴트를 일으킬수있다. (페이지간 전환이 많아지면 느려지겠지요) 

- 연속된 삽입간에 지역성을 유지하기 쉽다. 더 적은 I/O 가 발생한다.( 해쉬테이블은 효율적인        lookup 을 위해 버켓안의 모든 요소를 스왑할수있다)

- 해쉬는 테이블 리사이징 이슈 : 갑자기 성능이 다운됨.

- 해쉬는 메모리 낭비가 있을수있다.( 이건 해쉬의 구현이 어떻게 되있냐에 따라 다름)

- 트리는 부정확한 검색에 사용될수있다.( "a" 로시작되는 모든것, 범위검색) 



자바를 사용해 개발한다면, 대부분의 경우 순서가 필요하면 TreeMap , 아니면 HashMap 을 쓰는게 좋다고 

생각합니다. Hash 가 java 7 에서 또 한번 큰 발전이 있었으며,(http://d2.naver.com/helloworld/831311) 

큰 차이가 없다면 가독성이라도 도움이 되니깐요. 아 이건 순서를 중요시했구나, 순서가 필요없구나~ 

물론 많은 데이터를 관리해야할 필요가 있을때는, 벤치마크가 필요하겠지요. 





I'll talk about the HashMap and TreeMap implementation in Java:

  • HashMap -- implement basic map interface

    1. implemented by an array of buckets, each bucket is a LinkedList of entries
    2. running time of basic operations: put(), average O(1), worst case O(n), happens when the table is resized; get(), remove(), average O(1)
    3. not synchronized, to synchronize it: Map m = Collections.synchronizedMap(new HashMap(...));
    4. Iteration order of the map is unpredictable.

  • TreeMap -- implement navigable map interface

    1. implemented by a red-black tree
    2. running time of basic operations: put(), get(), remove(), worst case O(lgn)
    3. not synchronized, to synchronize it: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
    4. provide ordered iteration. higherKey(), lowerKey() can be used to get the successor and predecessor of a given key.

To sum, the biggest difference between HashMap and TreeMap is that TreeMap implements NavigableMap<K,V>, which provide the feature of ordered iteration. Besides, both HashMap and TreeMap are members of Java Collection framework. You can investigate the source code of Javato know more about their implementations.


저작자표시 비영리 변경금지 (새창열림)

'알고리즘,자료구조' 카테고리의 다른 글

디스크 상에서의 HashMap 구현  (0) 2015.11.03
레드블랙트리 (red-black tree) 삽입  (0) 2015.09.10
Finding Kth largest element in Array  (0) 2015.05.12

레드블랙트리는 이진트리이자, 균형을 갖춘트리입니다. C++ 의 map 이 레드블랙트리 기반이며, jemalloc 에서도 사용됩니다.레드블랙트리의 정의는 다음과 같습니다.

1. 모든 노드는 red나 black의 색깔을 갖는다.
2. Root 노드는 항상 black이다.
3. 모든 leaf 노드는 센티넬 노드(sentinel node)로서 black이다. (일단 항상 2개의 다른 값으로 채워질 수 있는 NIL=NULL 자식을 가진다.)
4. Red 노드의 자식은 모두 black이다. (Black의 자식은 black/red 모두 가능)
5. 루트(root)에서 leaf로의 경로를 생각할 때, 모든 경로에 대해서 black의 숫자는 같다. (이것을 black height라고 한다.)


삽입

삽입시에 이진트리와 마찬가지로 자신의 위치를 찾아가서 매달리게되는데, 그 이후에 레드블랙트리의  정의에 맞게끔 재구성이 시작됩니다.

부모가 조부모의 오른쪽 자식인지 왼쪽 자식인지에 따라 두가지의 경우로 나뉘는데 이 두 경우는 서로 정확히 대칭이므로 여기서는 부모가 조부모의 왼쪽 자식인경우 위주로 설명합니다. 레드블랙 트리 삽입을 이해하는데 매우 중요한 포인트 입니다. 대부분의 블로그 설명에서 이거 빼놓은듯 싶네요. 


노드 삽입를 위해서 먼저 binary search tree에 대한 노드 삽입 알고리즘대로 노드를 일단 추가한다. 당연히 새롭게 삽입된 노드는 기존의 센티넬 노드의 자리에 추가되어야 한다. 즉, 새 노드는 두 개의 센티넬 노드를 자식 노드로 갖고 기존 센티넬 노드 자리에 들어가게 된다. 새롭게 삽입된 노드의 색깔은 무조건 R 로 한다. (단, root 노드로 삽입시 B)

A. Root로 삽입

  1. void insert_case1(node n)
  2. {
  3.     if (n->parent == NULL)
  4.         n->color = BLACK;
  5.     else
  6.         insert_case2(n);
  7. }


N 이 root로 삽입되었다. 속성 2를 위해 B 로 설정한다.


B. 부모 P가 Black 인 경우

  1. void insert_case2(node n)
  2. {
  3.     if (n->parent->color == BLACK)
  4.         return; /* Tree is still valid */
  5.     else
  6.         insert_case3(n);
  7. }


삽입되는 노드는 red로 설정되기 때문에 속성 4를 만족하며 N이 red로 삽입되면서 2개의 black nil 자식을 가지기 때문에 각각의 leaf까지 black의 수는 똑같으므로 속성 5도 만족하며 아직 valid 한 RB 트리.

이 상황에서 다시 노드를 삽입하면...

1. 센티넬 노드 자리에 센티넬 노드를 자식으로 갖는 노드를 추가했기 때문에 속성 1, 2는 만족한다.
2. R로 했기 때문에 속성 3, 5를 만족한다.

위반할 수 있는 속성은 속성 4 밖에 없다. 즉, 다른 속성에 위반되지 않도록 하면서 속성 4 를 만족하도록 트리를 변경해 주면된다. 속성 4 를 위반하는 경우는 새로운 노드의 부모 노드가 R인 경우 밖에 없다. 이 때에 대한 처리 방법은 아래의 C, D의 2가지 경우로 나뉜다.

C. 부모가 R, 삼촌도 R

  1. void insert_case3(node n)     // 이미 부모는 R이 판명된 상태
  2. {
  3.     if (uncle(n) != NULL && uncle(n)->color == RED)
  4.     {
  5.         n->parent->color = BLACK;
  6.         uncle(n)->color = BLACK;
  7.         grandparent(n)->color = RED;
  8.  
  9.         insert_case1(grandparent(n));
  10.     }
  11.     else
  12.         insert_case4(n);
  13. }


부모가 R 이라면 할아버지는 반드시 B 여야 한다. (기존 트리가 RB트리 속성을 모두 만족하기 때문에 연속된 R을 갖을 수는 없다.) 부모와 삼촌이 모두 R 이라면 아래의 그림처럼 부모와 삼촌을 B로 바꾸고 할아버지를 R로 바꾼다. 이렇게 하면 모든 노드의 black height는 보전된다.

새롭게 생긴 R 노드, 즉 할아버지 노드에 대해서는 지금 적용한 삽입후 처리 알고리즘을 재귀적으로 적용할 수 있다. 할아버지 노드는 R 노드이고 B 를 자식으로 갖기 때문에 새롭개 삽입된 노드의 특징을 모두 지니기 때문에 같은 알고리즘이 적용될 수 있다. 만약 할아버지 노드가 루트 노드라면 할아버지 노드를 다시 B 로 칠하면 된다. 이 경우는 전체 트리의 black height가 1 증가하게 된다. (X의 black 자식으로 인해 height 1->2로 증가)

D. 부모가 R, 삼촌은 B

  1. // 삽입된 노드와 부모, 부모의 부모가 일련의 왼쪽 라인을 타도록...
  2. void insert_case4(node n)      
  3. {
  4.     if (n == n->parent->right && n->parent == grandparent(n)->left)
  5.     {
  6.         rotate_left(n->parent);
  7.         n = n->left;
  8.     }
  9.     else if (n == n->parent->left && n->parent == grandparent(n)->right)
  10.     {
  11.         rotate_right(n->parent);
  12.         n = n->right;
  13.     }
  14.     insert_case5(n);
  15. }
  16.  
  17. // 노드와 부모와 부모의 부모, 모두 같은 방향의 자식 관계라면... 색 반전하면서 회전
  18. void insert_case5(node n)
  19. {
  20.     n->parent->color = BLACK;
  21.     grandparent(n)->color = RED;
  22.  
  23.     if (n == n->parent->left && n->parent == grandparent(n)->left)
  24.     {
  25.         rotate_right(grandparent(n));
  26.     }
  27.     else
  28.     {
  29.         /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
  30.         rotate_left(grandparent(n));
  31.     }
  32. }



CASE D-1  (부모의 오른쪽 자식일때)

부모를 중심으로 왼쪽으로 회전한다. 여전히 레드블랙특성 4를 위반한다. CASE D-2 로 이동한다.


CASE D-2 (부모의 왼쪽 자식일때) 

조부를 중심으로 오른쪽으로 회전하고 부모와 조부의 색상을 맞바꾼다.


케이스 D 를 만나면 CASE D-2 의 수선을 마지막으로 상황이 종료된다.

케이스 C 를 만나면 상황이 끝날수도있고, 똑같은 상황이 다른노드에서 다시 시작될수도있다. 

재귀적으로 반복해서 루트까지 올라갈수도있다.


다시 한번 언급하지만  위의 CASE 들은 부모가 조부모의 왼쪽 자식을 기준으로 설명한것이다.

그 반대도 정확히 대칭이므로 반대로 생각하면 된다.

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 를 이용하여 시뮬레이션을 해보았다.

부모가 조부모의 왼쪽 자식인지 오른쪽 자식인지 염두해두고 살펴보자. 

                               100이 추가되며, 루트가 되면서 검정색이 되었다.

                             150이 빨강색 노드로 루트의 오른쪽에 여느 이진트리처럼 배치되었다.

                                 200이 추가된후에  좌회전되며 150이 루트가 되었다.

                               300 이 추가된후에 부모와 삼촌노드가 검정색으로 변경되었다. 

       180이 추가된후에 부모(175)와 삼촌(300) 가 검정이 되고 할아버지(200)이 빨강이 되었다.

다음 160번 노드 인서트되면서 대격변의 시작이다. 눈여겨 살펴보자.

160번 노드 삽입 


      삽입된 노드와 부모가 모두 빨강이라, 부모와 삼촌을 검정으로 바꾸고 할아버지를 빨강으로 바꿈 

할아버지 노드 = 그냥 삽입한 노드로 생각하고 다시 시작.  그 노드와 부모노드가 빨강이다. 

삼촌은 검정이다. 노드는 왼쪽자식이고 부모는 오른쪽 자식이다.  회전한다. 

                                                우회전 후 모습 


  노드와 부모가 모두 빨강, 노드는 오른쪽 자식이다. 부모는 오른쪽 자식이다. 회전을 통해 바로잡는다.


                                               좌화전후 모습 

                                          루트를 검정색으로 바꾸고, 정리한다.

레퍼런스:
http://www.yes24.com/24/goods/9345796?scode=032&OzSrank=3  https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
http://egloos.zum.com/sweeper/v/900135
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

저작자표시 비영리 변경금지 (새창열림)

'알고리즘,자료구조' 카테고리의 다른 글

디스크 상에서의 HashMap 구현  (0) 2015.11.03
레드블랙트리 vs 해쉬테이블 (TreeMap vs HashMap)  (0) 2015.09.14
Finding Kth largest element in Array  (0) 2015.05.12 


public class KthLargest {
 
  public static void main(String[] args) {
    int[] x = new int[] { 3, 6, 92, 34, 1, 35, 62, 13, 12, 24, 53 };
    System.out.println(getKthLargest(x, 3));
  }
 
  private static int getKthLargest(int[] x, int k) {
    int low = 0;
    int high = x.length - 1;
 
    while (true) {
      int pivot = (low + high) / 2;
      int newPiv = partition(x, low, high, pivot);
 
      if (newPiv == k) {
        return x[newPiv];
      } else if (newPiv < k) {
        low = newPiv + 1;
      } else {
        high = newPiv - 1;
      }
    }
  }
 
  private static int partition(int[] x, int left, int right, int pivot) {
    int pivValue = x[pivot];
    swap(x, pivot, right);
    int storePos = left;
 
    for (int i = left; i < right; i++) {
      if (x[i] < pivValue) {
        swap(x, i, storePos);
        storePos++;
      }
    }
    swap(x, storePos, right);
    return storePos;
  }
 
  private static void swap(int[] x, int a, int b) {
    int temp = x[a];
    x[a] = x[b];
    x[b] = temp;
  }
 
}


저작자표시 비영리 변경금지 (새창열림)

'알고리즘,자료구조' 카테고리의 다른 글

디스크 상에서의 HashMap 구현  (0) 2015.11.03
레드블랙트리 vs 해쉬테이블 (TreeMap vs HashMap)  (0) 2015.09.14
레드블랙트리 (red-black tree) 삽입  (0) 2015.09.10

+ Recent posts

티스토리툴바