로어링 비트맵 크기 계산기

값을 상위 16비트로 갈라 65,536개씩 조각을 내고, 조각마다 따로 담는 방법을 고릅니다. 빽빽한 조각은 비트맵으로, 성긴 조각은 배열로 담습니다. 실제 자료는 고르지 않아서 어떤 구간은 빽빽하고 어떤 구간은 텅 비어 있는데, 조각마다 따로 고르기 때문에 양쪽의 좋은 점만 가져갑니다.

조각 하나에서 배열과 비트맵이 뒤집히는 지점이기 때문입니다. 조각 안에서는 하위 16비트만 담으면 되므로 배열은 값 하나에 2바이트이고, 비트맵은 65,536비트 곧 8,192바이트 고정입니다. 2 × 4096 = 8192이므로 조각의 원소가 4,096개를 넘는 순간 비트맵이 작아집니다. 조각 안 밀도로는 6.25%입니다.

값이 연달아 있을 때입니다. 1000부터 5000까지가 모두 들어 있다면 「시작과 길이」만 적는 편이 훨씬 작습니다. 런 하나에 4바이트라 원소가 아무리 많아도 런이 하나면 6바이트입니다. 다만 값이 다 흩어져 있어 런이 2,048개를 넘으면 비트맵보다 커집니다.

로어링은 정확한 집합이고 블룸 필터는 확률적 구조입니다. 블룸 필터나 HyperLogLog는 틀려도 되는 대신 훨씬 작지만, 로어링은 넣은 것이 그대로 나오고 교집합·합집합도 정확합니다. 크기만 견주면 로어링이 커 보이지만 하는 일이 다릅니다.

가운데 밀도에서입니다. 아주 성기면 정렬 배열이, 아주 빽빽하면 생 비트맵이 더 작습니다. 로어링의 자리는 그 사이, 특히 값이 고르지 않게 흩어져 있을 때입니다. 어떤 구간은 빽빽하고 어떤 구간은 비어 있는 자료에서 단순한 두 방법을 모두 이깁니다.

조각마다 「어느 조각인가」와 「원소가 몇 개인가」를 적어 두어야 해서 붙는 크기입니다. 정확한 크기는 직렬화 형식마다 다르므로 이 계산기는 입력으로 두었습니다. 기본값 8바이트는 조각 번호·원소 수·위치를 담는다고 본 값입니다.

어림값입니다. 값이 흩어진 모양을 「한곳에 몰림」과 「고르게 흩어짐」 두 가지로만 단순화했고, 실제 자료는 그 사이 어딘가입니다. 두 값이 위아래 경계라고 보면 됩니다. 컨테이너 부담과 직렬화 형식도 구현마다 다릅니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.