weasel의 우당탕탕 개발기

Why B 트리?

B 트리는 이진트리와 다르게 하나의 노드에 많은 정보를 가질 수 있는 트리를 의미한다. 노드의 최대 자식의 개수를 M이라고 할때, M차 B트리라고 한다.

B 트리는 고전적인 메모리 계층 구조의 물음에서 출발한다.
이진탐색트리의 시간복잡도가 최악이 될 때는 노드가 편향된 경우인데, 이를 해결하는 것이 AVL,RB 트리와 같은 균형이진트리다.

그런데 이것만으로 부족하다. 왜 그러냐면, O(logn) 을 보장하는 균형이진트리의 최악을 생각해보자.

최악이 있을까? 분명히 있다.

RB트리에서 원소가 1백만개라고 해보면, 트리의 높이는 최대 2*log(10^6)이다. 따라서 대략 20정도이다.

RB 트리에서 Red 노드는 최대 두개만 연속으로 되어있음을 생각하면 쉽게 알 수 있다.

그러면, 원하는 원소를 찾기 위해서 20번 정도의 노드 액세스가 필요한데,
만약 모든 노드가 메인 메모리에 있다고 생각해보면, 매우 비싼 20번의 메모리 접근이 일어나는 것이다.

심지어 메인 메모리가 아닌 디스크에 있다면? 더 많은 시간이 단순히 노드에 접근하는데 쓰일 것이다.

따라서 이러한 메모리, 디스크에 관한 접근을 줄여야 한다. 그러기 위해서는 트리의 탐색 높이를 줄여야 한다.
이진트리에서 log의 베이스가 2인 이유가 2개의 자식노드임을 기억했을때 degree를 늘려야 하는 것이다.

💡 실제로는 트리 노드들이 하나의 캐시 라인이나 디스크 블록을 채울 수 있는 가장 큰 차수를 사용하고 있다.

따라서 B 트리는 아주 많은 양의 데이터들이 존재하는 곳에 사용되고, 높이를 h 라고 할때, 조회,삽입,삭제 등등의 동작 모두 O(h) 의 디스크 접근을 요구한다.

B 트리는 노드에 가능한 최대의 키들을 삽입하면서 트리의 높이를 낮게 유지한다.

즉, Balanced를 삽입,삭제 과정에서 혼자서 유지한다는 것이다.

그렇기에 AVL,RB 트리와 비교해서 매우 낮은 디스크 접근을 수행한다.

💡 이게 뭔말인가 했더니 노드의 사이즈를 디스크 블록 사이즈와 거의 동일하게 유지한다는 말, 어차피 디스크 액세스할때 1K 읽나 , 1 Byte 읽나 오버헤드는 같으니까, 한번에 많이 읽어오면 되는거다.

이러한 여러가지 특성때문에 B 트리는 B+트리와 더불어서 DBMS에서 많이 사용되고 있다.

💡 인덱스 다룰때 많이 쓴다고 한다. 요즘에 MongoDB 만지는데 대놓고 공식문서에 인덱스는 B트리 쓴다고 되어 있다. 물론 PostgreSQL 이런건 B+트리도 쓰고, MySQL은 B 트리,B+트리, 해시 다 쓴다.

B 트리 정의

degree가 m인 B트리는 아래와 같은 특성을 가진다.

• 루트 노드는 적어도 2개의 자식을 가진다.
• 루트 노드와 외부 노드를 제외한 모든 내부 노드는 적어도 올림(m/2)개, 최대 m 개의 자식을 가진다.
  • m=2이면, 1~2개의 자식 노드 → 포화 이진 트리
  • m=3이면, 2~3개의 자식 노드 → 2-3 트리
  • m=4이면, 2~4개의 자식 노드 → 2-3-4 트리
• 모든 외부 노드들은 같은 레벨에 있다. (Perfectly Balanced)
  • 이게 매우 중요... 높이의 상한을 준다는 것이니까 디스크 접근에 대한 상한을 준다는 것.
  • 그림에서 {8,11}, {22,23}, {58,59} 같은 애들을 외부 노드라고 부른다.
• 각각의 노드는 적어도 [m/2] 개, 최대 m-1 개의 키를 가질 수 있다.
  • 아래 그림을 보면, m=3일때, [3/2]=1 ~ 3-1=2 개의 키를 가진다.
  • 
  • 이런 조건이 있는 이유는, 만약 m=5일때 , 1개의 키가 있다고 해보자. 다음 키는 그 키보다 작거나 크거나 즉 두개인데, 그러면 3-4-5 트리를 만족하지 않는다.

B 트리의 목적이 데이터를 넓게 흩뿌리면서 높이를 낮게 가져간다는 점을 생각해보면서, n개의 원소가 있다고 할 때, 높이의 상한에 대해서 계산해보자.

• Best Case
  • 최고의 경우는 가장 잘 흩뿌려질때니
  • logm(n) n=(log n)/(log m)=O(log n)
• Worst Case
  • 최악의 경우는 가장 덜 흩뿌려질때, 즉 노드가 최소의 자식을 가지는 올림(m/2) 갈래로 흩어질때임.
  • log올림(m/2)(n)=(log n)/(log(올림(m/2))=O(log n)

즉 모든 최고,최악의 경우 모두 O(log n) 의 높이가 보장됨을 알게 되었다.

조회

조회는 이진탐색의 그것과 매우 비슷하다. 이진 탐색에서 조회는 분기가 세가지다. (못 찾는 경우 제외)

내가 찾는 키를 k 라고 하고, 노드의 키를 v 라고 하면,

• k=v : 같거나 → 찾았다.
• k>v : 작거나 → 왼쪽 서브 트리로 간다.
• k<v : 크거나 → 오른쪽 서브 트리로 간다.

이것처럼 B 트리에서도 비슷한 방식대로 움직이는데, 분기가 두가지다.

• k=v : 같거나 → 찾았다.
• i-th v< k < i+1-th v 를 만족하는 i 를 찾고 i-th pointer 가 가르키는 서브트리로 간다.
  • 이때 만족하는 i 는 최대 m-1 개이므로, 루프를 돌아도 되고, 이진 탐색을 수행해도 된다. ← 루프를 돌아도 안전한게, 어차피 같은 메모리안에 올라와
    있다. 추가적인 디스크 액세스가 필요하지 않다.
    

    

삽입

삽입부터 B 트리가 복잡해지고, 또 그 과정에서 B 트리가 가지는 균형유지의 전략을 볼 수 있다.

일단, 조회의 과정을 거치고, 삽입할만한 적절한 리프 노드 위치를 찾는다. 그 다음부터 분기가 나뉜다.

💡 리프 노드에 넣는 이유는 아래에서 설명하겠지만 삽입시에 일어나는 분할이 상향식이기 때문이다.

• 삽입할 곳에 자리가 남아있다면 (current capacity<m-1) , 그냥 넣고 끝낸다.
• 삽입한 뒤에 넘친다면, 분할한다.

분할

리프노드에 삽입한 후에 m개의 키를 가진다면, 분할하는 과정을 거친다. m개의 키를 가진 노드에 대해서 세 그룹으로 분할한다. (아래 과정은 m이 홀수일때)

1. 중위순서의 키보다 작은 키들로 이루어진 노드들
2. 중위순서의 키
3. 중위순서의 키보다 큰 키들로 이루어진 노드들

그리고 1번과 3번 그룹의 부모를 2번으로 만든다. 즉, 여전히 성질이 깨지지 않게끔 하는 것.

만약 이때 부모가 넘친다면? 또 다시 진행한다. 그렇기에 리프노드에서의 넘침이 상향식으로 전파될 가능성이 있는것.

이게 루트까지 넘친다면, 루트에 대해서 두 개의 자식을 가지는 새로운 노드를 만든다.

예시를 다 보여주기에는 어려우니, 가장 복잡한 예시만 들면 아래와 같다.

우선 67이 들어갈 위치를 찾는 과정을 거치고, 넣을만한 곳을 찾았는데 넣는 순간 5개의 키를 가지면서 넘친다. 분할 발생!
중위순서의 키는 67이니, {55,66}, {67}, {68,70} 로 나눈 후 {55,66} → {67} ← {68,70} 으로 만든다.

근데 67이 들어갈 위치는 50의 옆이다. 그런데 그럼 루트에서 넘침이 생기니, 루트에 대해서 상향식으로 분할이 전파된다.

따라서 {5,10} → {22} ← {50,67}의 구조로 만든 후 체크하면 5개의 키를 안 넘치니 끝.

삭제

삭제는 삽입보다 복잡하다.

B트리에서의 삭제는 삭제된 후에 B트리의 성질을 유지하기 위해서 최소키의 개수를 만족하는지,
만족하지 않으면 추가적인 조치가 필요하기 때문이다.

B트리에서의 삭제는 크게는 두가지, 작게는 세가지 경우가 있는데 , 먼저 삭제할 키인 k가 리프에 있는지 없는지를 따져서 두가지로 나뉜다.

💡 모든 삽입, 삭제 과정에서 k가 들어갈 혹은 삭제될 위치를 찾는 조회과정이 선행된다.

k가 리프에 있을때

근데 여기서 또 나뉜다. 골치 아프다. 아래 과정에서 m은 3이다. (2-3트리)

• k가 있는 노드의 키의 개수가 최소 키의 개수보다 클때 → 그냥 k를 삭제해도 아무런 문제가 없다.
• 형제 노드 중 하나의 키의 개수가 최소 키의 개수보다 클때
  1. 부모 키의 값으로 k를 대체한다.
  2. 최소 키의 개수보다 큰 형제노드가 왼쪽 형제라면 가장 큰 값을, 오른쪽 형제라면 가장 작은 값을 부모 키로 대체한다.
  3. 
• 양 쪽 형제가 최소 키의 개수를 가지고 있고 , 부모 노드의 키가 최소 키의 개수보다 많다면,
  1. k를 삭제한 후, 부모 키와 형제 노드를 병합한다. → 정확히는 부모 키가 내려오는 것.
  2. 부모노드의 키를 하나 줄이고, 자식 수 역시 줄여서 B트리의 특성을 유지한다.
  
• 양 쪽 형제가 최소 키의 개수를 가지고 있고, 부모 노드 역시 최소 키의 개수면 → 부모를 루트로 한 서브 트리의 높이 자체가 줄어들기 때문에 재구조화가 이어진다. 아래 참조
  • 어디에서 가져오든, 무조건 빵꾸가 생기잖아요~

k가 내부노드에 있고, 현재 노드 혹은 자식 노드의 키의 개수가 최소 이상일때

k를 predecessor(왼쪽 서브트리의 가장 큰 값) 혹은 successor(오른쪽 서브트리의 가장 작은 값)와 교환해준다. 찾는 과정은 BST의 그것과 매우 유사.

그런 후에 리프 노드가 된 k 를 삭제한 후 필요에 의해서 리프노드에서의 삭제 핸들링 과정으로 넘어간다.

위의 그림에선, 양쪽 형제 모두 최소 키의 개수만큼 가지고 있고, 부모노드의 키의 개수가 최소개수 이상이니 15,17이 병합된다.

k가 내부노드에 있고, 현재 노드,자식 노드의 키의 개수가 최소개수일때

만약 이 상황에서 k를 삭제하면, 전체적인 높이가 낮아지면서 B 트리의 조건을 유지하려 함. 이를 트리의 재구조화라 한다.

1. k를 삭제하고, k의 자식을 하나로 합친다.
2. k 의 부모 키를 인접한 형제노드에 붙인다. (이때 k 는 당연히 루트가 아니다. 루트면 위에서 걸렸겟지)
3. 아까 병합한 노드를 2번의 자식노드로 설정한다. (왼쪽 혹은 오른쪽)
4. 만약 이럴때, 부모노드의 키의 개수에 따라 수행 과정이 다르다. 이에 대해서 또 분기한다.

• 새로 구성된 인접 형제노드(부모 키 붙인)가 오버플로우 나면, 삽입연산에서의 분할 수행
• 인접 형제노드가 구성되더라도, k의 부모 노드가 최소 키의 개수보다 작아진다면, 다시 위의 2번 과정부터 수행한다.

다른 예시

4를 삭제하자. 이러면 현재 노드, 자식 노드 모두 키가 최소다.

2와 6을 합치고,

내 부모 노드와 합친것을 자식-부모관계로 연결시켜준다.

이때 7,9,11이 오버플로우가 나니 중앙값인 9를 분할해 처리한다.

당연하게도 9,15에 대해서 분할의 propagation이 일어날 수 있다.

차수에 대한 고민

결국에 높이를 최대한 낮춘다는 것이 B 트리의 성능 개선점이라고 보았을때, 차수(degree 혹은 order)를 잘 고르는 것이 중요하다.

좋은 차수를 고르는 방법은, 페이지 사이즈에 꽉 맞춰 들어가는 최대한 큰 사이즈의 노드를 고르는 것이다.

만약에 디스크에서 읽어오는 데이터베이스를 B 트리를 통해서 구성하려 한다면,
각각의 노드가 디스크 페이지 크기에 딱 맞는 사이즈를 골라야 할 것이다.

만약에 In-memory 데이터베이스를 구성하려 한다고 해보자.
그 말은 데이터는 메모리<->메모리 간 이동이 많을 것이고 중간에 L2 혹은 L3 캐시에 적재될때가 가장 빠른 접근을 할 수 있을때이다.

따라서 최대한 캐시 효율을 누릴 수 있게 L2나 L3 캐시의 라인 사이즈에 맞게끔, 즉 초과해서 캐시 바깥의 노드를 읽을 필요가 없게끔 구성해야한다.

모든 케이스에서 어떤 차수를 사용하는지 고르기 전에 먼저 하드웨어에 대한 스펙을 봐야할것이고,
내가 구현하려는 기능에서 B 트리가 어떤 역할을 하는지 알아야 할 것이다.

💡 Typically, you'd choose the order so that the resulting node is as large as possible
while still fitting into the block device page size.
If you're trying to build a B-tree for an on-disk database, you'd probably pick the order
such that each node fits into a single disk page,
thereby minimizing the number of disk reads and writes necessary to perform each operation.
If you wanted to build an in-memory B-tree, you'd likely pick either the L2 or L3 cache line sizes as your target
and try to fit as many keys as possible into a node without exceeding that size.
In either case, you'd have to look up the specs to determine what size to use.

강점

B 트리가 어떻게 균형을 유지하는지는 알았는데 실용적으로 어떤 강점이 있을까?
HashTable의 grow 된다는 점을 생각하지 않았을때, O(1) 이어서 더 유리한거 아닌가?

분명한 건 해시테이블을 이용할때는 하나의 조회에 있어서 O(1)이 소요되는것은 맞다.
하지만, 이 조회는 어디까지나 Hash Table.eqaul(key) 의 결과물이지 DB에서 쓰이는 range 와 같은 연산을 수행하지 못한다.

💡 실제로 회사에서 설계를 하면서 Redis를 사용하자는 의견이 나왔을때, 이 근거로 반대했다. range 연산이 필요한 곳에서는 HashTable에 기반한 redis는 전혀 이점을 누릴 수 없다.

즉, range 와 같은 연산을 수행할때는 계속된 참조가 필요한 것이다. 또, 해시테이블에서 특별한 구현체를 제외하고는 일반적으로 데이터가 정렬되어 있지 않다. 그렇기에 range 와 같은 연산이 매우 비효율적인것이다.

그럼 해시테이블과 비교했을때 강점에 대해서는 알았는데, 다른 트리랑 비교하면 어떨까?
다른 트리에서도 O(log n) 을 지원하는데 그건 왜 사용되지 않을까?

앞서 말한 높이의 상한에 있어서의 엄격함과 더불어서 B 트리의 노드들의 데이터는 배열속에서 순차적으로 저장되어 있고,
연속적으로 메모리에 저장되어 있음을 뜻한다. 즉, 공간지역성이 높다는 것이다.

다시 말해서, B 트리노드 끼리 참조로 이동할때는 디스크 액세스가 필연적이지만, 노드 내부의 데이터들은 배열과 같은 구조로 저장되어 있기 때문에 Sequential access에 유리하다. 이는 공간지역성에 의해서 캐시효율이 높음을 의미한다.

그렇기에 같은 O(log n) 의 시간복잡도를 가져도, 다른 트리보다 빠른 접근이 가능한 것이다.

다른 트리는 노드끼리 이동할때 자연스럽게 추가적인 메모리 접근이 필요하지만, B 트리에서 노드 안의 데이터 접근은 공간지역성을 충분히 누릴 수 있다는 것.

정리하자면,

1. 항상 정렬된 상태이기에 부등호 연산에 유리하다.
2. 참조 포인터가 적어 빠르게 메모리 접근이 가능하다.
3. 데이터 탐색뿐 아니라 삽입, 삭제에도 O(h) = O(log n)의 시간 복잡도를 가진다.

   #define order 3
   struct B_node {
       int order; /* number of children /
       B_node *child[order]; / children pointers /
       int key[order-1]; / keys */
   }

```

💡 그런데 이제 h에 밸런싱을 곁들인...

요즘 MongoDB에 대해서 빡세게 사용중인데, 정말 자료구조가 중요함을 새삼 느낀다.
백엔드 개발자가 DB 모르는건 말이 안되니까.

Stack

선형자료구조의 일종으로 LIFO의 특성을 가지고 있다. 가장 처음 들어간 원소가 가장 나중에 접근 가능 하고, 다시 말해서 호출 시에 가장 최근의 원소에 접근 할 수 있다. O(n)의 공간복잡도를 가진다.

링크드 리스트를 이용한 구현과 배열을 이용한(정확히는 Dynamic Array) 두가지 버전이 있다. 링크드 리스트는 일관적인 시간복잡도 O(1)를 보여주는 대신에 추가적인 메모리 사용량(Node 구조를 유지하는데 드는)과 메모리 할당에 추가적인 비용이 들 수 있다.

• 조회 : Top에 있는 원소를 조회할때는 O(1), 하지만 특정한 데이터를 찾고자 할때는 O(n)이다.
• 삽입 : 링크드 리스트를 이용한 구현에서는 단순히 기존의 Top 원소를 새 원소의 next 로 연결시켜주고 head 의 포인터에 새로운 원소를 연결시켜주면 되기 때문에 O(1)이다.
  배열을 이용한 구현에서도 특정 상황(Dynamic array의 팽창)을 제외하고는 O(1)이니 amoritezd\ O(1)이다.
• 삭제 : 링크드 리스트와 배열 모두 O(1)이다.

활용

• Stack Usage : JVM stack, 컴파일러에서 문법 체크(matching parentheses)

💡 프로그램의 함수 호출과 실행 순서는 아래와 같으니

스택프레임에 지역변수,매개변수,복귀주소등의 정보를 저장하고

함수의 실행이 끝나면 stack frame의 top을 pop한 후 복귀 주소로 복귀한다
가장 마지막에 호출된 함수를 가장 먼저 처리하고 복귀하는 후입선출의 구조를 처리하기 위해서 스택을 이용해서 관리한다.

Queue

선형자료구조로 FIFO의 특성을 가지고 있다. 먼저 들어간 원소가 가장 먼저 나오는 구조를 가지고 있다. O(n)의 공간복잡도를 가진다.

배열을 이용해 구현할때는 단순 배열보다 원형 구조 (circular queue)를 이용해서 구현한다. 혹은 링크드 리스트를 이용해서 구현할수 도 있는데 이때는 head 와 tail 에 대한 정보를 기록해야 한다.

• 조회 : 가장 끝에 있는 원소를 조회할때는 O(1).
• 삽입 : 링크드 리스트를 이용한 구현해서는 O(1). 동적 배열을 이용할때는 amoritezd\ O(1)이다. 원형 배열을 이용할때는 O(1).
• 삭제 : 모두 O(1).

스택과 큐 모두 배열을 이용하거나 링크드 리스트를 이용해 구현가능한데, 배열을 사용하는 경우에는 Dynamic array의 팽창을 고려해야하기 때문에 최악의 경우에는 느리지만, 전반적인 성능이 좋다. 반대로 링크드 리스트를 이용한 구현에서는 일관된 성능(O(1))을 보여주지만, 메모리 할당에 들어가는 추가적인 비용 때문에 런타임 성능이 낮을 수 있다.

활용

• Queue Usage : 스케쥴링,키보드 버퍼 → 두 개 모두 데이터 혹은 요청이 입력된 시간 순서대로 처리해야할 필요가 있을 경우에 사용한다.

문제들

• 두 개의 스택으로 큐를 구현하기
  1. in 에 A,B,C를 차례로 push. 그러면 in 에는 [A,B,C] 의 순서대로 데이터가 쌓일 것이다.
  2. 그 후 in 의 데이터를 각각 pop하면 C,B,A의 순서대로 나올것이다. 그 후 out 으로 push해보자. out : [C,B,A]
  3. 이후 out 의 원소들을 순서대로 pop하면 출력은 A,B,C가 나오고 out: []
• 생각보다 엄청 간단하다. 두 개의 스택을 각각 in과 out으로 구분하고, A,B,C 세개의 데이터가 입력으로 주어진다고 해보자. 출력은 A,B,C가 나와야 한다.
• 스택에서 min을 O(1)에 작동하도록 하기삽입
  1. 만약 스택이 비어있다면 x 를 삽입할때, minEle=x 로 할당한다.
  2. 그렇지 않다면, x 와 minEle 의 대소를 비교해야하는데 두가지 경우가 존재한다.
     1. x가 minEle 보다 크거나 같다면, 그냥 삽입한다.
     2. minEle 보다 작다면, 2x-minEle 를 스택에 삽입하고, minEle 를 x 로 초기화해준다.
     삭제
  3. y 가 min 보다 크거나 같으면, y 를 그냥 삭제한다. 여전히 최소값은 minEle 다. 그리고 그 값은 스택이 아닌 minELe 에 있다고 보는것이 맞다.
  4. y 가 minEle 보다 작을 경우에, minEle 를 2*minEle-y 로 변경해준다.minEle 보다 작은 원소가 삽입될때 우리는 2x-minEle 를 삽입하는데, 언제나 그것은 x 보다는 작다는 것이다.
  5. 원리
• 일단 최소 요소를 기록하는 minEle 변수를 stack 내부에 구현한다. 그 후 아래와 같은 사고방식대로 접근한다.

Array

논리적 저장순서와 물리적 저장순서가 일치한다. 다시 말해서 a[2] 와 다음에 오는 a[3] 는 물리적으로 연결되어 있다.
하지만, 하나의 Array의 크기가 너무 커 하나의 page(혹은 frame) 안에 다 못들어오는 경우에는 virtual adress는 연속적으로 이어져있지만, physical adress에서도 그렇다는 보장은 없다.

💡 하지만 physical adress와 virtual address에 관한 문제는 OS가 처리할 일이고 프로그래머에게 보이지 않는 추상계층이기에 우리가 깊게 생각할 필요는 없다고 생각한다.

또, 한번 사이즈가 정해지면 변할 수 없다. 이를 해결하는 방법이 Dynamic Array다.

• 조회 : 인덱스를 기반으로 한 접근이 가능하다. 인덱스를 알고 있다면 O(1)의 시간 내에 접근이 가능한데 , 이것을 Random Access라고 한다.
• 삽입 : Array의 특정 위치에 삽입을 할때는 원소를 넣고 끝나는 것이 아니라, 기존의 원소들을 shift 해주는 비용이 생기기 때문에 O(n)의 비용이 든다.
• 삭제 : 삽입과 마찬가지로 shift의 비용 때문에 O(n)이 소요된다. 만약 shift를 해주지 않는다면 삭제를 한 곳에 빈 공간이 생기게 될것이고, contiguous한 Array의 특성이 깨진다.

ArrayList

Java 기준으로 primitive만 저장 할 수 있는 Array와는 다르게 Object도 가능하다. ArrayList에 add를 사용하여 primitive한 데이터를 집어넣을때는 Auto-boxing이 사용된다. 또 제네릭이 사용 가능하다.

하지만 가장 큰 차이점은 ArrayList는 Dynamic Array라는 것이다. ArrayList는 내부적으로 Array와 사이즈 정보를 가지고 있다.

Array의 초기 사이즈가 고정되어 있고 늘어나지 않는것에 비해서, ArrayList는 add를 이용해서 원소를 삽입하다가 원소가 가득차게 되면, 내부적인 Array의 크기를 두배 혹은 1.5배 정도로 늘여서 기존의 원소들을 다 옮기게 된다.

이 과정에서의 시간 복잡도를 고민해보면, 기존 원소의 개수가 0개이고 사이즈가 n개라고 해보자.
이때 n번의 add를 할때까지 내부 Array는 가득차지 않고 각각의 삽입연산의 시간복잡도는 O(1)이다.

하지만 한번 더 add를 한다면 내부 Array를 두배로 늘리고 , 기존의 n개의 원소들을 모두 옮겨야 하니 O(n)의 시간이 소요된다.
n+1번의 add에 걸리는 시간복잡도가 O(1)*n+O(n)이니, 평균적인 시간 복잡도는 (O(1)*n+O(n))/(n+1)=O(1)이 되는 것이다.

이것을 분할 상환(Amortized Analysis)라고 한다.

LinkedList

LinkedList는 불연속적인 데이터들의 집합이다. LinkedList는 Node라고 불리는 내부구조들의 chain으로 구성되어 있는데 구조는 아래와 같다.

struct Node {
    Node* next;
    int val;
}

이처럼 Node는 원소와 그 다음 Node를 가리키는 포인터로 구성된다. 각각의 원소들은 오직 자기 다음에 오는 Node의 정보만을 가리키고 있는 것이다.(Singly Linked List 기준). 물론 next 라는 포인터를 하나 더 유지하는 메모리 사용량도 무시할 순 없다.

이것을 이용하여 삽입과 삭제를 O(1)만에 할 수 있다. 삽입을 할때는 단순히 next 만 교체하면 되고, 삭제 역시 마찬가지다.

• 조회 : k번째 원소를 찾기 위해서는 O(k)만큼의 시간이 소요된다.
• 삽입 : 동작 자체만으로는 O(1)이 걸리지만, 원하는 위치를 찾기 위해 LinkedList를 순회해야 하기 때문에 평균적으로 O(n)이 소요된다. 단, 맨 앞에 삽입하는 경우는 O(1)이 소요된다.
• 삭제 : 삽입과 동일. 맨 앞 삭제는 O(1), 맨 뒤 삭제는 tail 에 대한 정보가 있어도 O(n)이 걸리는데 그 이유는 마지막 원소를 가리키는 직전 원소를 찾기 위해 O(n)의 시간이 걸리기 때문이다.

그럼에도 LinkedList가 중요한 이유는 Tree 구조를 이해할때 필수적이기 때문이다.

Doubly Linked List

앞서 살펴본 Linked List는 일반적으로 Singly Linked List를 지칭하는 말이다. Singly Linked List는 아래처럼 다음 원소를 가리키는 next 포인터 하나만을 가지고 있다.

struct Node {
    Node* next;
    int val;
}

이에 반해서 Doubly Linked List는 next 포인터와 그 직전 원소를 가리키는 prev 포인터 역시 가지고 있는 아래와 같은 구조를 띈다.

struct Node {
    Node* next;
    Node* prev;
    int val;
}

또 일반 Singly Linked List와는 다르게 헤드 역시 Node로 이루어져 있다.

• 삽입 : new_node를 삽입하는 과정인데 살펴볼 필요가 있다.

  

  1. new_node의 prev가 before을 가리키게 한다.

  2. new_node의 next가 before의 next를 가리키게 한다.

  3. before의 next의 prev가 new_node를 가리키게 한다.

  4. before의 next가 new_node를 가리키게 한다.

     이 과정에서 순서에 유의해야 하는데, 1번은 언제 일어나도 상관이 없다.
     하지만 2번,3번의 경우 4번보다 먼저 일어나야 하는데, 그렇지 않으면 before의 next가 가리키는 node를 접근 할 방법이 없어지기 때문이다. 또 당연히 첫 순서로 실행되어서는 안된다.

• 삭제 : removed node를 삭제하려는 과정이다. removed의 이중 연결을 해제해주고, removed의 next와 prev를 서로 연결시켜준다.

  

  1. removed의 prev가 removed의 next를 가리키게 한다.

  2. removed의 next가 removed의 prev를 가리키게 한다.

     두 연산은 순서를 바꿔도 상관이 없다.

• 조회 : Doubly Linked List에는 prev 포인터가 있기 때문에, 최악의 경우 O(n)이 소모되었던 Singly Linked List와는 다르게 O(n/2)의 시간 안에 찾을 수 있다. 찾으려는 원소의 인덱스의 범위에 따라 end에서 prev 포인터를 이용해서 돌아가거나, head에서 next 포인터를 이용해 찾는 방법이다. 또, 직전 원소를 찾는 before도 쉽게 구현 할 수 있다.

이런 장점을 이용해서 연속적인 탐색과 접근에 유리하지만 , 구현이 상대적으로 복잡하고 prev 포인터를 유지해야 하기 때문에 메모리 사용량이 2배 정도 증가한다.

하지만 사용성때문에 플레이리스트, 되돌리기와 같은 기능에 사용되는 자료구조다.

Array vs LinkedList

일반론적인 얘기에서 조회는 Random Access를 지원하는 Array가 O(1)의 시간복잡도를 가지고 있어서 LinkedList보다는 빠르다.

삽입과 삭제는 모두 LinkedList가 빠르다고 하지만 이유에 대해서 조금 더 면밀하게 살펴볼 필요가 있다.

빠르다 라고 하는 것은 삽입과 삭제 그 자체에 주목하는 부분이다.
만약 바꿔야 할(삽입 혹은 삭제) 위치를 정확히 아는 상태에서는 Array보다 LinkedList가 항상 빠르다. 단순히 next 포인터만 변경해주면 되기 때문이다.

평균적인 경우에서는 Linkedlist는 O(n/2)개의 원소들을 살펴보아야 하고, Array도 동일한 원소의 개수들을 shift 해줘야하니 비슷하다.

그렇기 때문에 Usage에 따라 두 자료구조를 적절히 아래와 같이 선택해야 한다.

• 삽입과 삭제가 빈번하게 일어나는 경우 → LinkedList
• 데이터에 대한 접근(Access)가 빈번하게 일어나는 경우 → Array

Cache

또 한가지 더 깊게 생각해보자면, 캐싱과 연관이 있다. 정확히 말하면 Spatial Locality.

CPU가 일을 처리할때는 메모리에서 필요한 데이터를 로드하고, 일부를 캐싱한다. 그 캐시 안에 들어있는 요소들을 레지스터로 가져와서 일을 처리하는데, 이 과정에서 차이가 발생한다.

LinkedList는 데이터들의 주솟값들이 서로 연속적이지 않기 때문에, loop를 돌때 (Iterator든 뭐든) 매번 다음 메모리 주소를 찾아야 하고 , CPU가 메모리에 계속적으로 접근해서 로드하는 과정이 생길 수 있다.

불필요한 오버헤드가 생기는 것이다.

반대로 배열은 연결된 데이터 구조를 가지기 때문에, 특정 영역에 존재하는 데이터들을 한번에 로드해와서 bulk들을 캐싱한다.
그렇기에 loop를 돌때도 Array가 매우 크지 않으면 이미 캐시되어 있는 리소스들을 사용할 수 있게 되고 LinkedList와 비교했을 때 상대적으로 적은 메모리 접근이 일어나니 더 빠르다.

Hash Table은 내부적으로 배열을 사용하여 조회,삽입,삭제 모두 O(1)안에 수행하기 위한 특별한 자료구조다. 배열의 인덱스를 유일하게(혹은 그에 가깝게) 지정하기 위해서 데이터와 연관된 고유한 숫자를 만들어낸 후 그것을 인덱스로 사용한다.

또 일반적으로 순서를 보장하지 않기 때문에, 순서, 관계가 있는 목적에는 적합하지 않다.

Hash funciton

데이터에 연관된 고유한 값을 만들기 위해서 해시 함수를 사용한다. 이 해시 함수를 통해서 나온 결과값을 해시 값(혹은 해쉬 코드,해쉬)라고 하고 이것을 이용해 데이터에 대한 접근 연산을 수행한다.

가장 많이 쓰이는 해시 함수는 나머지 연산(modulo)를 이용한다. 키 k 를 어떤 정해진 수 D 로 나눈 나머지를 k 를 저장하는 버킷의 인덱스로 사용하는 것이다.
→ h(k)=k

일반적으로 D 는 적절히 큰 소수(prime number)를 사용하는데 이유는 다음과 같다.

만약 D를 소수가 아닌 값이라 하면, D의 모든 약수는 자신의 배수가 곧 키값이 된다. 해시충돌이 많이 일어나는것이다.

만약 이 해시 함수가 엄밀하지 못해서 여러개의 객체가 서로 같은 값을 가지게 된다면 이것을 해시 충돌(hash collision)이라고 한다.

일반적인 경우에서 가능한 키들의 집합을 U라고 하고, 버킷들의 개수를 m이라고 할때 U>>m인 경우가 대부분이므로 충돌은 필연적으로 발생한다. 이것을 해결하기 위해서 버킷의 사이즈를 단순히 키우는것은 좋은 해결책이 아니다. 메모리 사용량에서 치명적이다.

좋은 해시 함수를 고안해도, 여전히 해시 충돌은 불가피하다. 해시충돌이 늘어나게되면 O(1)의 시간복잡도 장점을 잃어버리고 O(n)에 가깝게 되니, 적절한 해결책을 세워야 한다.

Open Addressing

개방주소법(Open Addressing)은 간단히 말해서 해시충돌이 발생하면(계산된 인덱스로 접근한 버킷이 이미 사용중이면) 단순히 다른 인덱스에 데이터를 저장하는 방식이다.

개방주소법 안에서도 여러개로 나뉜다.

• Linear Probing
  • 계산된 해시값에서 해시충돌이 발생한다면, 고정폭만큼 건너뛰어 비어있는 해시에 저장하는 방법이다. 만약 그 자리에도 차있다면, 그 다음 고정폭의 위치를 탐색한다.
  • 이 방법은 단순해서 계산을 하기 쉽지만, 최악의 경우 탐색을 시작한 위치까지 돌아오게 되어 종료할 수 있다. O(n)이 걸리는 것이다.
  • 또 primary clustering이라는 특정 해쉬 값 슬롯 근처에 값들이 뭉치게 되는 문제도 생길 수 있다. x 라는 해쉬 값을 공유하는 객체들이 x+1,x+2,x+3 등으로 모이기 때문이다.
  • 클러스터의 크기가 커질수록, 비슷한 해쉬값들이 적절히 배치되지 못하고 다음을 probing하니 클러스터가 더 빠르게 자라나고*, 이는 성능적으로 이슈를 불러일으킨다.
  • 다만 값들이 클러스터링 되어있기 때문에 cache hit 적인 측면에서는 유리하다. 처음 키에 대해서 접근을 하면 다음 키도 캐쉬에 올라와 있기 때문이다.
• Quadratic Probing
  • Linear Probing과 비슷하게 , 해시충돌이 발생한다면 다음 슬롯을 찾는다. 다른 점은 idx=(hash(key)+i^2) mod m 의 꼴을 취하는 것이다.
  • 이 방법도 primary clustering보다는 덜 하지만 성능에 영향을 주는 secondary clustering 문제를 일으킨다.
  • 초기 hash 포지션이 아닌 좀 더 광범위하게 퍼져있는 것이다.
• Double hashing
  • 이름 그대로 해시 충돌이 생기면, 2차 해시함수를 이용해서 다시 해시를 하는 방법.
  • 값이 퍼지게 되어서 캐쉬의 측면에서는 비효율적이고 연산량이 많이 들지만, 클러스터링에는 큰 영향을 받지 않는다.

장점과 단점

이처럼 개방주소법 내에서도 여러가지 충돌 처리방식이 있다. 일반적으로 개방주소법은 적은 양의 데이터에는 효과를 보이고 메모리 효율도 분리연결법에 비해 상대적으로 좋고, 메모리 할당에 대한 오버헤드도 없는 편이다.

또 일반적으로 연결리스트를 사용하는 분리연결법에 비하여 캐쉬 효율이 좋기 때문에 (특히 Linear Probing) Python에서 hashtable을 구현할때 사용된다.

하지만 데이터의 삭제에서 좋지 않은 퍼포먼스를 보인다.
예를 들어 A,B,C 가 연속적으로 있을때(linear probing) A 를 삭제한다고 해보자. 그럼 NULL,B,C 라고 변경될텐데, 이때 C 에 대해서 조회를 한다면, NULL 을 만나게 된다. 이것을 원래부터 비어있는 공간인지 혹은 삭제되어서 비어있는 공간인지 알 수 없기 때문에 C 를 조회하지 못하고 탐색이 종료된다.
이를 극복하기 위해서 삭제된 공간은 삭제되었음을 표시해주는 DEL 같은 표기자를 사용해 다음 index를 조회할수 있게끔 해야한다.
물론 이러한 DEL 표시자가 늘어난다면, 조회할 데이터가 없어도 계속적인 탐색을 수행해줘야 하니 표시자의 개수에 따라 해시테이블 전체에 대해서 rehashing을 해줘야 한다.

load factor를 l이라고 하였을때 삽입과 조회, 삭제 모두 O(\frac{1}{1-l})의 성능을 보여준다.

Seperate Chaining

분리연결법(Separate Chaining)은 일반적인 상황에서 개방주소법보다는 빠른데, 개방주소법의 경우 load factor가 커질수록 최악의 경우( O(n))의 발생 빈도가 높아지기 때문이다.

분리연결법은 해시충돌이 잘 발생하지 않게끔 하기 위해서 보조 해시 함수를 이용해 최악의 경우로 가는 상황을 줄이려고 한다.

분리연결법에도 두가지 방법이 존재한다.

• Linked List
  • 각각의 버킷들을 연결리스트로 두어 충돌이 발생하면 해당 버킷의 리스트에 추가하는 방식.
  • 단, 연결리스트의 단점을 그대로 가지고 있다. 메모리 주소 상에서 연속적이지 않기 때문에 캐시의 효율이 나쁘고, 아주 적은 데이터가 있을때의 메모리 오버헤드가 있다.(개방주소법과 비교해서)
  • 또 Traverse를 할 때 최악의 경우에는 O(n)의 시간복잡도를 보인다.
• Tree
  • 연결리스트의 단점을 개선하기 위해 나온 것으로 연결리스트가 아닌 Tree 구조를 이용해 데이터를 저장한다.
  • 단, Tree에서도 데이터가 편향되게 들어오면 O(n)의 시간복잡도를 가질 수 있으니 Red-black Tree와 같은 Balanced Binary Tree를 사용함으로써 O(logn)의 연산을 보장시킨다.
  • 하지만 적은 데이터 수에서 RB Tree를 유지하는데 드는 메모리 사용량이 연결리스트보다 크니, 적은 수의 데이터보다는 어느정도 데이터가 들어왔을때 연결리스트에서 트리로 전환한다.
  • Java 8에서부터는 데이터가 8개가 넘어가면 트리로 전환하고, 6개가 되면 다시 연결리스트로 전환한다. 두개의 차이가 2가 나는 이유는 데이터의 잦은 삽입,삭제로 1개단위로 전환하게 되면 오버헤드가 더 크기 때문에 일정 수준을 유지하는것이다.
  • AVL 트리도 균형이진트리인데 사용하지 않는 이유는, 일반적으로 hashtable 같은 경우 데이터의 조회만 intensive하게 일어나지 않기 때문에, AVL 트리를 사용하면 rotation과 같은 balance를 유지하는데 드는 오버헤드가 너무 크다.
  • 이에 반해 RB 트리는 조금 더 느슨하게 균형을 유지함으로써 조회,삽입,삭제에 평균적으로 좋은 퍼포먼스를 보여주기 때문에 hashtable의 내부 자료구조로 사용되는 것이다.

장점과 단점

분리연결법은 load factor에 크게 민감하게 반응하지 않아도 된다. 일반적으로 개방주소법에서 load factor가 커지면 성능이 기하급수적으로 나빠지는것에 비해서
분리연결법은 조금 linear한 나쁜 성능을 보여준다.

또 개방주소법에서는 hash table의 resize가 필연적으로 일어나게 되는데, 이것은 O(m) , (m은 key의 개수)의 시간복잡도를 요구하니 꽤 치명적이다.
하지만 분리연결법에서는 하나의 버킷에 대해 지속적으로 사용하기 때문에 테이블의 확장이 개방주소법보다는 더디게 일어나는 편이다.

다만 일반적으로 개방주소법에서 버킷들의 캐시 효율이 좋은 반면 분리연결법은 링크드리스트나 트리를 이용하기에 캐시의 효율이 좋지 않다.

해시 테이블 자체의 단점

데이터가 pseudo-random 위치에 저장되기 때문에, 데이터를 정렬된 순서로 접근하는 것에 있어서 엄청난 비용이 발생한다. Self-balancing binary tree와 같은 자료구조에서는 O(logn)의 조회를 보장해 조금 느리고 구현이 더 복잡하지만 데이터는 정렬되어 있다.

또 데이터를 loop하면서 traverse하는 능력도 떨어지는데, 데이터가 흩뿌려질(산재된) 확률이 높은 해쉬테이블의 특성상 빈 슬롯도 모조리 체크해가면서 순회해야 하기 때문이다.

일반적으로 해시 테이블은 지역참조성에 취약한데, 해시 테이블의 조회 자체가 버킷들을 건너띄면서 확인하는 방식이기 때문이다. 그렇기에 프로세스가 계속해서 캐시 미스를 발생시키고 이는 오버헤드로 이어진다. 데이터가 적고 type이 간단한(Integer...) 경우에는 배열을 이용한 자료구조가 더 나은 성능을 보일 수 있다.

문제 상황

백준 빵집를 풀때 이상한 점이 확실히 생겼다. 일반적으로 python에서 방문 여부를 확인하기 위해 set과 list중에 하나를 사용한다.
set같은 경우는 잘못된 접근 같은 행동에서 안전한 편이고 대부분의 기능에서 O(1)의 시간이 보장된다고 알고 있기 때문에 set을 이용한 풀이를 종종했다.

List에서는 미숙한 코드로 indexError를 경험할 수 있다.

이 문제는 naive 하게 set을 사용하면 시간초과를 당한다. 처음엔 논리를 잘못 구성해 recursionDepth가 커져서 시간초과가 나는건가 라고 생각했지만 논리에는 문제가 없었다. 그래서 set만을 list로 바꿔주었더니 통과했다.

분명 lookup도 똑같이 O(1)이고 set에서는 add도 O(1)이라고 알고 있는데 왜 차이가 나는 것일까? 이 이해 안되는 상황을 지금부터 알아보자.

메모리 사용량

먼저 간단하게 두 자료구조의 메모리 사용량을 비교해보았다.

아래 코드는 10000개의 행 , 500개의 열을 가진 2차원 board에서 사용되는 방문을 기록하는 일반적인 구현이다.

하나는 List로 하나는 set으로 구현한 뒤 sys.getsizeof(object)를 이용해서 각각의 객체의 메모리 사용량을 체크해보았다.

getsizeof(object [, default]) -> int : Return the size of object in bytes.

R=10000 # ROW
C=500    # COL

a=[[True for _ in range(R)] for _ in range(500)]
sys.getsizeof(a)
>>> 4264

b=set()
for i in range(R):
    for j in range(C):
        b.add((i,j))
sys.getsizeof(b)
>>> 134217944

놀라운 결과다. 같은 기능을 수행하는 서로 다른 자료구조인데 메모리차이가 대략 31,000배 정도의 차이를 보였다.

list는 4264 Byte, set은 134217944 Byte를 사용한다. 대략적으로 두 자료구조는 각각 4KB,134MB을 사용한다는 것이다.

List와 Set의 내부구조

왜 이렇게 차이가 나는 것일까?

list와 set이 내부적으로 데이터를 저장하는 방식에서 차이가 있어서 그렇다. stackoverflow의 한 답변에 따르면

List

List는 그저 원래의 객체들에 대한 참조를 모아놓은것에 불과하다. 만약 1000개의 integer를 만든다고 하면 , 그것들이 만들어지고 list는 오직 그 integer들에 대한 참조만을 담고 있다.

list는 참조들의 collection이고 일종의 주솟값을 가지고 있는것이다. 그렇기에 아래와 같은 코드를 수행해도 여전히 4264 Byte다.

c= [[[1,2,3] for _ in range(10000)] for _ in range(500)]
sys.getsizeof(c)
>>> 4264

list가 세번 중첩되어 있지만 [1,2,3]에 대한 참조만을 가지고 있기 때문에 메모리 사용량이 같은 것이다.

내부적으로는 dynamic array를 사용하고 있다.

Set

반대로 set은 어떨까? Python에서의 set은 내부적으로 key가 dummy value인 dict 를 상당 부분 재사용함으로써 hash table 의 구조를 가지고 있다.

여전히 위의 같은 답변을 참고하자면

반면에, set이나 dictionary는 1000개의 integer들의 hash value를 모두 계산해야하고 그에 따라 메모리 사용량이 증가한다.

예를 들어 set이나 dict나 가장 작은 크기의 기본값은 8이다.(즉, 오직 3개의 값만 저장한다해도 python은 8개를 지정해준다.) resize를 할때, buckets들의 개수는 요소가 50,000개가 되기 전까지는 4배씩 증가한다. 그런 다음에는 2배씩 증가한다.

Set에서의 resize

과연 정말 그렇게 작동할까? resize는 set에 일반적으로 값을 추가할 때 호출되기 때문에 add를 할때 호출되는 CPython의 set의 set_add_entry의 구현 코드를 직접 보자.

/* CPython */
/* https://github.com/python/cpython/blob/main/Objects/setobject.c */ 
static int
set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
...
...
  found_unused:
    so->fill++;
    so->used++;
    entry->key = key;
    entry->hash = hash;
    if ((size_t)so->fill*5 < mask*3)
        return 0;
    return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

...
...

위의 코드에서 load factor가 일정 부분(아래서 다시 언급할 것이다.)을 넘어갈때를 보자.
(if ((size_t)so->fill*5 < mask*3) 의 아랫부분이다.)
so(set object)의 크기에 따라 set_table_resize의 인자를 다르게 주고 있음이 보인다.

** Load factor ** : Hash table 전체에서 얼마나 원소가 차 있는지를 나타내는 수치.
m개의 bucket의 Hash tablen에 n개의 원소가 저장되어 있다면 load_factor = n/m 이다

so->used가 50,000이 넘어가면 현재 used의 2배를, 그렇지 않으면 4배만큼 큰 값으로 resize를 하는 것이다.

여기서 mask는 hash_table의 크기보다 1 작다. modulo의 역할처럼 hash에 쓰이는데 AND 연산을 이용한다.

resize의 내부동작 방식

이제 set_table_resize가 내부적으로 어떻게 동작하는지를 살펴보자.

요약하자면 set_table_resize는 hash table의 구조를 가지는 setentry 구조체를 기존 oldtable의 2배 혹은 4배의 크기인 newtable이라는 이름으로 동적할당 받은 후 oldtable의 모든 entry들을 newtable에 넣어주는 과정을 거친다.

typedef struct {
    PyObject *key;
    Py_hash_t hash;             /* Cached hash code of the key */
} setentry;

이해가 안가도 당황하지 마세요... 아래서 차근차근 설명해줄거에요...😅

단계별로 살펴보자. 아래 코드부터다.

/* CPython */
/* https://github.com/python/cpython/blob/main/Objects/setobject.c */ 
static int
set_table_resize(PySetObject *so, Py_ssize_t minused)
{
    setentry *oldtable, *newtable, *entry;
    ...
    /* Find the smallest table size > minused. */
    /* XXX speed-up with intrinsics */
    size_t newsize = PySet_MINSIZE;
    while (newsize <= (size_t)minused) {
        newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
    }

일단, newtable의 크기를 정해야 한다. set_table_resize의 두번째 인자만큼
newsize를 left shift를 사용해 Pyset_MINSIZE에서 minused만큼 증가시킨다.
(PySet_MINSIZE는 위에 언급한 것처럼 8이다.)

/* CPython */
/* https://github.com/python/cpython/blob/main/Objects/setobject.c */
    ...
    /* Get space for a new table. */

    if (newsize == PySet_MINSIZE) {
        ...
        /* A large table is shrinking, or we can't get any smaller. */
        ...
        ...
        }
    }
    else {
        newtable = PyMem_NEW(setentry, newsize);
        if (newtable == NULL) {
            PyErr_NoMemory();
            return -1;
        }
    }

newsize가 PySet_MINSIZE(8)가 아닐때, PyMem_New(type,n)를 통해서 위에서 계산된 newsize의 크기만큼 setentry의 객체를 생성하는 것이다.

좀 더 엄밀하게 얘기하면 PyMem_new(type,n)는 PyMem_Malloc(n)를 이용해서 (n)*sizeof(type) Byte만큼의 메모리를 동적할당(malloc) 하는 macro다. (cpython/include/pymem.h 참조)

이제 거의 다 왔다. oldtable들의 값들을 newtable에 옮겨주기만 하면 된다.

/* CPython */
/* https://github.com/python/cpython/blob/main/Objects/setobject.c */
    ...
    so->mask = newsize - 1;
    so->table = newtable;
    ...

hashing에 필요한 mask 값을 갱신해주고 (modulo와 비슷한 역할을 한다. 다만 AND 연산자를 사용할뿐이다.)

/* CPython */
/* https://github.com/python/cpython/blob/main/Objects/setobject.c */
    /* Copy the data over; this is refcount-neutral for active entries;
       dummy entries aren't copied over, of course */
    newmask = (size_t)so->mask;
    if (so->fill == so->used) {
        for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
            if (entry->key != NULL) {
                set_insert_clean(newtable, newmask, entry->key, entry->hash);
            }
        }
    } else {
        so->fill = so->used;
        for (entry = oldtable; entry <= oldtable + oldmask; entry++) {
            if (entry->key != NULL && entry->key != dummy) {
                set_insert_clean(newtable, newmask, entry->key, entry->hash);
            }
        }
    }

newmask 를 이용해서 oldtable안의 기존의 값들을 newtable에 set_insert_clean을 이용해 넣어준다.

** 이런 복잡한 과정들을 거쳐서 set에서 resize가 진행되는 것이다. **

그래서 얼마나 걸리는데?

b=set()
for i in range(R):
    for j in range(C):
        b.add((i,j))

위 문제에선 set이 최대 몇 번 resize를 할까? resize 전 후로 b의 메모리 크기가 달라지니 아래와 같은 코드로 확인 할 수 있다.

resize_count=0
prev=cur_size=sys.getsizeof(b)

for i in range(R):
    for j in range(C):
        b.add((i,j))
        if prev!=sys.getsizeof(b):
            prev=cur_size
            resize_count+=1

print(resize_count)
>>>13

13번 resize를 한다. 그럼 그때마다 내부 구조인 hash table의 bucket은 언제 , 그리고 얼만큼 늘어날까?

Set의 load factor

아래와 같은 코드로 확인 할 수 있다.

element_count=0
prev=cur_size=sys.getsizeof(b)

for i in range(R):
    for j in range(C):
        s=time.time()
        b.add((i,j))
        element_count+=1
        if prev!=sys.getsizeof(b):
            cur_size=sys.getsizeof(b)
            print("resize at "+str(element_count))
            prev=cur_size

>>>
resize at 5
resize at 19
resize at 77
resize at 307
resize at 1229
resize at 4915
resize at 19661
resize at 78643
resize at 157286
resize at 314573
resize at 629145
resize at 1258291
resize at 2516582

1. 처음 bucket의 크기는 8이니 5/8만큼 찼을때 늘어난다.
2. 19/32만큼 찼을때 늘어난다.
3. 77/128만큼 찼을때 늘어난다.
   ...

이걸 바탕으로 우린 위에서 언급한 load factor를 계산 할 수 있는데, 미리 계산해왔다. 😅
대략 0.6에 근접하면 resize가 호출된다.

** Python에서, 최소한 CPython의 set의 load factor는 0.6에 근접하는것 같다.**

직접 계산 해보면 hash table의 bucket의 크기는 8->32->128->...->32768->131072->262144->...->4194304 순으로 늘어난다. ** 정말 50,000을 넘어서부터는 4배가 아니라 2배씩 늘고 있다.**

아까 위에서 언급한 resize를 할지 말지 결정하는 부분을 다시 한번 보자.

    if ( (size_t)so->fill*5 < mask*3)
        return 0;
    return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

mask는 size보다 1 작은 값이니 bucket의 size-1로 바꿔쓸 수 있다.. 식을 보기 좋게 살짝 정리해보자.

    if ( (so->fill) < (size-1) * 0.6 )
        return 0;
    return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

해석해보자. size-1개의 bucket들 중에서

• 60%보다 덜 차있다면, resize를 진행하지 않고 add 함수를 종료한다.
• 60%보다 더 차있다면 resize를 진행한다.

** 최소한 CPython의 set의 load factor는 0.6에 아주 근사하다고 말할 수 있게 된 것이다.**

결론

우리는 긴 과정을 거쳐서 set이 add를 할 때 사실은 resize를 할 때가 있기 때문에 Overhead를 동반한다는 것을 알게 되었다.

그렇기에 아주 naive하게 set의 add가 O(1)이라는 건 엄밀하지 않다. add하는 과정에서 resize를 호출할때가 있고 , 그 과정에서 현재 element의 약 60% 개의 element들을 옮겨야 하니 , amortized O(1)이다.

우리가 이 상황을 왜 분석했을까? BFS 탐색 문제를 푸는데 시간초과가 나서이다.

그 원인은 add를 반복할때 resize에 있다는 것을 확실하게 알 수 있다.

그럼 어떻게?

List도 index 기반 접근을 하기 때문에 lookup에 대한 시간이 O(1)이다. 또 List를 처음 선언할때 메모리를 할당해주기 때문에, append를 쓰지 않는다면, resize가 필요하지 않다.

List도 내부 구조는 dynamic array이기 때문에 resize가 발생할 수 있다. append도 amortized O(1)인 이유가 있다.

정말 특수한 상황을 제외하고는 List를 사용하는게 의문의 시간 초과 오류를 보지 않는 방법이다.

경험상 특수한 상황은 탐색에서 조건적으로 매우 크고 sparse한 범위의 방문을 할 때다.

모든 코드는 Python 3.8.10 [GCC 9.4.0] on linux 버전을 사용했습니다

참고자료

CPython Source Code
Python 메모리 관리 공식문서
Memory consumption of a list and set in Python
Load Factor and Rehashing
Time complexity for adding elements to list vs set in python

내부적으로 배열을 사용하여 조회,삽입,삭제 모두 O(1)안에 수행하기 위한 특별한 자료구조다. 배열의 인덱스를 유일하게(혹은 그에 가깝게) 지정하기 위해서 데이터와 연관된 고유한 숫자를 만들어낸 후 그것을 인덱스로 사용한다.

또 일반적으로 순서를 보장하지 않기 때문에, 순서, 관계가 있는 목적에는 적합하지 않다.

Hash function

데이터에 연관된 고유한 값을 만들기 위해서 해시 함수를 사용한다. 이 해시 함수를 통해서 나온 결과값을 해시 값(혹은 해쉬 코드,해쉬)라고 하고 이것을 이용해 데이터에 대한 접근 연산을 수행한다.

가장 많이 쓰이는 해시 함수는 나머지 연산(modulo)를 이용한다. 키 k 를 어떤 정해진 수 D 로 나눈 나머지를 k 를 저장하는 버킷의 인덱스로 사용하는 것이다.
→ h(k)=k

일반적으로 D 는 적절히 큰 소수(prime number)를 사용하는데 이유는 다음과 같다.

만약 D를 소수가 아닌 값이라 하면, D의 모든 약수는 자신의 배수가 곧 키값이 된다. 해시충돌이 많이 일어나는것이다.

만약 이 해시 함수가 엄밀하지 못해서 여러개의 객체가 서로 같은 값을 가지게 된다면 이것을 해시 충돌(hash collision)이라고 한다.

일반적인 경우에서 가능한 키들의 집합을 U라고 하고, 버킷들의 개수를 m이라고 할때 U>>m인 경우가 대부분이므로 충돌은 필연적으로 발생한다. 이것을 해결하기 위해서 버킷의 사이즈를 단순히 키우는것은 좋은 해결책이 아니다. 메모리 사용량에서 치명적이다.

좋은 해시 함수를 고안해도, 여전히 해시 충돌은 불가피하다. 해시충돌이 늘어나게되면 O(1)의 시간복잡도 장점을 잃어버리고 O(n)에 가깝게 되니, 적절한 해결책을 세워야 한다.

Open Addressing

개방주소법(Open Addressing)은 간단히 말해서 해시충돌이 발생하면(계산된 인덱스로 접근한 버킷이 이미 사용중이면) 단순히 다른 인덱스에 데이터를 저장하는 방식이다.

개방주소법 안에서도 여러개로 나뉜다.

• Linear Probing
  • 계산된 해시값에서 해시충돌이 발생한다면, 고정폭만큼 건너뛰어 비어있는 해시에 저장하는 방법이다. 만약 그 자리에도 차있다면, 그 다음 고정폭의 위치를 탐색한다.
  • 이 방법은 단순해서 계산을 하기 쉽지만, 최악의 경우 탐색을 시작한 위치까지 돌아오게 되어 종료할 수 있다. O(n)이 걸리는 것이다.
  • 또 primary clustering이라는 특정 해쉬 값 슬롯 근처에 값들이 뭉치게 되는 문제도 생길 수 있다. x 라는 해쉬 값을 공유하는 객체들이 x+1,x+2,x+3 등으로 모이기 때문이다.
  • 클러스터의 크기가 커질수록, 비슷한 해쉬값들이 적절히 배치되지 못하고 다음을 probing하니 클러스터가 더 빠르게 자라나고*, 이는 성능적으로 이슈를 불러일으킨다.
  • 다만 값들이 클러스터링 되어있기 때문에 cache hit 적인 측면에서는 유리하다. 처음 키에 대해서 접근을 하면 다음 키도 캐쉬에 올라와 있기 때문이다.
• Quadratic Probing
  • Linear Probing과 비슷하게 , 해시충돌이 발생한다면 다음 슬롯을 찾는다. 다른 점은 idx=(hash(key)+i^2) mod m 의 꼴을 취하는 것이다.
  • 이 방법도 primary clustering보다는 덜 하지만 성능에 영향을 주는 secondary clustering 문제를 일으킨다.
  • 초기 hash 포지션이 아닌 좀 더 광범위하게 퍼져있는 것이다.
• Double hashing
  • 이름 그대로 해시 충돌이 생기면, 2차 해시함수를 이용해서 다시 해시를 하는 방법.
  • 값이 퍼지게 되어서 캐쉬의 측면에서는 비효율적이고 연산량이 많이 들지만, 클러스터링에는 큰 영향을 받지 않는다.

장점과 단점

이처럼 개방주소법 내에서도 여러가지 충돌 처리방식이 있다. 일반적으로 개방주소법은 적은 양의 데이터에는 효과를 보이고 메모리 효율도 분리연결법에 비해 상대적으로 좋고, 메모리 할당에 대한 오버헤드도 없는 편이다.

또 일반적으로 연결리스트를 사용하는 분리연결법에 비하여 캐쉬 효율이 좋기 때문에 (특히 Linear Probing) Python에서 hashtable을 구현할때 사용된다.

하지만 데이터의 삭제에서 좋지 않은 퍼포먼스를 보인다.
예를 들어 A,B,C 가 연속적으로 있을때(linear probing) A 를 삭제한다고 해보자. 그럼 NULL,B,C 라고 변경될텐데, 이때 C 에 대해서 조회를 한다면, NULL 을 만나게 된다. 이것을 원래부터 비어있는 공간인지 혹은 삭제되어서 비어있는 공간인지 알 수 없기 때문에 C 를 조회하지 못하고 탐색이 종료된다.
이를 극복하기 위해서 삭제된 공간은 삭제되었음을 표시해주는 DEL 같은 표기자를 사용해 다음 index를 조회할수 있게끔 해야한다.
물론 이러한 DEL 표시자가 늘어난다면, 조회할 데이터가 없어도 계속적인 탐색을 수행해줘야 하니 표시자의 개수에 따라 해시테이블 전체에 대해서 rehashing을 해줘야 한다.

load factor를 l이라고 하였을때 삽입과 조회, 삭제 모두 O(\frac{1}{1-l})의 성능을 보여준다.

Seperate Chaining

분리연결법(Separate Chaining)은 일반적인 상황에서 개방주소법보다는 빠른데, 개방주소법의 경우 load factor가 커질수록 최악의 경우( O(n))의 발생 빈도가 높아지기 때문이다.

분리연결법은 해시충돌이 잘 발생하지 않게끔 하기 위해서 보조 해시 함수를 이용해 최악의 경우로 가는 상황을 줄이려고 한다.

분리연결법에도 두가지 방법이 존재한다.

• Linked List
  • 각각의 버킷들을 연결리스트로 두어 충돌이 발생하면 해당 버킷의 리스트에 추가하는 방식.
  • 단, 연결리스트의 단점을 그대로 가지고 있다. 메모리 주소 상에서 연속적이지 않기 때문에 캐시의 효율이 나쁘고, 아주 적은 데이터가 있을때의 메모리 오버헤드가 있다.(개방주소법과 비교해서)
  • 또 Traverse를 할 때 최악의 경우에는 O(n)의 시간복잡도를 보인다.
• Tree
  • 연결리스트의 단점을 개선하기 위해 나온 것으로 연결리스트가 아닌 Tree 구조를 이용해 데이터를 저장한다.
  • 단, Tree에서도 데이터가 편향되게 들어오면 O(n)의 시간복잡도를 가질 수 있으니 Red-black Tree와 같은 Balanced Binary Tree를 사용함으로써 O(logn)의 연산을 보장시킨다.
  • 하지만 적은 데이터 수에서 RB Tree를 유지하는데 드는 메모리 사용량이 연결리스트보다 크니, 적은 수의 데이터보다는 어느정도 데이터가 들어왔을때 연결리스트에서 트리로 전환한다.
  • Java 8에서부터는 데이터가 8개가 넘어가면 트리로 전환하고, 6개가 되면 다시 연결리스트로 전환한다. 두개의 차이가 2가 나는 이유는 데이터의 잦은 삽입,삭제로 1개단위로 전환하게 되면 오버헤드가 더 크기 때문에 일정 수준을 유지하는것이다.
  • AVL 트리도 균형이진트리인데 사용하지 않는 이유는, 일반적으로 hashtable 같은 경우 데이터의 조회만 intensive하게 일어나지 않기 때문에, AVL 트리를 사용하면 rotation과 같은 balance를 유지하는데 드는 오버헤드가 너무 크다.
  • 이에 반해 RB 트리는 조금 더 느슨하게 균형을 유지함으로써 조회,삽입,삭제에 평균적으로 좋은 퍼포먼스를 보여주기 때문에 hashtable의 내부 자료구조로 사용되는 것이다.

장점과 단점

분리연결법은 load factor에 크게 민감하게 반응하지 않아도 된다. 일반적으로 개방주소법에서 load factor가 커지면 성능이 기하급수적으로 나빠지는것에 비해서
분리연결법은 조금 linear한 나쁜 성능을 보여준다.

또 개방주소법에서는 hash table의 resize가 필연적으로 일어나게 되는데, 이것은 O(m) , (m은 key의 개수)의 시간복잡도를 요구하니 꽤 치명적이다.
하지만 분리연결법에서는 하나의 버킷에 대해 지속적으로 사용하기 때문에 테이블의 확장이 개방주소법보다는 더디게 일어나는 편이다.

다만 일반적으로 개방주소법에서 버킷들의 캐시 효율이 좋은 반면 분리연결법은 링크드리스트나 트리를 이용하기에 캐시의 효율이 좋지 않다.

해시 테이블 자체의 단점

데이터가 pseudo-random 위치에 저장되기 때문에, 데이터를 정렬된 순서로 접근하는 것에 있어서 엄청난 비용이 발생한다. Self-balancing binary tree와 같은 자료구조에서는 O(logn)의 조회를 보장해 조금 느리고 구현이 더 복잡하지만 데이터는 정렬되어 있다.

또 데이터를 loop하면서 traverse하는 능력도 떨어지는데, 데이터가 흩뿌려질(산재된) 확률이 높은 해쉬테이블의 특성상 빈 슬롯도 모조리 체크해가면서 순회해야 하기 때문이다.

일반적으로 해시 테이블은 지역참조성에 취약한데, 해시 테이블의 조회 자체가 버킷들을 건너띄면서 확인하는 방식이기 때문이다. 그렇기에 프로세스가 계속해서 캐시 미스를 발생시키고 이는 오버헤드로 이어진다. 데이터가 적고 type이 간단한(Integer...) 경우에는 배열을 이용한 자료구조가 더 나은 성능을 보일 수 있다.