Bạn cần một tập hợp các số nguyên — theo dõi những id đã thấy, những trạng thái đã bật, những phần tử được chọn. Phản xạ mặc định là std::set<int> hoặc std::unordered_set<int>, gõ một dòng là xong. Nhưng nếu miền giá trị nhỏ và biết trước (ví dụ id trong khoảng 0..1 triệu), có một cấu trúc nén hơn hàng trăm lần và nhanh hơn hàng nghìn lần: bitset. Tôi đo cả ba lựa chọn trong container gcc:13, và con số cho thấy "chọn set cho tiện" có thể phí cả RAM lẫn tốc độ một cách khủng khiếp — hoặc ngược lại, bitset có thể là lựa chọn sai nếu bạn dùng nhầm chỗ.
Một bit cho một phần tử
Bitset là một mảng bit: bit thứ i bằng 1 nghĩa là i thuộc tập. Lưu bằng một mảng uint64 — mỗi word 64 bit chứa 64 phần tử của miền. Thêm phần tử i là bật bit (A[i/64] |= 1<<(i%64)), kiểm tra là đọc bit. So với std::set — một cây đỏ-đen mà mỗi node tốn ~48 byte (ba con trỏ, một byte màu, giá trị, đệm) — hay unordered_set (~40 byte/phần tử gồm node và bucket), bitset chỉ tốn 1 bit cho mỗi vị trí của miền.
Điều này cho bitset ba lợi thế khi miền nhỏ và dày đặc: (1) bộ nhớ — nén hàng trăm lần; (2) phép tập hợp — hợp/giao/hiệu là OR/AND/XOR trên uint64, xử lý 64 phần tử mỗi lệnh CPU; (3) kiểm tra thành viên — một phép dịch và AND, O(1), không cache miss theo con trỏ. Tôi đo cả ba.
Đo: nén 192 lần, giao nhanh 10.000 lần
Tôi dựng một tập ~501 nghìn phần tử (~50%) trên miền 0..1 triệu, bằng cả ba cấu trúc:
Miền 0..1 triệu, tập ~501k phần tử (~50%), g++ -O2:
A. BỘ NHỚ:
bitset (mảng uint64) : 122 KB (1 bit/phần tử của miền)
std::set<int> : ~23.000 KB (~48 B/node × 501k)
unordered_set<int> : ~19.000 KB (~40 B/phần tử × 501k)
-> bitset nén ~192 lần so với std::set
B. GIAO (intersect) A & B:
bitset AND : 4,8 µs (AND 64 phần tử/lệnh + popcount)
std::set lặp + count : 47.851,2 µs (lặp qua A, tra B: O(n log n))
-> bitset nhanh hơn ~10.000 lần
C. KIỂM TRA THÀNH VIÊN (1 triệu lần test):
bitset test bit : 0,39 ns/test (O(1), 1 lệnh dịch+and)
std::set count : 338,91 ns/test (O(log n), cache miss mỗi bước)
unordered_set count : 19,83 ns/test (O(1) tb, nhưng hash + cache miss)
Nhìn A: cùng tập ~501 nghìn phần tử, bitset chỉ tốn 122 KB, còn std::set tốn ~23 MB — bitset nén ~192 lần. Vì set trả ~48 byte cho mỗi phần tử (node cây), còn bitset trả 1 bit. B còn ấn tượng hơn: phép giao hai tập bằng bitset chỉ mất 4,8 µs (AND từng cặp word — 64 phần tử mỗi lệnh — rồi popcount), trong khi std::set phải lặp qua từng phần tử của A và tra trong B, mất 47,9 mili-giây — bitset nhanh hơn ~10.000 lần. Và C: kiểm tra thành viên, bitset 0,39 ns so với std::set 338,9 ns (nhanh 870 lần — set phải đi ~20 bước cây, mỗi bước cache miss) và unordered_set 19,8 ns (nhanh 50 lần — hash vẫn có một cache miss). Với tập số nguyên miền nhỏ dày đặc, bitset thắng ở mọi mặt, và không phải chút ít — mà hàng trăm tới hàng nghìn lần.
Một lần tôi đo hớ: "set nào cũng như nhau" rồi "bitset luôn tốt"
Tôi vào đo với niềm tin lười: "cần tập thì std::set, chọn cái nào cũng như nhau, tiện là được". Đo phá tan: với miền nhỏ dày đặc, bitset nén RAM 192 lần, giao tập nhanh 10.000 lần, kiểm tra thành viên nhanh 870 lần. "Set cho tiện" có thể phí hàng chục MB và làm chậm hàng nghìn lần. Nhưng rồi tôi suýt rơi vào đo hớ ngược: "vậy bitset luôn tốt hơn vì nó nhỏ và nhanh". Cũng sai — bitset tốn M bit cho cả miền, bất kể tập có bao nhiêu phần tử. Nếu miền rộng mà tập thưa — ví dụ 100 phần tử nằm rải trong 0..1 tỷ — bitset cần 1 tỷ bit = 125 MB dù chỉ có 100 phần tử, trong khi std::set/hash chỉ tốn ~100 node. Lúc đó bitset là lựa chọn tệ.
Bài học đo lường: bitset (1 bit/phần tử của miền) thắng std::set/hash ĐẬM khi miền NHỎ & DÀY ĐẶC — nén RAM ~192x (122 KB vs 23 MB), giao/hợp ~10.000x nhanh (AND 64 phần tử/lệnh), thành viên 0,39 vs 338,9 ns (870x) — vì dùng bit và phép AND/OR song song thay con trỏ + cache miss; NHƯNG miền RỘNG & THƯA thì bitset phí M bit (0..1 tỷ = 125 MB dù ít phần tử), set/hash hợp hơn. Nếu tôi tin "set nào cũng vậy" tôi bỏ lỡ một tối ưu hàng nghìn lần cho miền nhỏ; nếu tôi tin "bitset luôn tốt" tôi phí 125 MB cho một tập 100 phần tử. Chọn đúng phụ thuộc miền và mật độ.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi tập số nguyên có miền nhỏ, biết trước, và dày — dùng bitset. Cờ trạng thái (0..số-trạng-thái), tập id trong một khoảng, sàng nguyên tố, đánh dấu "đã thăm" trong đồ thị với đỉnh đánh số liên tục — tất cả là ứng viên hoàn hảo. std::bitset<N> (kích thước cố định) hay std::vector<uint64_t> (động) cho bạn nén và tốc độ. Và nếu bạn làm nhiều phép hợp/giao/hiệu các tập, bitset gần như luôn thắng vì phép bit song song.
Hệ quả thứ hai: khi tập thưa trên miền rộng — dùng hash set (hoặc set nếu cần thứ tự). unordered_set tốn bộ nhớ theo số phần tử, không theo miền, nên nó là lựa chọn đúng khi bạn có ít phần tử rải trên một không gian lớn (id 64-bit, khóa chuỗi băm ra số lớn). Đừng ép bitset vào đây — bạn sẽ cấp phát một biển bit rỗng. (Có cấu trúc lai như roaring bitmap xử lý cả hai trường hợp, nén theo khối — đó là lý do các cơ sở dữ liệu phân tích dùng chúng.)
Hệ quả thứ ba là tinh thần đo lường: "tập hợp" không phải một lựa chọn duy nhất — hình dạng dữ liệu (miền, mật độ) quyết định cấu trúc. Con số mang theo: bitset vs std::set cho tập số nguyên: miền NHỎ & DÀY (0..1tr, ~50%) thì bitset nén ~192x RAM (122 KB vs 23 MB), giao tập ~10.000x (4,8 µs vs 47.851 µs, AND 64 phần tử/lệnh + popcount), thành viên 0,39 vs 338,9 ns (870x); nhưng miền RỘNG & THƯA (100 phần tử trong 0..1 tỷ = 125 MB) thì bitset phí, unordered_set/set (~số phần tử) hợp hơn. Chọn theo miền nhỏ/rộng và dày/thưa, không mặc định std::set. Cùng khái niệm "tập", nhưng cấu trúc đúng khác nhau cả nghìn lần tùy dữ liệu.
Thử ba mươi giây
Dựng một tập vài trăm nghìn số nguyên trong khoảng 0..1 triệu bằng hai cách: một std::set<int> và một mảng uint64 làm bitset (bật bit thứ i). So bộ nhớ ước tính (số phần tử × ~48 byte cho set, số phần tử của miền / 8 cho bitset) — bitset nhỏ hơn cả trăm lần. Rồi tạo hai tập và tính giao của chúng: với bitset là một vòng A[i] & B[i] chạy vèo, với set là lặp và tra cứu, chậm hơn hàng nghìn lần. Cuối cùng, thử tưởng tượng (hoặc đo) trường hợp ngược: một tập chỉ 100 phần tử nhưng giá trị tới hàng tỷ — bitset lúc này phải cấp cả trăm MB, còn set chỉ 100 node. Ba mươi giây đó cho bạn thấy điều mà "cứ dùng set cho tiện" giấu đi: cấu trúc tập đúng phụ thuộc miền giá trị nhỏ hay rộng và tập dày hay thưa — chọn khớp thì nhanh và gọn hàng nghìn lần, chọn nhầm thì phí RAM hoặc phí thời gian.
