자료구조
글 17개
VitalRouter 의 구독과 해제는 목록을 처음부터 찾는다
씬을 나갈 때 구독자 4,000명을 하나씩 Dispose 하면 IL2CPP 에서 3 ms 가 넘습니다. VitalRouter 는 빈 칸도 해제할 구독자도 배열 처음부터 찾기 때문입니다. 함께 사라지는 구독은 라우터째 버리면 탐색이 없습니다.
벽은 막고 문은 통과시킨다
앞의 다섯 편은 물체를 추렸습니다. 포털 컬링은 보이는 영역 자체를 잘라 나갑니다. 문을 지날 때마다 시야가 얼마나 좁아지는지, BSP(binary space partitioning)가 왜 축에 갇히지 않는지 실측으로 봅니다.
움직이는 것들에는 트리를 짓지 않는다
앞의 네 편은 구조를 지어 두고 질의를 던졌습니다. 스윕 앤 프룬(sweep and prune)은 한 축으로 줄만 세워 둡니다. 프레임마다 순서가 거의 안 바뀐다는 성질 하나로 어디까지 갈 수 있는지, 대신 무엇을 내주는지 실측으로 봅니다.
공간이 아니라 물체를 나눈다
격자도 쿼드트리도 KD 트리도 공간을 잘라 왔습니다. BVH(bounding volume hierarchy)는 물체를 둘로 갈라 각 무리를 상자로 감쌉니다. 크기가 있는 물체가 왜 여기에만 온전히 담기는지, 상자끼리 겹쳐도 괜찮은 이유를 실측으로 봅니다.
가운데가 아니라 중앙값에서 자른다
쿼드트리는 공간의 한가운데를 자르고 KD 트리(k-d tree)는 점들의 중앙값을 자릅니다. 트리 모양이 분포에서 풀려나는 대신 무엇을 내주는지, 가지치기가 실제로 몇 개를 걷어 내는지 실측으로 봅니다.
빈 곳은 큰 칸 하나로 남긴다
밀도가 고르지 않으면 칸 크기를 하나로 정할 수 없습니다. 붐비는 칸만 넷으로 쪼개는 쿼드트리(quadtree)의 동작과, 격자보다 나은 자리와 나쁜 자리를 실측으로 갈라 봅니다.
좌표를 칸으로, 칸을 배열로
균일 격자를 실제로 만들 때 막히는 자리들입니다. 음수 좌표에서 칸 번호가 어긋나는 이유, 맵 밖을 다루는 공간 해시(spatial hash), 같은 쌍을 두 번 보지 않는 법, 칸마다 리스트를 두지 않고 배열 세 개로 짓는 법.
가장 작은 것만 꺼낼 건데 전부 정렬할 필요는 없다
우선순위 큐(priority queue)와 그것을 떠받치는 이진 힙(binary heap) 이야기입니다. 트리처럼 보이지만 배열 하나이고, 넣기와 꺼내기가 왜 둘 다 log n 인지, 유니티에서는 무엇을 쓸 수 있는지 봅니다.
타일맵도 스킬 트리도 결국 같은 모양이다
점과 선으로 보면 길찾기, 스킬 선행 조건, 던전 방 연결이 한 문제가 됩니다. 그래프를 인접 행렬과 인접 리스트 중 무엇으로 저장할지, 격자는 왜 저장하지 않아도 되는지 봅니다.
LinkedList 는 손을 잡고 선 줄이다
칸이 붙어 있지 않고 각자 다음 사람의 위치를 들고 있습니다. 끼워 넣기는 싸지고 번호로 찾기는 비싸집니다.
넣고 빼는 순서가 규칙이다
어느 것을 꺼낼지 우리가 고르지 않습니다. 나중에 넣은 것부터 나오거나, 먼저 넣은 것부터 나옵니다.
해시 테이블은 자리를 계산해서 정한다
Dictionary 와 HashSet 이 곧장 찾는 이유입니다. 해시 코드를 버킷 개수로 나눈 나머지가 자리이고, 그 버킷 개수는 언제나 소수입니다. 겹치면 어떻게 되고 줄은 어디까지 길어지는지까지 봅니다.
HashSet 은 중복을 받지 않는다
이미 있는지 확인하는 일을 List 로 하면 전부 훑습니다. Dictionary 에서 값을 떼고 키만 남긴 것이 HashSet 입니다.
Dictionary 는 번호 대신 이름으로 찾는다
이름을 숫자로 바꿔서 자리를 계산합니다. 그래서 몇 개가 들어 있든 찾는 시간이 거의 같습니다.
List 는 칸이 모자라면 알아서 늘린다
속은 그냥 배열입니다. 꽉 차면 더 큰 배열을 만들어 옮기는 일을 대신 해 줄 뿐입니다.
2차원 배열은 행과 열로 찾는다
격자로 보이지만 메모리에는 여전히 한 줄로 놓여 있습니다. 번호 두 개가 한 자리를 가리키는 방식입니다.
배열은 번호가 붙은 칸 한 줄이다
값 하나에 변수 하나씩 만들면 백 개를 다룰 수 없습니다. 배열은 이름 하나에 칸을 여러 개 붙여 번호로 꺼냅니다.