GoSuda

Vivace Bitmap

By snowmerak
views ...

๋น„ํŠธ๋งต์ด๋ž€?

์—ฌ๊ธฐ์„œ ๋น„ํŠธ๋งต์€ ์ธ๋ฑ์Šค์˜ ํ•œ ์ข…๋ฅ˜์ž…๋‹ˆ๋‹ค. ๊ทธ๋ž˜ํ”ฝ์Šค ์ƒ๊ฐํ•˜๊ณ  ๋“ค์–ด์˜ค์…จ๋‹ค๋ฉด ๋’ค๋กœ๊ฐ€๊ธฐ ๋ˆ„๋ฅด์‹œ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

๊ธฐ๋ณธ ๊ฐœ๋…

๋น„ํŠธ๋งต์€ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์˜ ์ธ๋ฑ์‹ฑ ๊ธฐ์ˆ ์˜ ํ•œ ํ˜•ํƒœ์ž…๋‹ˆ๋‹ค. ํŠน์ • ์นผ๋Ÿผ์˜ ๊ฐ’์„ ๋น„ํŠธ ๋ฐฐ์—ด์ด๋‚˜ ๋ฒกํ„ฐ์˜ ํ•œ ์›์†Œ๋‚˜ ํ˜•ํƒœ๋กœ ํ‘œํ˜„ํ•˜์—ฌ, ๊ฐ ๋น„ํŠธ๊ฐ€ ํ•ด๋‹น ์นผ๋Ÿผ์˜ ํŠน์ • ๊ฐ’์ด ์กด์žฌํ•˜๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ๊ฐ€์žฅ ๊ธฐ๋ณธ์ ์ธ ํ˜•ํƒœ๋Š” ๊ฐ row์— ๋Œ€ํ•ด ๋น„ํŠธ ์ธ๋ฑ์Šค๋ฅผ ํ• ๋‹นํ•˜๊ณ  ์กด์žฌ ์—ฌ๋ถ€๋ฅผ 0๊ณผ 1๋กœ ํ‘œํ˜„ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์„ฑ๋ณ„ ์นผ๋Ÿผ์ด ์žˆ๋Š” ํ…Œ์ด๋ธ”์ด ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ด…์‹œ๋‹ค. ์ด ํ…Œ์ด๋ธ”์— 5๊ฐœ์˜ row๊ฐ€ ์žˆ๊ณ , ์„ฑ๋ณ„ ์นผ๋Ÿผ์˜ ๊ฐ’์ด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค๊ณ  ํ•ฉ์‹œ๋‹ค:

  1. ๋‚จ์„ฑ
  2. ์—ฌ์„ฑ
  3. ๋‚จ์„ฑ
  4. ์—ฌ์„ฑ
  5. ๊ธฐํƒ€

์ด ๊ฒฝ์šฐ, ์„ฑ๋ณ„ ์นผ๋Ÿผ์— ๋Œ€ํ•œ ๋น„ํŠธ๋งต ์ธ๋ฑ์Šค๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ‘œํ˜„๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค:

  • ๋‚จ์„ฑ: 10100
  • ์—ฌ์„ฑ: 01010
  • ๊ธฐํƒ€: 00001

๊ทธ๋ž˜์„œ ์ง„์งœ ์–ด๋””๋‹ค๊ฐ€ ์“ฐ๋ƒ๋ฉด

๊ทธ๋ž˜์„œ ๋‹จ์ˆœํžˆ ์ €๊ฑธ ๋‚˜ํƒ€๋‚ด๊ธฐ ์œ„ํ•œ ๊ฒƒ์ด ์•„๋‹ˆ๋ผ๊ณ  ๋‹ค๋“ค ์ƒ๊ฐํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๋น„ํŠธ๋งต ์ธ๋ฑ์Šค๋ฅผ ์ œ๋Œ€๋กœ ์‚ฌ์šฉํ•ด๋ณด๊ธฐ ์œ„ํ•ด ๋‹ค์Œ ๊ฒฝ์šฐ๋ฅผ ๊ณ ๋ คํ•ด๋ด…์‹œ๋‹ค.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

์ด ํ…Œ์ด๋ธ”์— 1,000,000๊ฐœ์˜ row๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ด…์‹œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ฟผ๋ฆฌ๋ฅผ ์‹คํ–‰ํ•œ๋‹ค๊ณ  ํ•ฉ์‹œ๋‹ค.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

์ด ์ฟผ๋ฆฌ๋Š” active์™€ sex ์นผ๋Ÿผ์ด ๋ชจ๋‘ TRUE์ธ row๋ฅผ ์ฐพ์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ๊ฐ€์žฅ ๋น ๋ฅด๊ฒŒ ๋‘ ์นผ๋Ÿผ์ด TRUE์ธ ์กฐ๊ฑด์„ ์„ฑ๋ฆฝํ•˜๋Š” row๋ฅผ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ bit and ์—ฐ์‚ฐ์„ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

  • active ์นผ๋Ÿผ์— ๋Œ€ํ•œ ๋น„ํŠธ๋งต ์ธ๋ฑ์Šค๊ฐ€ 1100110011... (1,000,000๊ฐœ ๋น„ํŠธ ๋ฐฐ์—ด)์ด ๋ฏธ๋ฆฌ ์ธ๋ฑ์‹ฑ ๋˜์–ด ์žˆ๊ณ ,
  • sex ์นผ๋Ÿผ์— ๋Œ€ํ•œ ๋น„ํŠธ๋งต ์ธ๋ฑ์Šค๊ฐ€ 1010101010... (1,000,000๊ฐœ ๋น„ํŠธ ๋ฐฐ์—ด)์ด ๋ฏธ๋ฆฌ ์ธ๋ฑ์‹ฑ ๋˜์–ด ์žˆ๋‹ค๊ณ  ํ•ฉ์‹œ๋‹ค.

๊ทธ๋Ÿฌ๋ฉด ๋‘ ๋น„ํŠธ๋งต ์ธ๋ฑ์Šค์— ๋Œ€ํ•ด bit and ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•˜์—ฌ, ๋‘ ์นผ๋Ÿผ์ด ๋ชจ๋‘ TRUE์ธ row๋ฅผ ๋น ๋ฅด๊ฒŒ ์ฐพ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹จ์ˆœ ๋น„ํŠธ ์—ฐ์‚ฐ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค๋ฅธ ์ธ๋ฑ์Šค ์Šค์บ”๋ณด๋‹ค ํ›จ์”ฌ ๋น ๋ฅด๊ฒŒ ๊ฒฐ๊ณผ๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

ํŠธ๋ ˆ์ด๋“œ ์˜คํ”„

๋น„ํŠธ๋งต ์ธ๋ฑ์Šค๋Š” ๋งค์šฐ ํšจ์œจ์ ์ผ ์ˆ˜ ์žˆ์ง€๋งŒ, ๋ช‡ ๊ฐ€์ง€ ํŠธ๋ ˆ์ด๋“œ ์˜คํ”„๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹ค๋ฅธ ๋‹จ์ ์ด ๋งŽ์ง€๋งŒ ์ง€๊ธˆ์€ ํ•˜๋‚˜๋งŒ ์งš๊ณ  ๋„˜์–ด๊ฐ€๊ฒ ์Šต๋‹ˆ๋‹ค.

๋ฐ”๋กœ ๋น„ํŠธ๋งต ์ธ๋ฑ์Šค๋Š” ๋‚ฎ์€ ์นด๋””๋„๋ฆฌํ‹ฐ(์ฆ‰, ์นผ๋Ÿผ์— ๊ฐ€๋Šฅํ•œ ๊ฐ’์˜ ์ˆ˜๊ฐ€ ์ ์€ ๊ฒฝ์šฐ)์— ๋” ์ ํ•ฉํ•ฉ๋‹ˆ๋‹ค. ๋†’์€ ์นด๋””๋„๋ฆฌํ‹ฐ์˜ ์นผ๋Ÿผ์— ๋น„ํŠธ๋งต ์ธ๋ฑ์Šค๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ๋น„ํŠธ๋งต์ด ๋งค์šฐ ์ปค์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋†’์€ ์นด๋””๋„๋ฆฌํ‹ฐ์˜ ์นผ๋Ÿผ์— ๋น„ํŠธ๋งต ์ธ๋ฑ์Šค๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด, ๊ฐ ๊ณ ์œ  ๊ฐ’์— ๋Œ€ํ•ด ๋ณ„๋„์˜ ๋น„ํŠธ๋งต์„ ์ƒ์„ฑํ•ด์•ผ ํ•˜๋ฏ€๋กœ, ์ €์žฅ ๊ณต๊ฐ„์ด ๋งŽ์ด ํ•„์š”ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ๋งŒ์•ฝ ์นผ๋Ÿผ์— 1,000,000๊ฐœ์˜ ๊ณ ์œ  ๊ฐ’์ด ์žˆ๋‹ค๋ฉด, 1,000,000๊ฐœ์˜ ๋น„ํŠธ๋งต์„ ์ƒ์„ฑํ•ด์•ผ ํ•˜๋ฏ€๋กœ, ์ด๋Š” ๋งค์šฐ ๋น„ํšจ์œจ์ ์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๊ทธ๋ž˜์„œ ์šฐ๋ฆฌ๋Š”

๋†’์€ ์นด๋””๋„๋ฆฌํ‹ฐ์—์„œ ์˜ค๋Š” ๋น„ํŠธ๋งต์„ ๋Œ€์ฒดํ•˜์—ฌ Roaring Bitmap์ด๋ผ๋Š” ๊ฒƒ์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. Roaring Bitmap์€ ์—ฌ๋Ÿฌ๊ฐ€์ง€ ํŠน์„ฑ์ด ์žˆ์ง€๋งŒ, ๊ฐ€์žฅ ํฐ ๊ธฐ๋ฐ˜ ์ฒ ํ•™๊ณผ ํŠน์„ฑ์€ ๋ฐ์ดํ„ฐ์˜ ๋ฐ€๋„์— ๋”ฐ๋ผ ๊ฐ€์žฅ ์ ํ•ฉํ•œ ์ €์žฅ ๋ฐฉ์‹์„ ๋™์ ์œผ๋กœ ์„ ํƒํ•˜์—ฌ ์••์ถ•๋ฅ ๊ณผ ์—ฐ์‚ฐ ์†๋„ ๋ชจ๋‘ ๊ทน๋Œ€ํ™”ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

Roaring Bitmap์˜ ๊ธฐ๋ณธ ๊ฐœ๋…

2๋‹จ๊ณ„ ์ธ๋ฑ์‹ฑ

Roaring Bitmap์€ ์ •์ˆ˜ ํ•˜๋‚˜๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด ๋จผ์ € ๋‹ค์Œ 2๋‹จ๊ณ„๋ฅผ ๊ฑฐ์นฉ๋‹ˆ๋‹ค. ๋ง์ด 2๋‹จ๊ณ„ ์ธ๋ฑ์‹ฑ์ด์ง€, ๊ทธ๋ƒฅ 2์ฐจ์› ๋ฐฐ์—ด์ด๋ผ๊ณ  ์ƒ๊ฐํ•˜์‹œ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

  • ์ƒ์œ„ 16๋น„ํŠธ ์ถ”์ถœ: ์ •์ˆ˜์˜ ์ƒ์œ„ 16๋น„ํŠธ๋ฅผ ์ถ”์ถœํ•˜์—ฌ, ์ด๋ฅผ ์ธ๋ฑ์Šค๋กœ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. ์ด 65536๋งŒํผ์˜ ๊ธธ์ด๋ฅผ ๊ฐ€์ง„ 2์ฐจ์› ๋ฐฐ์—ด ์ค‘ ๋ฐ”๊นฅ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๊ฐ€ ๋˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ๋ฐฐ์—ด์€ ํ›„์ˆ ํ•  ์ปจํ…Œ์ด๋„ˆ์˜ ์ฃผ์†Œ๋ฅผ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค.
  • ํ•˜์œ„ 16๋น„ํŠธ ์ถ”์ถœ: ์ •์ˆ˜์˜ ํ•˜์œ„ 16๋น„ํŠธ๋ฅผ ์ถ”์ถœํ•˜์—ฌ, ์ด๋ฅผ ์ปจํ…Œ์ด๋„ˆ ๋‚ด์—์„œ์˜ ์œ„์น˜๋กœ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.

์ปจํ…Œ์ด๋„ˆ

์ด ์ปจํ…Œ์ด๋„ˆ๋Š” ๋ฐฉ๊ธˆ ๋น„์œ ํ–ˆ๋˜ ๋Œ€๋กœ 2์ฐจ์› ๋ฐฐ์—ด ์ค‘ ์•ˆ์ชฝ ๋ฐฐ์—ด์— ํ•ด๋‹นํ•ฉ๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ ์ƒ์œ„ 16๋น„ํŠธ์˜ ๊ทธ๊ฒƒ๊ณผ๋Š” ๋‹ค๋ฅด๊ฒŒ, ์ด ์ปจํ…Œ์ด๋„ˆ๋Š” ๋‚ด๋ถ€ ๋ฐ์ดํ„ฐ๊ฐ€ ์–ผ๋งˆ๋‚˜ ์žˆ๋ƒ์— ๋”ฐ๋ผ ๋‚ด๋ถ€ ๊ตฌ์กฐ๊ฐ€ ๋‹ฌ๋ผ์ง‘๋‹ˆ๋‹ค. Roaring Bitmap์€ ๋‹ค์Œ 3๊ฐ€์ง€ ์ปจํ…Œ์ด๋„ˆ๋ฅผ ์ง€์›ํ•ฉ๋‹ˆ๋‹ค.

  • Array Container: ์ด ์ปจํ…Œ์ด๋„ˆ๋Š” ๋‚ด๋ถ€์— ์ €์žฅ๋œ ๋ฐ์ดํ„ฐ๊ฐ€ ์ ์„ ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ, 4096๊ฐœ ์ดํ•˜์˜ ์›์†Œ๋ฅผ ์ €์žฅํ•  ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค. ์ด ์ปจํ…Œ์ด๋„ˆ๋Š” ๋‹จ์ˆœํžˆ ์ •๋ ฌ๋œ ์ •์ˆ˜ ๋ฐฐ์—ด๋กœ ๊ตฌํ˜„๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด์ง„ ํƒ์ƒ‰ ํ•˜์—ฌ ์›์†Œ๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • Bitmap Container: ์ด ์ปจํ…Œ์ด๋„ˆ๋Š” ๋‚ด๋ถ€์— ์ €์žฅ๋œ ๋ฐ์ดํ„ฐ๊ฐ€ ๋งŽ์„ ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ, 4096๊ฐœ ์ดˆ๊ณผ์˜ ์›์†Œ๋ฅผ ์ €์žฅํ•  ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค. ์ด ์ปจํ…Œ์ด๋„ˆ๋Š” 65536๋น„ํŠธ(8192๋ฐ”์ดํŠธ)์˜ ๋น„ํŠธ๋งต์œผ๋กœ ๊ตฌํ˜„๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ๋น„ํŠธ๋Š” ํ•ด๋‹น ์œ„์น˜์˜ ์ •์ˆ˜๊ฐ€ ์กด์žฌํ•˜๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
  • Run Container: ์ด ์ปจํ…Œ์ด๋„ˆ๋Š” ์—ฐ์†๋œ ์ •์ˆ˜ ๋ฒ”์œ„๋ฅผ ์ €์žฅํ•  ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 1, 2, 3, 4, 5์™€ ๊ฐ™์€ ์—ฐ์†๋œ ์ •์ˆ˜๋“ค์„ ์ €์žฅํ•  ๋•Œ ํšจ์œจ์ ์ž…๋‹ˆ๋‹ค. ์ด ์ปจํ…Œ์ด๋„ˆ๋Š” (์‹œ์ž‘ ๊ฐ’, ๊ธธ์ด) ์Œ์˜ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ ๋‹ค ์žˆ์œผ๋ฉด? ๊ทธ๋ƒฅ ์ฒ˜์Œ๋ถ€ํ„ฐ ๋๊นŒ์ง€ ๋‹ค ์žˆ๋‹ค๋Š” ๋œป์ด๋‹ˆ, (0, 65536) ํ•˜๋‚˜๋งŒ ์ €์žฅํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

์ด๋Ÿฌํ•œ ๋ฐฉ์‹์€ Roaring Bitmap์ด ๋งค์šฐ ํšจ์œจ์ ์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜๊ณ , ๋‹ค์–‘ํ•œ ๋ฐ์ดํ„ฐ ๋ฐ€๋„์— ๋Œ€ํ•ด ์ตœ์ ์˜ ์„ฑ๋Šฅ์„ ์ œ๊ณตํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•ฉ๋‹ˆ๋‹ค.

Roaring Bitmap์˜ ๊ธฐ๋Šฅ

๊ธฐ๋ณธ ๊ธฐ๋Šฅ

Roaring Bitmap์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ธฐ๋ณธ ๊ธฐ๋Šฅ์„ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค.

  • ์‚ฝ์ž…: ์ƒˆ๋กœ์šด ์ •์ˆ˜๋ฅผ ๋น„ํŠธ๋งต์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค. ์ด ๊ณผ์ •์—์„œ ์ ์ ˆํ•œ ์ปจํ…Œ์ด๋„ˆ๋ฅผ ์„ ํƒํ•˜๊ฑฐ๋‚˜, ํ•„์š”์— ๋”ฐ๋ผ ์ปจํ…Œ์ด๋„ˆ๋ฅผ ๋ณ€ํ™˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์‚ญ์ œ: ๊ธฐ์กด ์ •์ˆ˜๋ฅผ ๋น„ํŠธ๋งต์—์„œ ์ œ๊ฑฐํ•ฉ๋‹ˆ๋‹ค. ์ด ๊ณผ์ •์—์„œ๋„ ์ปจํ…Œ์ด๋„ˆ์˜ ์ƒํƒœ์— ๋”ฐ๋ผ ์ ์ ˆํ•œ ์ฒ˜๋ฆฌ๊ฐ€ ์ด๋ฃจ์–ด์ง‘๋‹ˆ๋‹ค.
  • ๊ฒ€์ƒ‰: ํŠน์ • ์ •์ˆ˜๊ฐ€ ๋น„ํŠธ๋งต์— ์กด์žฌํ•˜๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค. ์ด ๊ณผ์ •์€ ๋งค์šฐ ๋น ๋ฅด๊ฒŒ ์ˆ˜ํ–‰๋ฉ๋‹ˆ๋‹ค.

์ง‘ํ•ฉ ์—ฐ์‚ฐ

Roaring Bitmap์€ ๋˜ํ•œ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ง‘ํ•ฉ ์—ฐ์‚ฐ์„ ์ง€์›ํ•ฉ๋‹ˆ๋‹ค.

  • ํ•ฉ์ง‘ํ•ฉ (Union): ๋‘ ๋น„ํŠธ๋งต์˜ ๋ชจ๋“  ์›์†Œ๋ฅผ ํฌํ•จํ•˜๋Š” ์ƒˆ๋กœ์šด ๋น„ํŠธ๋งต์„ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค.
  • ๊ต์ง‘ํ•ฉ (Intersection): ๋‘ ๋น„ํŠธ๋งต์— ๋ชจ๋‘ ์กด์žฌํ•˜๋Š” ์›์†Œ๋งŒ์„ ํฌํ•จํ•˜๋Š” ์ƒˆ๋กœ์šด ๋น„ํŠธ๋งต์„ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค.
  • ๋Œ€์นญ ์ฐจ์ง‘ํ•ฉ (Symmetric Difference): ๋‘ ๋น„ํŠธ๋งต ์ค‘ ํ•˜๋‚˜์—๋งŒ ์กด์žฌํ•˜๋Š” ์›์†Œ๋ฅผ ํฌํ•จํ•˜๋Š” ์ƒˆ๋กœ์šด ๋น„ํŠธ๋งต์„ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค.

์ด๋Ÿฌํ•œ ์—ฐ์‚ฐ๋“ค์€ ๋น„ํŠธ๋งต์˜ ์ปจํ…Œ์ด๋„ˆ ์œ ํ˜•์— ๋”ฐ๋ผ ์ตœ์ ํ™”๋˜์–ด ๋งค์šฐ ๋น ๋ฅด๊ฒŒ ์ˆ˜ํ–‰๋ฉ๋‹ˆ๋‹ค.

Go ์–ธ์–ด์—์„œ

Go ์–ธ์–ด์—์„œ๋Š” github.com/RoaringBitmap/roaring ํŒจํ‚ค์ง€๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ Roaring Bitmap์„ ์‰ฝ๊ฒŒ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ํŒจํ‚ค์ง€๋Š” Roaring Bitmap์˜ ๋ชจ๋“  ๊ธฐ๋Šฅ์„ ์ œ๊ณตํ•˜๋ฉฐ, Go ์–ธ์–ด์˜ ํŠน์„ฑ์— ๋งž๊ฒŒ ์ตœ์ ํ™”๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.

์„ค์น˜

1go get github.com/RoaringBitmap/roaring/v2

์‚ฌ์šฉ ์˜ˆ์‹œ

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Inizializza con 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inizializza con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Aggiunge 5
14	b2.Add(10) // Aggiunge 10
15
16	b2.Remove(12) // Rimuove 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Le operazioni sul bitmap modificano l'originale, quindi usa una copia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}
12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

์œ„ ์˜ˆ์‹œ ์ฝ”๋“œ์—์„œ ๋‚˜์˜ค์ง€ ์•Š์€ ์ฃผ์š” ๊ธฐ๋Šฅ๋“ค๋กœ

  • Contains(x uint32) bool: ํŠน์ • ๊ฐ’์ด ๋น„ํŠธ๋งต์— ์กด์žฌํ•˜๋Š”์ง€ ํ™•์ธ
  • GetCardinality() uint64: ๋น„ํŠธ๋งต์— ํฌํ•จ๋œ ์›์†Œ์˜ ๊ฐœ์ˆ˜ ๋ฐ˜ํ™˜
  • Rank(x uint32) uint64: ํŠน์ • ๊ฐ’ ์ดํ•˜์˜ ์›์†Œ ๊ฐœ์ˆ˜ ๋ฐ˜ํ™˜
  • ToBytes() ([]byte, error): ๋น„ํŠธ๋งต์„ ๋ฐ”์ดํŠธ ์Šฌ๋ผ์ด์Šค๋กœ ์ง๋ ฌํ™”
  • FromBytes(data []byte) error: ๋ฐ”์ดํŠธ ์Šฌ๋ผ์ด์Šค์—์„œ ๋น„ํŠธ ๋งต ๋ณต์›
  • Clone() *Bitmap: ๋น„ํŠธ๋งต์˜ ๋ณต์ œ๋ณธ ์ƒ์„ฑ
  • Clear(): ๋น„ํŠธ๋งต ์ดˆ๊ธฐํ™”
  • NextValue(x uint32) int64: x๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ๋‹ค์Œ ์›์†Œ ๋ฐ˜ํ™˜
  • PreviousValue(x uint32) int64: x๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜
  • Maximum() uint32: ๋น„ํŠธ๋งต์—์„œ ๊ฐ€์žฅ ํฐ ์›์†Œ ๋ฐ˜ํ™˜
  • Minimum() uint32: ๋น„ํŠธ๋งต์—์„œ ๊ฐ€์žฅ ์ž‘์€ ์›์†Œ ๋ฐ˜ํ™˜

์ด๋Ÿฐ ๊ธฐ๋Šฅ๋“ค์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ž์„ธํ•œ ๋‚ด์šฉ์€ ๊ณต์‹ ๋ฌธ์„œ๋ฅผ ์ฐธ๊ณ ํ•˜์„ธ์š”.

์ฐธ๊ณ ๋กœ roaring ํŒจํ‚ค์ง€๋Š” ๋‚ด๋ถ€์— uint32 ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ uint64๋ฅผ ์ง€์›ํ•˜๋Š” ํŒจํ‚ค์ง€๋ฅผ ํฌํ•จํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฑฐ์˜ ๋™์ผํ•œ ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์ œ๊ณตํ•จ์œผ๋กœ ๋ฐ”๋กœ ๊ต์ฒดํ•˜์—ฌ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Inizializza con 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inizializza con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Aggiunge 5
14	b2.Add(10) // Aggiunge 10
15
16	b2.Remove(12) // Rimuove 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Le operazioni sul bitmap modificano l'originale, quindi usa una copia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

๋งˆ์น˜๋ฉฐ

Roaring Bitmap์€ ๋†’์€ ์นด๋””๋„๋ฆฌํ‹ฐ์˜ ์ •์ˆ˜ ์ง‘ํ•ฉ์„ ํšจ์œจ์ ์œผ๋กœ ์ €์žฅํ•˜๊ณ  ์กฐ์ž‘ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฐ•๋ ฅํ•œ ๋„๊ตฌ์ž…๋‹ˆ๋‹ค. Go ์–ธ์–ด์—์„œ github.com/RoaringBitmap/roaring ํŒจํ‚ค์ง€๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด, Roaring Bitmap์˜ ๋ชจ๋“  ๊ธฐ๋Šฅ์„ ์‰ฝ๊ฒŒ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ํŒจํ‚ค์ง€๋Š” ๋‹ค์–‘ํ•œ ์ปจํ…Œ์ด๋„ˆ ์œ ํ˜•๊ณผ ์ตœ์ ํ™”๋œ ์—ฐ์‚ฐ์„ ํ†ตํ•ด, ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰๊ณผ ์„ฑ๋Šฅ์„ ๊ทน๋Œ€ํ™”ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์ธ๋ฑ์‹ฑ, ๋กœ๊ทธ ๋ถ„์„, ํ†ต๊ณ„ ๊ณ„์‚ฐ ๋“ฑ ๋‹ค์–‘ํ•œ ๋ถ„์•ผ์—์„œ Roaring Bitmap์„ ํ™œ์šฉํ•˜์—ฌ ํšจ์œจ์ ์ธ ๋ฐ์ดํ„ฐ ์ฒ˜๋ฆฌ๋ฅผ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Roaring Bitmap์€ ํŠนํžˆ ๋Œ€๊ทœ๋ชจ ๋ฐ์ดํ„ฐ์…‹์—์„œ ๋†’์€ ์„ฑ๋Šฅ์„ ๋ฐœํœ˜ํ•˜๋ฉฐ, diverse applicazioni เคฎเฅ‡เค‚ เค‰เคชเคฏเฅ‹เค—เฅ€ เคนเฅ‹ เคธเค•เคคเคพ เคนเฅˆเฅค Go ์–ธ์–ด์˜ ๊ฐ„๊ฒฐํ•˜๊ณ  ํšจ์œจ์ ์ธ ๋ฌธ๋ฒ•๊ณผ ๊ฒฐํ•ฉํ•˜์—ฌ, Roaring Bitmap์€ ๊ฐœ๋ฐœ์ž๋“ค์—๊ฒŒ ๊ฐ•๋ ฅํ•œ ๋„๊ตฌ๋ฅผ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค. ์•ž์œผ๋กœ๋„ Roaring Bitmap์˜ ๋ฐœ์ „๊ณผ ํ•จ๊ป˜, ๋” ๋งŽ์€ ๊ธฐ๋Šฅ๊ณผ ์ตœ์ ํ™”๊ฐ€ ์ด๋ฃจ์–ด์งˆ ๊ฒƒ์œผ๋กœ ๊ธฐ๋Œ€๋ฉ๋‹ˆ๋‹ค.

์ „ ์ด๊ฑธ ์™œ ํ–ˆ๋ƒ๊ตฌ์š”? ์‹œ๊ณ„์—ด ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์—์„œ ๊ฐ ํƒœ๊ทธ ๋ณ„ ์ธ๋ฑ์‹ฑ๊ณผ ๋น ๋ฅธ ํ•ฉ์ง‘ํ•ฉ ์—ฐ์‚ฐ์„ ์œ„ํ•ด์„œ์š”.