비트 계층화 - 메모리 사용량 87.5% 감소

개발Vanim animation engine을 할 때, 나는 픽셀 데이터를 저장하는 버퍼를 어떻게 최적화하는지 보려고 했다.다음은 9x9 픽셀의 빈 버퍼입니다.

이 버퍼에 흰색 삼각형을 그려서 상중(5,0)에서 오른쪽 아래(9,9)와 왼쪽 아래(0,9)로 갑시다.

buffer.plot_triangle((5,0), (9,9), (0,9))

컴퓨터의 모든 데이터와 마찬가지로 픽셀은 숫자다.흑백 이미지에 대해 0과 1을 사용하는 것은 의미가 있다.그러나 Vanim 애니메이션 엔진에서 사용하는 버퍼 형식은 사실상 회색조입니다. 즉, 색상은 검은색, 흰색 또는 둘 사이의 색상일 수 있습니다.일반적으로 가장 밝은 색상 값은 255일 수 있습니다.이것은 바이트가 일반적으로 색 값을 설명하는 데 사용되기 때문이다.한 바이트는 8자리로 구성되어 있기 때문에 한 바이트에 저장할 수 있는 최대 가능한 값은 (2^8-1) 또는 255이다.

따라서 배경이 검은색(0), 삼각형이 흰색(255)이면 버퍼는 다음과 같습니다.

이제 왼쪽에서 오른쪽으로 중심에 수평선을 그읍시다.

buffer.plot_line((0,5), (9,5))

다행이다, 우리는 지금 삼각형과 선이 하나 있다!하지만 직선이 아닌 삼각형을 회전하고 싶다면?아마도 우리는 모양을 바꿀 때마다 버퍼를 다시 그릴 수 있습니까?비록 이 해결 방안은 소형 버퍼에 나쁘지 않지만, 만약 우리가 9x9이 아닌 1000x1000의 버퍼를 가지고 있다면?그럼 우리 점수 다시 그려야 돼!
어쩌면 우리는 모든 모양을 그것들의 버퍼에 그려야 할지도 모른다.

현재 모든 모양은 단독으로 수정할 수 있습니다. 화면에 그리려면 모든 버퍼를 그릴 수 있습니다.
하지만 이것은 곧 문제가 될 것이다.각 모양은 9x9 버퍼에 그려집니다.이것은 모든 버퍼의 크기가 81바이트라는 것을 의미한다.우리가 20개의 형상을 그렸다고 가정해 보자.현재 우리는 총 1620바이트의 9x9 버퍼가 20개 있다.1620바이트 자체는 많지 않지만, 그것은 곧 비교적 큰 버퍼의 문제가 될 것이다.만약 우리가 다시 20개의 모양을 그린다면, 이번에는 모양마다 100x100 버퍼가 있습니다.지금 우리는 갑자기 모양마다 10만 바이트, 혹은 총 20만 바이트를 썼다.
이 문제를 해결하기 위해서 우리는 비트 압축이나 나의 용어인'비트 층'을 사용할 수 있다.
비트 계층: 비트 스토리지의 고유한 식별자입니다.
데이터 유형에 있는 모든 사람에게는 고유한 ID가 있을 수 있습니다.

log2(v+1) = n

또는

sqrt(v+1) / 2 = n

이는 최대값이 v인 객체에 대해 고유 IDn가 있을 수 있음을 의미합니다.(이곳에서 우리가 기대하는 n는 바이트가 일치하는 데이터 형식이다.
바이트의 최대 값이 255이므로

log2(256) = 8

이것은 바이트에 8개의 유일한 ID를 저장할 수 있다는 것을 의미한다.각 ID는 한 자리여야 합니다(나중에 이유를 설명하겠습니다).
다음은 바이트에서 사용할 수 있는 고유 ID 목록입니다.

0000 0001 = 1
0000 0010 = 2
0000 0100 = 4
0000 1000 = 8
0001 0000 = 16
0010 0000 = 32
0100 0000 = 64
1000 0000 = 128

이제 가능한 아이디를 알았으니 그림을 그려봅시다!
우리는 처음과 같은 모양부터 시작할 것이다.이제 우리는 색깔 값으로 이 삼각형을 그리지 않고 하나의 ID로 그립니다. 이 삼각형에 첫 번째 가능한 ID가 있다고 가정하십시오. 1.

우리의 첫 번째 예에서 주의할 만한 일이 발생하지 않았다.
하지만 이제 시작할 때와 같은 선을 그려보자. 이 선의 ID는 2다.

버퍼에서 선 ID가 위치(2,5)와 (6,5)의 삼각형 ID를 덮어쓰는 것을 볼 수 있습니다.이것은 만약 우리가 그들의 ID로 다각형을 구분한다면, 우리는 중점이 끊어진 삼각형을 얻을 것이다. 이것은 우리가 원하는 것이 아니다.
존재하는 값을 덮어쓰지 않고 줄 ID를 추가해 보겠습니다.

이제 삼각형 1과 직선 2가 중첩되면 점을 3으로 설정하는 것을 볼 수 있습니다.가능한 ID 목록(1,2,4,8,...)에서ID가 3일 수는 없습니다.즉, 이 점에서 중첩된 원래 ID를 얻을 수 있습니다.
그래서 이 값의 ID를 얻기 위해 우리는 가능한 ID의 합을 먼저 계산하면 3을 얻을 수 있다.이 경우 ID 1+2만 3의 값을 지정할 수 있습니다.따라서 이것은 모양 1과 2가 이 점에서 중첩된다는 것을 의미해야 한다.Bits를 통해 시각적 시각화를 개선할 수 있습니다.

ID: 0000 0001
ID: 0000 0010 +
SUM 0000 0011 = 3

우리 다시 한 번 예를 들자.같은 삼각형(ID 1)과 선(ID 2)을 그려 보겠지만 가장자리(ID 4)에 정사각형을 그리고 중심(ID 8)에 수직선을 그립니다.

이것은 조합 형태가 됩니다.

나는 V programming language 에서 get_amount_of_ids() 라는 함수를 만들어서 그것을 테스트했다.

fn main() {
  mut buffer := Buffer{
    width: 9
    height: 9
  }

  buffer.data = [
    byte(4),4, 4, 4, 13, 4, 4, 4, 4,
         4, 0, 0, 1, 08, 1, 0, 0, 4,
         4, 0, 0, 1, 08, 1, 0, 0, 4,
         4, 0, 1, 0, 08, 0, 1, 0, 4,
         6, 2, 3, 2, 10, 2, 3, 2, 6,
         4, 1, 0, 0, 08, 0, 0, 1, 4,
         4, 1, 0, 0, 08, 0, 0, 1, 4,
         5, 0, 0, 0, 08, 0, 0, 0, 5,
         5, 5, 5, 5, 13, 5, 5, 5, 5
  ]

  mut possible := []byte{}

  for i := 1; i < 256; i *= 2 {
    possible << byte(i)
  }

  buffer.get_amount_of_ids(possible)
}

이 인쇄 4 는 네 개의 모양을 그리는 데 사용되는 유일한 ID의 수량입니다.
그러나 그것은 어떻게 신분증을 얻었습니까?이것이 바로 왜

fn get_ids(arr []byte, target int) []int {
  mut ids := []int

  for i := 0; i < arr.len; i++ {
   if (target & (1 << i)) != 0 { {
      ids << arr[i]
    }
  }

  return ids
}

우선, 함수get_ids()를 정의합니다. 함수는 바이트 배열arr과 목표 값(정수/자연수)을 수락합니다.그리고 이 함수를 반환[]int으로 설정합니다. 이것은 중첩된 ID를 포함하는 정수 그룹입니다.
그런 다음 점에서 중첩된 ID를 검색하는 정수 배열을 만듭니다.mut ids := []int이제 신기한 부분을 살펴봅시다.

for i := 0; i < arr.len; i++ {
  if (target & (1 << i)) != 0 {
    ids << arr[i]
  }
}

먼저 0부터 amount_of_ids - 1까지(0부터 7까지)for i := 0; i < arr.len; i++ {그리고 우리는 이것(target & (1 << i))이 0와 같지 않은지 검사했다.
이것이 바로 우리가 비트 연산자를 토론하는 곳이다.첫 번째부터 시작하겠습니다. & 2진법 "AND"연산자.

0100 0110 (70)
       |
0001 0011 (19)
       v
0000 0010 (2)

여기서 우리는 유사70 & 19 = 2한 물건을 볼 수 있는데, 왜 그런가?이는 & 두 가지 상황에서만 1할 때 사용되기 때문이다.다음은 또 다른 예입니다.

1111 (15)
 | |
0101 (5)
 v v
0101 (5)

여기15와 5는 1위와 3위만 같아 출력5이다.
우리는 아직 << 교환원이 있다.이것은 2진 좌이동 연산자다.

33: 0010 0001
<<
66: 0100 0010

따라서 나머지 위치를 지정한 양으로 옮깁니다.그러나 이것은 간단한 수학으로 설명할 수 있다.다음과 같이 가정합니다.

a << b

다음과 같습니다.

a * (2^b)

17 << 3 = 17 * (2^3) = 136오른쪽으로 이동>>할 수도 있다.이것은 곱셈이 아니라 나눗셈이 됩니다.

a / (2^b)

그것으로 코드를 간소화합시다.

for i := 0; i < arr.len; i++ {
  if (target & (1 << i)) != 0 {
    ids << arr[i]
  }
}

다음이 됩니다.

for i := 0; i < arr.len; i++ {
  if (target & math.pow(2, i)) != 0 {
    ids << arr[i]
  }
}

이제 상상해 봅시다(target & math.pow(2, i)).결합된 버퍼에는 어떤 ID가 상단 중심점13을 구성합니까?
13는 아주 작은 숫자이기 때문에, 당신은 그것을 이미 알고 있을 것이다1 + 4 + 8.하지만 코드를 작성해 봅시다.

get_ids([1,2,4,8,16,32,64,128], 13)

for i := 0; i < arr.len; i++ {
  if (13 & math.pow(2, i)) != 0 {
    ids << arr[i]
  }
}

i의 시작은 01의 IDarr에 해당)이므로 math.pow(2, i)로 바꾸겠습니다. math.pow(2, 0):

for i := 0; i < arr.len; i++ {
  if (13 & math.pow(2, 0)) != 0 {
    ids << arr[i]
  }
}

0지수 규칙에 의하면 모든 0의 멱은 1이기 때문에 math.pow(2, 0)는1:

for i := 0; i < arr.len; i++ {
  if (13 & 1) != 0 {
    ids << arr[i]
  }
}

먼저 "및"작업13 & 1:

0000 1101 (13)
&       |
0000 0001 (1) math.pow(2, 0) i=0
=       v
0000 0001 (1)

13와 1가 모두 공동 1위를 차지했기 때문에 이것은 1라는 것을 의미한다. 지금 우리는 그것이 0인지 아닌지를 검사한다.

if 1 != 0 {
    ids << arr[0]
}

결과가 아니기 때문에0 중첩된 ID를 찾았습니다.
이제 첫 번째 ID1가 생겼습니다.이제 계속 증가i:

0000 1101 (13)
&       
0000 0010 (2) math.pow(2, 1) i=1
=       
0000 0000 (0)

여기서 우리는 13와 2의 공통점이 없다는 것을 볼 수 있다.
다음으로 넘어가겠습니다.

0000 1101 (13)
&     |
0000 0100 (4) math.pow(2, 2) i=2
=     v
0000 0100 (4)

여기서 볼 수 있듯이 i가 2일 때math.pow(2, i)는 4와 같다. 이것은 13와 약간 같다. 이것은 다음 중첩 ID가 4라는 것을 의미한다.
현재 우리는 i가 가능한 모든 ID를 통과할 때까지 계속 이렇게 할 것이다.

0000 1101 (13)
&    |
0000 1000 (8) math.pow(2, 3) i=3
=    v
0000 1000 (8)

다음에 검사할 ID는 16, 32, 64, 128이고 모두 우리의 목표 값인 13을 초과했기 때문에 나머지 값을 테스트하는 것은 무의미하다.
현재 그는 이미 세 개의 ID를 수집했는데, 그것들은 우리의 target 값 [1, 4, 8] 과 같다.우리는 1+4+8의 합을 얻어 이 점을 검증할 수 있다. 즉13 ID의 숫자를 얻으려고 한다.

각 ID는 ids 배열에 첨부된 다음 함수 끝에 반환됩니다.
이제 다각형 정점을 구성하는 ID를 성공적으로 획득했습니다.각 ID에 대한 배열을 만들려면 버퍼의 각 점을 누비고 해당 점의 ID를 얻은 다음 일치하는 ID에 해당 점을 추가할 수 있습니다. 이렇게 하면 각 다각형을 고유의 배열에 분리할 수 있습니다. 이제 각 모양의 점이 있으면 독립적으로 수정하거나 그릴 수 있습니다.
8개의 ID가 있을 수 있으므로 8개의 버퍼를 하나로 결합할 수 있으며 이는 메모리 사용량을 87.5% 줄일 수 있음을 의미합니다!
지금 8바이트가 아닌 32비트 정수를 사용한다면?
원시 블로그: https://stigsen.xyz/blog/bit-layering.html