블록 배치 알고리즘
메인 페이지의 게시물 블록 배치 규칙에 대해 서술한다.
Last updated
메인 페이지의 게시물 블록 배치 규칙에 대해 서술한다.
Last updated
세자보에 등록된 게시물은 타 게시판과는 다르게 게시물 블록 별로 개별적인 크기가 존재한다. 때문에 게시물 블록을 보드에 가능한 한 효율적으로 배치할 수 있는 규칙이 필요하다.
실제 서비스를 고려한다면, 좀 더 폭넓은 종류의 블록 규격이 필요하겠지만, 테스트 및 시연을 위하여 다음 4가지의 규격으로 블록의 종류를 한정하였다. 모든 블럭의 px은 20 단위로 구성되며, 가로와 세로의 비율이 1:1.4(A4 용지 비율)에 근접하도록 하였다.
블록 배치 알고리즘은 아래와 같이 블록의 배치 및 정렬로 2 단계로 나뉘어져 있다.
지정된 공간에 최대한의 아이템을 넣기 위한 방안으로 Shelf 알고리즘을 응용하였다.
쉐프 알고리즘은 고정적인 높이를 기준으로 배치하기 때문에 상당한 공간 비효율성이 있다고 판단하여 시간을 좀 더 소모하더라도 가능한 한 모든 높이에서 다음을 블럭을 놓을 수 있는 없는지를 판단하여, 왼쪽에서 오른쪽으로, 위에서 아래쪽으로 채워나가는 방식이다.
대략적인 순서는 다음과 같다.
현재 배치해야 하는 블록을 불러온다.
width: 0px, height 0px을 시작으로 width가 현재 화면의 해상도를 넘을때까지 증가시킨다.
해당 픽셀부터 시작한 도형의 좌표에 이미 다른 도형이 배치되어 있을 경우, width를 현재 겹쳐진 도형의 오른쪽 모서리의 좌표 + 20px 혹은 기존의 width + 20px의 값 중, 큰 것으로 갱신시킨 후, 탐색을 재개한다.
만약 Width가 해상도를 넘을 경우, width는 0px로 초기화하고 height를 증가시키며 다음 블록을 넣을 수 있는 공간을 탐색한다.
이때 height는 현재 배치된 모든 블록 중, 가장 낮은 height를 가지는 값 + 20px 및 기존의 height + 20px 중, 더 높은 값을 결정하여 탐색을 속행한다.
현재의 도형의 좌표에 어떠한 다른 도형의 좌표와도 겹치지 않을 경우, 해당 좌표에 블록을 배치한다.
아직 블록 리스트에 더 배치해야 할 게 남아있는 경우, 1번으로 돌아간다.
블록 리스트에 아직 배치해야할 블록이 남아있음에도 현재 넣을 수 있는 공간이 없거나, 모든 블록을 배치했을 경우 작업을 종료한다.
1px 단위로 탐색을 속행할 경우, 최악의 경우 화면 해상도만큼의 시간 복잡도가 나오기 때문에 블록 단위로 픽셀을 증가시켜 탐색하였다. 이 경우 현재 리스팅된 블록의 수만큼의 시간 복잡도가 나오게 된다.
공간 효율성을 위해 모든 경우의 수를 고려할 경우, 반대로 시간 효율성이 극도로 낮아질 수 있기 때문에 블록의 배치는 무조건 왼쪽에서 오른쪽으로 배치하는 순서로 고정시켰다. 그 때문에 다음에 선택해야 하는 블록에 따라 공간 적재율에 차이가 나타나게 된다.
그러므로 아래의 추가적으로 공간 효율성을 높이기 위한 블록 배치에 대한 순서에 대해 연구해보았다.
먼저 DB 내에서 날짜, 관심도 등을 통해 보여줄 게시물들을 정렬하여 리스트를 생성한다. 그리고 해당 리스트 내의 게시물 블록을 어떻게 배치하면 좋을 지에 따라 다시 재정렬을 수행한다.
기본적으로 모든 경우의 수를 고려하기에는 시간면에서 너무나 비효율적으로 동작하기 때문에 어느정도의 휴리스틱을 적용시켜야 했다.
같은 면적의 남은 공간이라도 흩어질 수록 공간 활용이 어려워진다.
위와 같이 가장자리 부분에 작은 크기의 블록이 등장했을 경우, 그 뒤에 큰 블록의 등장으로 인해 빈 공간이 격리될 확률이 높아진다. 즉, 가장자리 측에 큰 블럭을 배치하고, 중간으로 갈수록 작은 블록을 배치함으로 빈 공간을 중간으로 집약시킬 수 있을 것이다.
가로로 배치된 블록 사이의 크기 차이가 클 수록 격리되는 빈 공간이 많이 발생한다.
가로로 배치된 블록의 크기의 차이가 크게 교차하면 그 사이에 끼어있는 빈 공간의 크기도 증가하게 된다. 블록의 크기 차이를 줄이면서 연속적으로 배치하여 해당 빈 공간을 집약시킬 수 있을 것이다.
즉, 블록의 순서는 다음과 같은 경향을 띄도록 순서를 나열한다.
가로에서 가장자리일 경우 큰 블록의 빈도 수를 높이고, 중앙에 가까워질수록 작은 블록의 빈도수를 높이도록 정렬한다. 단, 해당 휴리스틱 또한 완전하지 않기 때문에 그러한 경향을 유도하기 위해 블록을 배치할 확률을 높일 뿐, 배치를 강제하지는 않게 하였다.
이를 통해, 최적의 경우, 남아있는 빈 공간을 중앙으로 적재하여 새로운 블록을 놓을 수 있는 공간을 창출할 수 있을 것이다.
해당 알고리즘을 포함하여, 여러가지 경우에 대한 결과를 시뮬레이션 해보았다.
5,6 시뮬레이션은 각 케이스를 약 10000번을 실행하여 평균 수치를 도출한 값이다.
테스트한 화면의 해상도는 1980x1080이며, 실제로 블록을 배치하기 위한 보드의 픽셀 크기는 2304x1296이다.
먼저 해당 해상도를 모두 작은 블록을 채웠을 때의 적재율이 88%인 것에 반해, 완전한 랜덤 배치마저 80%의 적재율을 보여주는 것은 상당히 의외였다. 알고리즘의 배치가 랜덤에 비해 약 4% 정도 공간 적재율이 높은 반면, 평균 블록 적재 수가 약 3개 정도가 적은 것은 그만큼 공간 활용을 통하여 더 큰 블록을 배치하는 것에 성공했다고 해석할 수 있다.
단, 충분한 통계치를 구하지 못한 것과 해당 알고리즘 또한 확률에 의존하는 부분, 그리고 기존의 랜덤에 의한 공간 적재마저 81%라는 적지 않은 적재율울 보여주고 있기 때문에 정확한 결과라고 단정지을 수는 없다.
분류
내용
Small
100개
공간 적재 비율
88.04347826086956 %
소요 시간
0.8287839889526367 초
블럭 수
60.0 개
분류
내용
X-Large
100개
공간 적재 비율
63.74999999999999 %
소요 시간
0.12566399574279785 초
블럭 수
12.0 개
분류
내용
입력된 블럭 수
4*8 = 32
공간 적재 비율
74.52445652173914 %
소요 시간
0.048868417739868164 초
블럭 수
27.0 개
분류
내용
입력된 블럭 수
4*8 = 32
공간 적재 비율
90.04076086956522 %
소요 시간
0.05285501480102539 초
블럭 수
25.0 개
분류
내용
입력된 블럭 수
32
평균 공간 적재 비율
80.41989130434959 %
평균 소요 시간
0.15594168663024903 초
평균 블럭 수
29.998 개
분류
내용
입력된 블럭 수
32
평균 공간 적재 비율
85.6603260869522 %
평균 소요 시간
0.12356143109003703 초
평균 블럭 수
27.233 개
분류
Small
Medium
Large
X-Large
Width
160px + 20px(margin)
200px + 20px
260px + 20px
320px + 20px
Height
220px + 20px
280px + 20px
360px + 20px
440px + 20px
